[LINE 코딩테스트] 상반기 기출문제 파헤쳐보기

 

LINE은 하반기에 채용전환형 인턴을 채용합니다. 이번주 일요일에 2019 LINE DEVEL-UP 코딩 테스트가 있죠?

2019년 상반기 LINE 인턴 채용 코딩테스트에는 어떤 문제가 나왔는지 한번 살펴보겠습니다.

문제 설명

문제

연인 코니와 브라운은 광활한 들판에서 ‘나 잡아 봐라’ 게임을 한다. 이 게임은 브라운이 코니를 잡거나, 코니가 너무 멀리 달아나면 끝난다. 게임이 끝나는데 걸리는 최소 시간을 구하시오.

조건

1. 코니는 처음 위치 C에서 1초 후 1만큼 움직이고, 이후에는 가속이 붙어 매 초마다 이전 이동 거리 + 1만큼 움직인다. 즉 시간에 따른 코니의 위치는 C, C + 1, C + 3, C + 6, …이다.
2. 브라운은 현재 위치 B에서 다음 순간 B – 1, B + 1, 2 * B 중 하나로 움직일 수 있다.
3. 코니와 브라운의 위치 p는 조건 0 <= x <= 200,000을 만족한다.
4. 브라운은 범위를 벗어나는 위치로는 이동할 수 없고, 코니가 범위를 벗어나면 게임이 끝난다.

입력 형식

표준 입력의 첫 줄에 코니의 위치 C와 브라운의 위치 B를 공백으로 구분하여 순서대로 읽는다.

출력 형식

브라운이 코니를 잡을 수 있는 최소시간 N초를 표준 출력한다. 단 브라운이 코니를 잡지 못한 경우에는 -1을 출력한다.

예제 

입력: 11 2

출력: 5

코니의 위치: 11 → 12 → 14 → 17 → 21 → 26

브라운의 위치: 2 → 3 → 6 → 12 → 13 → 26

브라운은 코니를 5초 만에 잡을 수 있다.

 

문제 풀이

어디서 많이 본 문제같은데..

얼마전 포스팅했던 숨바꼭질 문제의 응용문제라고 생각됩니다. 먼저 숨바꼭질 문제를 확인해보세요.

[BOJ 1697] 숨바꼭질 파이썬(Python) 풀이

 

Python3 코드

from collections import deque
def solve(conyPosition, brownPosition):
    time = 0
    visit = [[0]*2 for _ in range(200001)]
    q = deque()
    q.append((brownPosition, 0))

    while 1:
        conyPosition += time

        if conyPosition > 200000:
            return -1
        if visit[conyPosition][time%2]:
            return time

        for i in range(0, len(q)):
            current = q.popleft()
            currentPosition = current[0]
            newTime = (current[1]+1)%2

            newPosition = currentPosition - 1
            if newPosition >= 0 and not visit[newPosition][newTime]:
                visit[newPosition][newTime] = True
                q.append((newPosition, newTime))

            newPosition = currentPosition + 1
            if newPosition < 200001 and not visit[newPosition][newTime]:
                visit[newPosition][newTime] = True
                q.append((newPosition, newTime))

            newPosition = currentPosition * 2
            if newPosition < 200001 and not visit[newPosition][newTime]:
                visit[newPosition][newTime] = True
                q.append((newPosition, newTime))
        time+=1

 

C++ 코드

int solve(int conyPosition, int brownPosition) {
    int time = 0;
    bool visit[200001][2];
    queue<pair<int, int> > queue;

    memset(visit, 0, sizeof(visit));
    queue.push(make_pair(brownPosition, 0));

    while (1) {
    	conyPosition += time;

        if (conyPosition > 200000)
            return -1;
        if (visit[conyPosition][time % 2])
            return time;

        for (int i = 0, size = queue.size(); i < size; i++) {
            int currentPosition = queue.front().first;
            int newTime = (queue.front().second + 1) % 2;
            int newPosition;

            queue.pop();

            newPosition = currentPosition - 1;
            if (newPosition >= 0 && !visit[newPosition][newTime]) {
                visit[newPosition][newTime] = true;
                queue.push(make_pair(newPosition, newTime));
            }

            newPosition = currentPosition + 1;
            if (newPosition < 200001 && !visit[newPosition][newTime]) {
                visit[newPosition][newTime] = true;
                queue.push(make_pair(newPosition, newTime));
            }

            newPosition = currentPosition * 2;
            if (newPosition < 200001 && !visit[newPosition][newTime]) {
                visit[newPosition][newTime] = true;
                queue.push(make_pair(newPosition, newTime));
            }
        }
        time++;
    }
}

 

자세한 해설은 아래 LINE 기술블로그를 참고해주세요.

2019년 상반기 LINE 인턴 채용 코딩테스트 문제 해설 - LINE ENGINEERING

 

[2019 라인 코딩테스트 후기] 2019년 하반기 LINE SW개발 DEVEL-UP 인턴십 코딩테스트 후기