[백준_스택2] 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이다.

 

 

 

 

입력

 

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)

이 주어진다.

 

출력

 

총 N개의 수 NGE(1), NGE(2), ..., NGE(N)을 공백으로 구분해 출력한다.

 

 

 

예시 입력

 

4
3 5 2 7

 

예시 출력

 

5 7 7 -1

 

 

 

 

풀이

 

아래 단계별로 문제를 해결하는 방법을 설명합니다.

1. 입력 처리
   - 먼저, N을 입력으로 받습니다. N은 수열 A의 크기를 나타냅니다.
   - 다음으로, 수열 A를 공백으로 구분된 숫자로 입력받고 리스트로 저장합니다.

2. 스택과 결과 리스트 초기화
   - 스택(stack)과 결과를 저장할 리스트(result)를 초기화합니다.
   - 결과 리스트(result)는 모든 값을 -1로 초기화합니다.

3. 오큰수 찾기
   - 수열 A를 왼쪽에서 오른쪽으로 순회하면서 각 원소에 대해 오큰수를 찾습니다.
   - 인덱스 i를 사용하여 수열 A를 순회합니다.

4. 스택 활용
    - 스택(stack)을 사용하여 오큰수를 찾습니다. 스택은 현재까지 탐색한 원소의 인덱스를 저장하는 역할을 합니다.
    - 스택이 비어있지 않고, 스택의 가장 위(마지막) 원소가 현재 원소보다 작을 때까지 다음을 반복합니다.
    - 스택의 가장 위(마지막) 원소를 팝하고, 그 원소의 오큰수를 현재 원소로 설정합니다. 결과 리스트(result)에 오큰수를 저장합니다.
    - 현재 원소의 인덱스를 스택에 추가합니다.

5. 결과 출력
   - 모든 원소에 대한 오큰수를 찾았으므로, 결과 리스트(result)를 공백으로 구분하여 출력합니다.

 

예를 들어, 입력이 N = 4,  A  = [3, 5, 2, 7]인 경우, 코드는 다음과 같이 동작합니다.
- N을 입력받고, 수열 A를 리스트로 저장합니다.
- 스택과 결과 리스트를 초기화합니다.
- 수열 A를 순회하며 각 원소에 대한 오큰수를 찾습니다.
- 결과는  5 7 7 -로 출력됩니다. (NGE(1) = 5, NGE(2) = 7, NGE(3) = 7, NGE(4) = -1)

 

 

내 풀이

 

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


#1 ~ N
for i in range(len(stack)):
    count = 0
    for j in stack[i+1:]:
        if stack[i] < j:
            print(j, end=" ")
            count += 1
            break
    if count == 0:
        print("-1", end=' ')

 

답은 나오지만 시간 복잡도 O(n^2)라서 시간 초과...

 

스택을 활용해야한다.

 

 

스택을 활용한 정답 풀이

 

# N을 입력으로 받음 (수열 A의 크기)
N = int(input())

# 수열 A를 공백으로 구분된 숫자들로 입력받아 리스트로 저장
A = list(map(int, input().split()))

# 스택으로 활용할 리스트를 초기화
stack = []

# 결과를 저장할 리스트를 초기화하고, 모든 값들을 -1로 설정
result = [-1] * N

# 수열 A의 각 원소에 대해 오큰수를 찾는 반복문
for i in range(N):
    # 스택이 비어있지 않고, 스택의 가장 위(마지막) 원소가 현재 원소보다 작을 경우
    while stack and A[stack[-1]] < A[i]:
        # 스택의 가장 위(마지막) 원소를 팝하고, 그 원소의 오큰수를 현재 원소로 설정
        result[stack.pop()] = A[i]
    
    # 현재 원소의 인덱스를 스택에 추가
    stack.append(i)

# 결과 리스트를 공백으로 구분하여 출력
print(*result)