[BOJ] 17299 오등큰수

https://www.acmicpc.net/problem/17299

 

 

한 수열이 주어졌을 때, 각 원소에 대하여, 해당 원소보다 등장빈도가 높은 숫자 중 오른쪽 방향으로 가장 가까이에 있는 숫자를 구하는 문제.

 

 

1/ 조건

1) 수열의 크기는 1 이상 100만 이하다.

2) 각 원소의 크기는 1 이상 100만 이하다.

3) 시간 제한은 1초, 메모리 제한은 512MB.

 

 

2/ 설계

일단 메모리가 충분하므로 100만+1의 크기를 갖는 배열을 만들어서 등장빈도를 기록해야겠다고 생각했다. 그렇게 해야 O(1)으로 각 등장빈도를 호출할 수 있을 테니.

가장 간단한 방식은 각 원소보다 큰 인덱스를 탐색하며 등장빈도가 높은 원소를 만나면 break를 하는 것인데, 최악의 경우(예를 들어 모든 원소가 한 번만 등장할 경우) 시간 제한을 쉽게 넘어간다. 다른 방식이 필요했다.

직감적으로는 스택을 써야 한다고 느꼈다. 그런데 어떻게 스택을 쌓아나가고 어떻게 호출할지 감이 잘 안 왔다. 나는 계속해서 각 원소의 이후에 오는 원소들(오등큰수 후보)을 어떻게 스택에 쌓을 것인가에 대해 생각했는데, 해답은 스택에 기존의 원소를 쌓고, 스택과 비교하는 주체를 오등큰수 후보로 만드는 것이었다.

 

 

3/ 구현

n = int(input())
seq = list(map(int, input().split()))

freq = [0]*1000001
for num in seq:
    freq[num] += 1

stack = []
result = [-1]*n
for i in range(n):
    while stack and freq[seq[i]] > freq[seq[stack[-1]]]:
        result[stack.pop()] = seq[i]
    stack.append(i)

print(*result)

 

 

4/ 결과

야호!

 

 

5/ 후기

1) 이 문제에서 비교해야 하는 대상은 두 개다. 특정 원소와, 그 원소에 해당하는 오등큰수(의 후보). 내가 풀었던 문제들은 거의 오등큰수의 후보에 해당하는 대상을 스택에 집어넣곤 했고, 그래서인지 스택에 '특정 원소'를 담는다는 발상을 하지 못했다. 어떠한 경험칙을 갖고 있는 건 좋지만 그걸 필요할 때 곧바로 해체할 수 있어야 한다. 그러려면 거리두기를 통한 메타인지가 필요하고, 동시에 명시적인 정의와 암묵적인 전제에 대해서도 잘 알아야 한다. 물론 늘 말은 쉽다.

 

2) 취업에 성공했다. 당장 내가 맡게 될 일이 뭔지 알 수 없어서 뭘 붙잡고 공부를 하기보다 두뇌 트레이닝(ㅋㅋ) 용으로 하던 1일 1문제 풀기만 반복하는 중이다. 책도 읽긴 읽는데 지식이 계속 어딘가로 흘러나가는 기분이 들더라. 그래서 문제를 푸는 순간에라도 좀 더 도전적이려고 하지만 쉽지 않다. 매일 문제를 하나 풀어야 한다는 생각에 스마트폰으로 해결할 수 있는 문제를 풀기도 했다. 살면서 이렇게 뭔가를 연속으로 해본 적이 없기 때문에 나름 뿌듯하면서도 이렇게 연속에 집착하는 게 맞나 싶기도 하다. 지금은 집착하기로 했다. 큰 부담도 아니고, 내 인식 깊은 곳까지 연속성과 친해지고 싶어서.