문제 출처: https://www.acmicpc.net/problem/17298
1. 결과
메모리 153484KB, 시간 1212ms
2. 풀이
처음에는 이 문제를 이중 for문을 통해 각 자리의 숫자(i번째)마다 이후의 숫자(i+1번째부터 n번째까지)를 탐색하며 큰 수가 있다면 이를 저장하며 break, 없다면 끝까지 탐색 후 -1을 추가하게 되는 방법으로 작성했다. 이 경우는 답은 도출이 되었지만 시간 복잡도가 크게(O(N^2)) 발생되었다. 다른 풀이로는 먼저 첫 숫자에 대해 나머지 숫자를 탐색하며 첫 숫자보다 큰 숫자가 있다면 해당 숫자를 스택에 저장하고, 두 번째 숫자부터 모두 해당 숫자보다 작다면 스택의 마지막 숫자를 그대로 또 추가하는 방식을 적용해봤다. 만약 스택의 마지막 숫자보다 현재 숫자가 크다면 다시 현재 숫자에 대해 나머지 숫자를 탐색하여 같은 경우를 반복했다. 즉, 처음에 선택한 숫자가 이후의 숫자보다 웬만하면 크고, 해당 숫자보다 큰 숫자라면 그 사이의 숫자에 대해서도 오큰수일 것이라고 생각했다. 하지만 이 방식은 6 3 5 2 7과 같은 경우에 오답이 발생한다. 답은 7 5 7 7 -1이지만, 이 방식으로는 7 7 7 7 -1이 나오는 것이다.
그래서 다른 풀이를 고민하던 중, 숫자 자체가 아니라 인덱스를 스택으로 저장해보는 방식을 떠올렸다. N이 5이고, 주어지는 순열이 6 3 5 2 7인 경우를 예시로 들어서 풀이 방식을 정리하면 아래와 같다.
1. 인덱스를 저장하는 스택([0])과 결과를 저장하는 리스트([-1] * N)를 아래와 같이 생성한다.
2. 스택에 원소가 남아있고, 현재 숫자가 스택의 마지막 원소([-1])를 인덱스로 갖는 숫자보다 큰 경우스택의 마지막 원소를 인덱스로 갖는 숫자가 현재 숫자보다 크지 않을 때까지 pop하고, 결과 리스트의 pop한 인덱스에 해당하는 원소를 현재 숫자로 저장한다.3. 2번 과정이 끝났거나, 스택이 비어있을 경우에는 현재 숫자의 인덱스를 그냥 스택에 저장한다.- 이미 스택에 초기값으로 저장된 0 이후의 첫 인덱스 1에 해당하는 숫자 3은 스택의 마지막 인덱스(0)에 해당하는 숫자 6보다 작기 때문에 2번 과정 없이 바로 인덱스를 스택에 저장
- 그 다음 인덱스 2에 해당하는 숫자 5는 스택의 마지막 인덱스(1)에 해당하는 숫자 3보다 크기 때문에 인덱스 스택에서 1을 pop. 이후 결과 리스트(result[1])에서 인덱스 1에 해당하는 숫자는 -1에서 5로 다시 할당.
- 다음 숫자 2는 스택의 마지막 인덱스(2)에 해당하는 숫자 5보다 작으므로 스택에 저장
- 마지막 숫자 7에 대해 스택에 저장된 마지막 인덱스(3)에 해당하는 숫자 2보다 크므로 인덱스 스택에서 3을 pop하고 결과 리스트의 result[3] 에 7을 할당. 남은 인덱스 스택의 2, 0도 같은 과정 반복. 이후 for문 종료
이렇게 이 문제는 해결할 수 있었고, 이를 코드로 작성한 것은 아래의 코드이다.
이 문제는 다른 간단했던 스택 문제에 비해 비교적으로 떠올리기 어려운 문제였다. 보통의 스택 문제는 자료나 값 자체를 스택에 저장하고, 이를 pop하는 방식으로 조건에 따라 다시 출력하며 적은 공간 복잡도와 적은 시간 복잡도를 갖도록 구현하는 문제였는데, 이 문제는 값이 아닌 인덱스를 스택에 저장한다는 것을 떠올려야 문제 채점 조건에 맞는 복잡도를 가질 수 있었다. 이렇게 구현하면 이중 for문은 필요도 없을뿐더러 for문을 한 번 돌면서, 스택에서도 최악의 경우에야 순열의 숫자 개수 N에 해당하는 출력만 존재할 뿐이기 때문이다. 즉, O(2*N) = O(N)에 해당하는 코드로 구현할 수 있었다. 쉽다고 생각했던 자료구조도 이렇게 생각보다 쉽지 않은 문제로 구현할 수 있다는 점과 값이 아닌 인덱스 자체를 저장한다는 방법 등 문제를 해결할 수 있는 창의적인 생각을 기르는 것이 중요하다고 느낀 문제였다.
import sys
def main():
N = int(sys.stdin.readline())
nums = list(map(int, sys.stdin.readline().split()))
idxStack = [0]
result = [-1] * N
for i in range(1, N):
while idxStack and nums[i] > nums[idxStack[-1]]:
idx = idxStack.pop()
result[idx] = nums[i]
idxStack.append(i)
return result
if __name__ == "__main__":
print(*main())
'지극히 개인적인 공부 노트 > 알고리즘(Algorithm)' 카테고리의 다른 글
[Algorithm] 백준 2667번: 단지 번호 붙이기 | DFS, BFS 비교 (0) | 2021.09.18 |
---|---|
[Algorithm] 백준 5430번: AC | 덱 응용 (0) | 2021.09.18 |
[Algorithm] 백준 6549번: 히스토그램에서 가장 큰 직사각형 | 분할 정복 응용 (0) | 2021.09.10 |
[Algorithm] 백준 18258번: 큐 2 | 덱(Deque) 이용 (0) | 2021.09.08 |
[Algorithm] 백준 10845번: 큐 | 연결 리스트와 큐를 클래스로 구현 (0) | 2021.09.08 |