[Line] 2019 상반기 LINE 인턴 채용 코딩테스트
1. 문제 이해
구현 + BFS를 사용하여 최단시간을 구하는 문제
2. 문제 분석
1. 브라운이 특정 칸에 도달할 수 있는 시간: BFS로 탐색
2. 특정 시간에 코니가 도달한 칸에 브라운이 가서 잡을 수 있는지:
-
브라운은 2초 후에 제자리로 돌아올 수 있습니다.
ex) 2 -> 1 -> 2 -
만약 코니가 11초에 x에 도착했을 때
1, 3, 5, 7, 9, 11초 중 한 번이라도 브라운이 그 칸에 도착했다면 코니를 잡을 수 있습니다.
-
만약 코니가 10초에 x에 도착했다면
0, 2, 4, 6, 8, 10초 중 한 번이라도 브라운이 그 칸에 도착했다면 잡을 수 있습니다. -
따라서 도착 시간을 홀수, 짝수로 나누어서 확인해야 합니다.
3. 코드
public class Main {
static boolean[][] visited = new boolean[200_001][2];
static final int even = 0, odd = 1;
static Queue<Integer> q = new LinkedList<>();
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int conyPosition = sc.nextInt();
int brown = sc.nextInt();
q.add(brown);
visited[brown][even] = true;
visited[brown][odd] = true;
int time = 0;
while(inRange(conyPosition)) {
int timeRemainder = time%2;
if(visited[conyPosition][timeRemainder]) {//끝
System.out.println(time);
return;
}
time++;
conyPosition += time;
updateNextBrown(q.size(), time);
}
System.out.println(-1);
}
public static void updateNextBrown(int size, int time) {
for(int i = 0; i < size; i++) {
int index = q.poll();
int[] nextIndex = {index-1, index+1, index*2};
int timeRemainder = time%2;
for(int j = 0; j < 3; j++) {
int now = nextIndex[j];
if(inRange(now) && !visited[now][timeRemainder]) {
visited[now][timeRemainder] = true;
q.add(now);
}
}
}
}
public static boolean inRange(int num) {
if(0 <= num && num <= 200_000) {
return true;
} else {
return false;
}
}
}
Author And Source
이 문제에 관하여([Line] 2019 상반기 LINE 인턴 채용 코딩테스트), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@mincho920/Line-2019-상반기-LINE-인턴-채용-코딩테스트저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)