1. 문제
크기가 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)을 공백으로 구분해 출력한다.
2. 문제 해석
각 인덱스의 오른쪽에서 해당 인덱스의 값보다 더 큰 값이 나오면 그 수를 출력하면 된다.
위 예시에서는 [3, 5, 2, 7]에서
- 첫 번째 항인 3을 기준으로 오른쪽에 있는 것 중에 3보다 큰 것 중 가장 먼저 등장하는 것은 5이다.
- 두 번째 항인 5를 기준으로 오른쪽에 있는 것 중에 5보다 큰 것 중 가장 먼저 등장하는 것은 7이다.
- 세 번째 항인 2를 기준으로 오른쪽에 있는 것 중에 2보다 큰 것 중 가장 먼저 등장하는 것은 7이다.
- 네 번째 항인 7를 기준으로 오른쪽에 원소가 없으므로 -1이다.
3. 풀이
3-1) 2중 반복문을 통한 풀이
상위 반복문을 통해 주어진 배열의 각각의 원소별로 답을 구하려고 했다.
하위 반복문에는 첫번째로 각 원소의 오른쪽에 있는 원소중 대상이 되는 원소보다 큰 경우가 나오면, 그 값을 result 배열에 담고 반복문을 나온다. 만약에 대상 원소보다 큰 값을 찾지 못하면 for else 구문으로 -1의 값을 result 배열에 추가한다.
마지막에는 result 배열의 원소들을 한 줄로 출력한다.
n = int(input())
A = list(map(int, input().split()))
result = []
for i in range(0, n):
for j in range(i+1,n):
if A[j]>A[i]:
result.append(A[j])
break
else:
result.append(-1)
for ele in result:
print(ele, end=" ")이 풀이의 시간복잡도는 O(N^2)이 N의크기는 10^6으로 최대 10^12만큼 연산해야한다. 파이썬의 초당 연산횟수는 초당 10^8~10^9이기 때문에 이 방법은 시간초과로 풀리지 않는다.
3-2) stack을 이용한 풀이
이 풀이는
1. stack에는 현재 원소를 담고 인접한 두원소끼리만 비교한다.
2. 인접한 두 원소 중 오른 쪽이 클때 stack을 pop하여 answer를 업데이트한다.
3. 그 이후에 stack의 가장위에 있는 값이 현재 오른쪽 값보다 작은 지 확인하고, 작다면 pop 한다.
3번은 stack이 비거나 왼쪽의 값이 더 큰 값을 가질때 까지 반복한다.
n = int(input())
A = list(map(int, input().split()))
answer = [-1] * n
stack = []
stack.append(0)
for i in range(1, n):
while stack and A[stack[-1]] < A[i]:
answer[stack.pop()] = A[i]
stack.append(i)
print(*answer)이 풀이의 시간복잡도 또한 O(N^2)이지만, 이미 처리된 원소에 대해서는 다시 비교하지 않기 때문에 위의 풀이보다 연산횟수가 적다.
