[백준] 17298 오큰수

문제 링크

정답 코드

n = int(input())
lst = list(map(int, input().split()))

answer = [-1] * n
stack =[]

for i in range(n):
    while stack and lst[stack[-1]] < lst[i]:
        answer[stack.pop()] = lst[i]
    stack.append(i)

print(' '.join(map(str, answer)))

시간초과 코드 O(n^2)

# 시간초과 코드
import sys
_ = sys.stdin.readline()
lst = list(map(int, sys.stdin.readline().split()))

answer = []

for index, value in enumerate(lst[:-1]):
    compare_value = float('inf')
    for indent_index, indent_value in enumerate(lst[index+1:]):
        # 지금 값 보다 들여쓰기의 값이 크고, 그 중 제일 작은 값이 존재한다면
        if value < indent_value and compare_value> indent_value:
            # value보다 큰 수 중 가장 작은 값을 Compare value에 넣는다.
            compare_value = indent_value
    if compare_value == float('inf'):
        answer.append(-1)
    else:
        answer.append(compare_value)

print(' '.join(map(str, answer)) +' -1')

문제 설명

해당 문제는 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. 라는 설명에 의해 O(N) 으로 문제를 풀이해야 한다.

풀이 방법으로는 스택을 활용하여 인덱스에 접근하는 방법으로 문제를 해결할 수 있다.

결국 문제를 풀지 못하여 다른 분들의 문제 풀이를 보며 방법을 이해할 수 있었기에 다른 사람들에게 본인이 이해한 방법을 설명하며 코드를 이해하고 추 후 다시 풀어볼 계획이다.

문제 풀이

1번부터 5번의 코드를 실행하게 되면 위와 같은 상태로 초기화가 된다.

이 문제를 해결할 수 있는 핵심 코드는 8번 코드이다.
8번 코드의 역할은

• stack 이 존재하며, 현재 조회하는 값보다 직전에 순회하던 값이 작다면
• stack에 쌓인 마지막 인덱스에 해당하는 answer 값을 현재 순회하는 값으로 변경한다.

의 구조를 가지고 있다.
스택에 쌓여야 answer에 접근할 수 있기 때문에 반복문이 시작하는 i 가 0인 경우에는 반드시 스택에 값이 들어간다.

해당 경우를 i값 기준에서 본다면

0. i는 스택에 추가된다.

1. 9보다 5가 크므로, 8번 코드는 동작하지 않는다. i가 스택에 추가된다.
2. 5보다 4가 크므로, 8번 코드는 동작하지 않는다. i가 스택에 추가된다.
   
3. 4는 8보다 작으로 8번 코드의 조건이 충족된다. answer의 2번째 인덱스는 8로 변경된다.
   3-1. 5는 8보다 작으므로 8번 코드의 조건이 충족된다. answer의 1번째 인덱스는 8로 변경된다.
   
   3-2. 9는 8보다 크므로 8번 코드는 동작하지 않는다.

해당 상태를 마지막으로 코드는 종료되며 print의 출력값이 실행된다.