백준 22.04.07. 17298번 - 오큰수

---

↓ 틀린 코드

import sys
input = sys.stdin.readline

n = int(input())

stack = list(map(int, input().split()))

result = [-1 for i in range(n)]

for i in range(n):
    for j in range(i, n):
        if stack[j] > stack[i]:
            result[i] = stack[j]
            break

print(*result)

시간초과입니다.

---

n = int(input())

# 주어진 예제 리스트로 만들기
arr = list(map(int, input().split()))

# NGE(n)에 요구되는 n저장 (인덱스 저장)
stack = []

# 조건에 충족하지 않았을 때를 위해 기본값을 -1로 지정
result = [-1 for i in range(n)]

# NGE(0)부터 구해야 하므로 미리 할당
stack.append(0)

for i in range(1, n):

    # stack의 유무를 판단하는 이유는 stack.pop()을 하면 stack의 길이가 0이 될 가능성이 존재하기 때문
    while stack and arr[stack[-1]] < arr[i]:
        # stack에 저장된 인덱스들을 사용하여 result의 해당 요소를 조건에 부합한 arr[i]로 변경
        result[stack.pop()] = arr[i]

    # 다음에 알아볼 NGE(i)를 위해 인덱스를 스택에 저장
    stack.append(i)

# 리스트의 괄호와 반점들을 제거하여 출력해줌
print(*result)

기존 코드처럼 반복문을 조건없이 실행되게 했더니 시간초과가 나옵니다.

아마 for문 안의 반복문이 무조건 실행되게 되어있어서 나온 듯 합니다.

위와 같은 코드로 고쳐 필요할 때만 반복을 실행하니 정답처리 되었습니다.

 

• 위 코드에서 스택은 NGE(n)에 사용되는 n인 인덱스를 저장하는데 쓰였습니다.
  • 만약 stack에 i가 쌓인다면 그 의미는 아직 오큰수가 존재하지 않는다는 뜻입니다.
  • 따라서 stack의 길이가 2만큼 쌓였을 때 while문 조건에 부합하는 arr[i]이 나왔다면 stack에 저장된 인덱스들의 오큰수는 arr[i]이 됩니다.
• while문을 조건이 맞을 때만 실행되도록 설정해줍니다.
  • stack이 비어있는지 여부를 조건에 추가해주어야합니다.
  • while문의 내용에서 stack.pop()을 하면 스택이 비어버려 오류를 출력할 수도 있습니다.
• 스택에 오큰수를 찾을 인덱스를 추가해줍니다.
  • 스택에 인덱스를 추가하는 부분이 while문보다 늦게 실행되는 이유는 미리 할당해둔 stack[0]을 이용한 NGE(0)을 먼저 확인해야 하기 때문입니다.
• print의 매개변수로 리스트를 줄 때 *을 달아주면 리스트의 괄호들과 반점들이 모두 제거된 채로 출력됩니다.