뒤에 있는 큰 수 찾기

NJW·2023년 4월 28일

코테

목록 보기

155/170

문제 설명

해당 숫자보다 뒤에 있는 수 중 크면서 제일 가까운 수를 정답 배열에 넣어 반환하는 문제이다.

문제 풀이

첫 번째 접근

너무나 간단하게 2차원 반복문을 생각했다. 하나 잡아서 뒤에 거 계속 돌리면 되지 않겠는가? 찾으면 break해주고. 시간 초과가 걸릴 걸 알면서도 그냥 해봤다...

당연히 시간 초과!

두 번째 접근

그렇다면 시간 초과가 나지 않게 하기 위해서 어떻게 해야 할까? 고민해봤지만, 답이 나오지 않아서 다른 사람의 풀이를 참고했다.

내가 참고한 풀이는 스택을 이용했는데, 스택이 FIFO이라는 점을 이용한 것이다.

배열을 reversed로 돌려서 뒤에서 부터 시작한다. 왜냐하면 문제에서 해당 값의 뒤쪽에 있는 숫자를 찾으라고 했으니 뒤에서부터 최대값을 찾는 방식이다.
만일 뒤에 있는 최댓값이 존재하면 해당 값이 존재할 때까지 while문을 돌려준다. 그래서 현재 값과 스택의 제일 첫 번째의 최대값을 비교해서 만일 현재 값이 더 작다면 해당 스택이 top 값이 현재 값의 제일 가까이있으면서 제일 큰 값이 되는 것이기에 answer에 append를 한다. 그리고 최대값 스택에 해당 값을 넣어준다. 만일 top값이 더 작다면 해당 값의 뒤에 있는 값 중 더 작은 값이 되므로 pop를 한다.
위의 while문을 다 돌렸는데 last의 값이 0이라면 해당 값보다 뒤에 있는 수 중 최댓값이 존재하지 않는다는 의미이므로 last에 해당 값을 넣어주고 해당 값 위치에는 -1을 넣어주면 된다.

코드

Python

def solution(numbers):
    last = []
    answer = []
    
    for number in reversed(numbers):
        
        # 만일 뒤에 최대값이 존재하면
        if len(last) > 0:            
            while len(last) > 0:
                # 만일 맨 마지막 최대값이 현재 값보다 크면
                if number < last[-1]:
                    answer.append(last[-1])
                    last.append(number)
                    break
                # 만일 맨 마지막 최대값이 현재 값보다 작으면
                else:
                    last.pop()
        
        # 만일 뒤에 최대값이 존재하지 않으면
        # 여기서 else를 쓰면 안 되는 것이, 만일 위의 if를 다 돌았는데 최댓값이 없을 때도 검사해야 하기 때문이다.
        if len(last) == 0:
            last.append(number)
            answer.append(-1)
    

    return answer[::-1]