스파르탄 365 2주차 (3) 오큰수

2주차

백준 17298번 오큰수

문제링크 : https://www.acmicpc.net/problem/17298

💡 풀이 전 계획과 생각

1. 이중 for문을 통해 순차 탐색을 하면 되겠다

💡 풀이

틀린 코드

import sys
arr_NGE = list()

def NGE(arr):
    for i in range(len(arr)):
        std_i = arr[i]
        for j in range(i, len(arr)):
            if std_i < arr[j]:
                arr_NGE.append(arr[j])
                break
            elif j == (len(arr)-1):
                arr_NGE.append(-1)

N = int(sys.stdin.readline())
arr_A = list(map(int ,sys.stdin.readline().split()))
# for _ in range(N):
NGE(arr_A)
for a in arr_NGE:
    print(a, end=" ") 

맞은 코드

import sys
N = int(sys.stdin.readline())
nums = list(map(int, sys.stdin.readline().split()))

stck = []
# 깨달은 부분 : 오큰수를 찾지 못하는 예외 케이슬 둘 것이 아니라,
# 미리 -1 로 다 저장해놓으면 그것이 바로 예외 처리
result = [-1 for _ in range(N)]

stck.append(0)
i = 1

# 배운 부분: 스택에 값이 있고 while stck,
# 인덱스도 사용하려면 and 명령어를 통해 i < N을 써주면 된다.
while stck and i < N:
    # 이해 안가는 부분: 왜 인덱스로 해야하는지 이해가 안감 -_-
    while stck and nums[stck[-1]] < nums[i]:
        print('stck[-1] is ', stck[-1])
        result[stck[-1]] = nums[i]
        stck.pop()

    stck.append(i)
    i += 1

for i in result:
    print(i, end=" ")

🧐 막혔던 점과 고민

1. 시간초과

이중 for문을 통해 순차탐색을 하니 시간초과가 났다.
그래서 스택을 써야하나? 싶은 마음에 pop()함수를 이용했다.

2. pop을 쓰니 반복이 불가능

pop()을 쓰니 기존 원소가 사라져 첫 원소 이후로 반복이 불가능했다.

👏🏻 알게된 개념과 소감

• 배운 부분: 스택에 값이 있고 while stck,
  인덱스도 사용하려면 and 명령어를 통해 i < N을 써주면 된다.

while stck and i < N:

• 깨달은 부분 : 오큰수를 찾지 못하는 예외 케이슬 둘 것이 아니라,
  미리 -1 로 다 저장해놓으면 그것이 바로 예외 처리

result = [-1 for _ in range(N)]

❓ 아직 모르겠는 부분

이해 안가는 부분: 왜 인덱스로 해야하는지 이해가 안감 -_-

• 금요일 (혹은 토요일) 해설강의를 듣고 해결해야 할 것 같다.