MancityBallboy 흔적 남기기

2021 상반기 라인 인터쉽 코딩테스트 후기 및 복기

01 May 2021

2021 상반기 라인 인턴쉽 코딩테스트 후기

오늘 라인 인턴쉽 코딩테스트를 쳤습니다.

2시간 동안 3문제를 풀어야 했고, 1번 문제와 3번 문제는 해결 했다고 생각하니 풀지 못한 2번만 복기 하도록 하겠습니다.

문제

배열이 주어지면 각 인덱스의 숫자를 기준으로 기준이 된 숫자 보다 크면서 가장 가까이 위치한 숫자의 인덱스를 기준이된 인덱스에 저장하여서 완성된 배열을 만드는 문제였습니다.

  • 가장 가까이 있는 인덱스가 2개라면 작은 인덱스를 저장하여야 합니다.
  • 배열 내에 자기보다 큰 수가 없다면 -1을 저장하여야 합니다.

EX)

input = [3,5,4,1,2]

output = [1, -1, 1, 2, 2]

3은 5가 가장 가까이 있으면서 큰 수 이기 때문에 5의 인덱스인 1을 저장합니다.

5는 본인 보다 큰 숫자가 없기에 -1을 저장합니다.

1은 자기보다 크면서 가장 가까운 수가 4, 2 가 있지만 4의 인덱스는 2, 2의 인덱스는 4 이므로 더 작은 인덱스인 2를 저장합니다.

나의 풀이

문제에 이미 O(n)이상의 효율성을 가진 알고리즘을 구현하여야 한다고 제시 되어있었지만, 그런 풀이를 생각해내지 못해 각 인덱스에서 좌우로 옮겨가면서 값을 구해내는 조금은 비효율적인 풀이를 제시 하였습니다.

더 좋은 풀이

비슷한 문제인 백준 사이트의 오큰수 문제를 참고하였습니다.

오큰수문제는 위의 문제가 거의 유사하며 위의 문제는 양쪽에서 큰 수를 찾는 문제지만 오큰수 문제는 오른쪽 큰 수에만 집중하고 있기 때문에 오큰수 문제를 해결한 알고리즘을 응용하여 왼큰수 알고리즘을 만들어 문제를 해결 하였습니다.

개략적 알고리즘

stack을 활용

설명을 용이하게 하기위해 오른쪽 큰수를 찾는과정을 오큰수 왼쪽 큰수를 찾는 과정을 왼큰수로 얘기하겠습니다.

  1. 위의 문제는 좌우 모두 포함된 문제 이므로 오른쪽과 왼쪽을 나누어서 해결 할 것입니다.

  2. 같은 거리에 있는 숫자라면 더 작은 인덱스를 저장할것 이기때문에 왼큰수 먼저 시행한후 오큰수를 시행 하겠습니다.

  3. stack에는 왼큰수를 저장하지 못한 숫자들을 저장할 것입니다.

  4. 숫자를 저장한 후 바로 앞 숫자와 stack의 top를 비교하여 stack의 top가 작다면 stack의 top의 왼큰수는 뒷 숫자 이므로 배열에 저장합니다.

  5. stack이 비게되거나 stack의 top의 값이 뒷 숫자보다 크거나 같아질때 까지 4번 순서를 반복합니다.

    설명 추가

    stack에는 왼쪽에서 자기 보다 큰 수를 만나지 못한 수들이 쌓이게 됩니다. 그리고 큰 수를 만나게 되면 stack에서 빠지게 되므로 자연스럽게 가장 가까이 있으면서 큰 수를 찾을 수 있게 됩니다. 하지만 그 큰 수가 한 숫자에 대한 큰 수 가 아니기에 stack top가 크거나 같은 수 이거나 stack이 비워질때까지 pop되는 모든 수에 대해 적용하여야 합니다.

  6. 각 인덱스 별로 3,4,5의 과정을 거치면 stack에 남아 있는 숫자는 더 큰 수가 존재하지 않는 수이므로 -1을 저장합니다.

  7. 오큰수도 똑같이 반대로 진행합니다.

Solution

def solution(list):
    answer = [[float('inf'), -1] for _ in range(len(list))]
    
    ## left_bigger_number
    stack = []
    for idx in range(len(list)-1, 0, -1):
        stack.append(idx)
        while stack and list[stack[-1]] < list[idx - 1]:
            new_idx = stack.pop()       
            answer[new_idx] = [abs(new_idx - (idx - 1)), idx - 1]  

    ## right_bigger_number
    stack = []
    for idx in range(len(list)-1):
        stack.append(idx)
        while stack and list[stack[-1]] < list[idx + 1]:
            new_idx = stack.pop()
            if abs(new_idx - (idx + 1)) < answer[new_idx][0]:           ## 같은 거리일 때는 인덱스가 작은것을 저장할 것
                answer[new_idx] = [abs(new_idx - (idx + 1)), idx + 1]
    
    
    print([x[1] for x in answer])

Related posts