[백준] 17299: 오등큰수 (+ 오큰수 문제에 대한 잡담)

안녕하세요. 이번 문제는 백준의 17299 오등큰수 문제입니다.

골드 3단계의 문제입니다. 

 

이 문제를 풀기 이전에 17298의 오큰수를 먼저 풀었습니다.

오큰수를 푸는 방법을 거의 활용해서 풀었습니다.

 

오큰수 같은 경우 첫 골드 문제인지라 어렵기도 했고 시간 복잡도에서 계속 실패가 나왔습니다. 그래서 문제의 풀이를 찾아보며 문제를 풀었는데요.

찾아보고 나서 느낀건.. 정답 코드가 어려운 것은 아니었지만 그 알고리즘(스택 활용)을 문제만 보고 어떻게 도출해낼 것인지를 판단하는 건 쉽지 않더라구요. (많이 풀어보는 것이 능사겠지만요)

 

역시 문제를 잘 읽어보고, 문제에서 요구하는 자료구조를 잘 읽어낼 수 있는 게 중요한 부분인 것 같습니다.

그리고 입력 데이터들의 크기와 시간 제한을 보고, 통과할 수 있는 대략적인 시간 복잡도를 파악하는 것도 중요할 것 같습니다. 

 

오큰수-오등큰수 모두 아래와 같은 특징이 있는데요.

 

- 이미 사용된 이전 수들은 뒤 수에 의미를 주지 않고 (카운트를 셀 때 제외..)

- 앞에서부터 오큰수를 찾아낸다고 했을때, 만약 오큰수를 찾아내지 못하고 다음 수로 넘어가게 되면 오큰수를 찾는 것은 뒤 수 부터라는 것입니다. (먼저 들어간 것이 나중에 나옴)

 

이러한 요소들이 stack을 사용한다는 힌트가 될 것 같습니다. 아직 많이 어렵습니다.

 

알고리즘 캔버스

아이디어

브레인스토밍

• 오등큰수
  • NGF(i)
  • 수열의 등장 횟수가 나보다 크고, 오른쪽에 존재하며, 그중 가장 왼쪽에 있는 수
• 이건 이전 데이터들도 누적이 되어야 하는 문제. (stack만으로는 풀수 없음. 다른 내용도 활용 필요.)
  • 일단 스택을 사용해야 함.

아이디어

• 시간 복잡도를 n log n이나 n 만큼으로 만들어야 함 (아마 n)

1. 객체를 만들어서 {1: 0, 2: 0 } 등으로 등장 횟수를 저장할 수 있게 한다.
   1. 그리고 등장 횟수를 for문으로 구한다.
2. 오큰수를 구하는 방식과 동일하게 구한다.
   1. (result 배열을 -1로 초기화) 오큰수가 없다는 전제로 진행한다.
   2. stack에 아직 오등큰수를 못구한 수가 있다면
      1. stack에 마지막 요소의 count가 현재 요소의 count보다 작다면,
         1. 현재 스택의 마지막 요소의 오등큰수는 내가 된다.
   3. 그리고 현재 요소의 인덱스를 스택에 넣는다.

시간 복잡도 (Big-O)

• O(N)

Code

import sys
n=int(sys.stdin.readline().rstrip())
a=list(map(int, sys.stdin.readline().rstrip().split()))
count = {}
stack = [0]
result = [-1] * n

for i in range(n):
	if a[i] in count:
		count[a[i]] += 1
	else:
		count[a[i]] = 1

for i in range(1,n):
	while stack and count[a[stack[-1]]] < count[a[i]]:
		result[stack.pop()] = a[i]
	
	stack.append(i)
	
print(*result)