백준 17298 오큰수 파이썬 풀이 시간초과 해결

백준 17298 오큰수 파이썬 풀이

문제

크기가 N인 수열 A = A1, A2, ..., AN이 있다. 수열의 각 원소 Ai에 대해서 오큰수 NGE(i)를 구하려고 한다. Ai의 오큰수는 오른쪽에 있으면서 Ai보다 큰 수 중에서 가장 왼쪽에 있는 수를 의미한다. 그러한 수가 없는 경우에 오큰수는 -1이다.

예를 들어, A = [3, 5, 2, 7]인 경우 NGE(1) = 5, NGE(2) = 7, NGE(3) = 7, NGE(4) = -1이다. A = [9, 5, 4, 8]인 경우에는 NGE(1) = -1, NGE(2) = 8, NGE(3) = 8, NGE(4) = -1이다.

 

---

정답코드

#오큰수
N = int(input())
arr = list(map(int,input().split()))
result = [-1] * N
stack = [0]

for i in range(1,N):
    while stack and arr[stack[-1]] < arr[i]:
        result[stack.pop()] = arr[i]
    stack.append(i)

print(*result)

 시간복잡도 O(N^2) 였던 for 문 X 2 와 달리, for 문안에 스택이 들어있는 것은 시간복잡도가 O(N)이다.

 

 

 

코드 진행 순서

입력 예시 5, 3 8 2 7 4

 핵심코드

for i in range(1,N):
    while stack and arr[stack[-1]] < arr[i]:
        result[stack.pop()] = arr[i]
    stack.append(i)

while stack 이라는 조건과 조건을 만족할 경우 stack.pop()을 통해 조건을 만족하는 경우 stack이 줄도록 설계되어 있다.

 

Q)스택이 쌓이면서 왼쪽에서 오른쪽 인덱스로 체크하는 게 아니라, 오른쪽 인덱스에서 왼쪽으로 반대로 체크하게 됩니다.(후입선출 구조) 

그렇다면 예를들어, while 문의 조건을 stack[-1]이 만족한다고 할 때, 조건문이 한바퀴 돌고도 조건을 만족한다고 가정한 경우, 그 때 answer[stack[-2]] = arr[i]를 넣을 수 있다고 확신할 수 있나요??

 

-> 네

왜냐하면 stack이 쌓였다는 뜻은 arr[stack[-1] < arr[i] 비교 조건에 의해 arr의 직전 index 보다 값이 더 작다는 것을 의미합니다. 따라서 비교를 해야되고 그래서 while문이 한번 더 돌게 설계가 된 것입니다. 이떄 그 while 문에서의 조건 또한 만족한다면, 오른쪽에서 큰 수 중 가장 왼쪽에 있는 수가 되는 것이므로 확신 할 수 있습니다.

예시(7 5 8 1) 인 경우 answer = [8 8 -1 -1]

 

Q) 이 문제가 어려운 이유와 스택을 활용할 수 있는 이유??

-> 이문제가 어려운 이유는 단순한듯 보이지만, 시간 복잡도 와 자료구조를 활용해야하는 문제이기 때문이다.

forX2번으로 시간복잡도O(N^2)이 되는 풀이를 스택 자료구조를 활용해 시간복잡도 O(N)으로 줄여 문제를 해결해야 한다. 아울러 스택에 적응하지 못한  사람의 경우 이 문제에 스택을 어떻게 적용해야할지 감을 잡기 무척이나 어렵다. ( 나의 경우)

그렇다면 스택 자료구조를 사용할 수 있는 이유는 무엇인가?

1.왼쪽에서 오른쪽 혹은 오른쪽에서 왼쪽으로 순차적으로 방향성을 갖고 있다.

 

2. 조건을 만족하지 않으면 "저장"되었다가 나중에라도 체크해야한다.

 -> 스택의 구조는 "쌓인다"라는 특징을 가진다.

 

풀이과정

 

시간초과 코드

#오큰수

N = int(input())
answer = []
su_yeol = list(map(int,input().split()))

for i in range(len(su_yeol)):
    flag = 0
    for j in range(len(su_yeol)):
        #중복제거
        if(i<j):
            if(su_yeol[i] < su_yeol[j]):
                answer.append(su_yeol[j])
                flag = 1
                break
            elif(j == len(su_yeol) - 1 and flag == 0):
                answer.append(-1)
answer.append(-1)

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

 

for 문을 2번사용하였는데, 이 때문에 시간초과가 났다.

for 문 한번에 시간복잡도는 O(N) 인데, for 문을 두번 연속 사용하였으니 시간복잡도가 O(N^2)인 코드이다. 따라서 이러한 문제 때문에 시간초과가 난 것이다.

 

 정답코드를 참고했음에도 불구하고, stack을 활용하는 이유가 무엇인지 헷갈렸고, while 문과 stack을 활용한 설계가 익숙지 않아 , 꽤 많은 시간 고민을 하였다.

 

배운점 && 공부방향

1. 자료구조를 사용해 시간복잡도를 최소화 하자.

 ->for 문 X 2 , for 문 X stack 의 시간복잡도 비교

 

2. Stack은 어떤 문제 유형에서 활용할 수 있는가? 에 대해 적응할 필요가 있다.

-> 문제를 풀면서 처음에 stack을 쓸 수 있을지 생각 자체가 나지 않았음.

 

3. 조건을 만족하지 않는 경우를 default 값으로 하는 풀이
result = [-1] * N