[알고리즘 문제 풀이][파이썬] 백준 17299번: 오등큰수

백준 17299 문제 링크: https://www.acmicpc.net/problem/17299

📑 문제 설명

수열의 크기와, 수열이 주어졌을 때 각 수열의 각 자리에 대한 오등큰수를 구하는 프로그램 작성.

오등큰수는 오큰수랑 비슷한데 수열 각 자리의 수의 크기가 아닌, 각 자리의 수가 나오는 횟수를 비교하여 현재 자리에서 오른쪽에 있는 수들중에서 현재 자리의 숫자보다 더 많이 나오는 수 중에서 가장 왼쪽에 있는 수를 의미한다.

예를 들어 1 1 2 3 4 2 1 이라는 수열이 있을 때 각 수가 나오는 횟수는 1: 3번, 2: 2번, 3: 1번, 4: 1번이다.
따라서
0번째: 오등큰수가 없음 --> -1
1번째: 오등큰수가 없음 --> -1
2번째: 1(2: 2번 < 1: 3번)
3번째: 2
4번째: 2
5번째: 1
6번째: -1

입력: 수열의 크기, 수열
출력: 오등큰수

💡 문제 해결 방법

1. 수열 각 자리수가 나오는 횟수를 저장할 변수 사용 --> cnt_list
2. 오큰수 문제를 응용하여, stack에 index를 저장

• i) 현재 자리수의 횟수 > stack에 저장된 이전 자리수의 횟수일 경우 --> 오등큰수를 얻음 + 현재 자리수 index를 stack에 push
• ii) 현재 자릿수의 횟수 < stack에 저장된 이전 자릿수의 횟수일 경우 --> 현재 자리수 index를 stack에 push

3. stack이 비어있지 않을 경우(= stack에 push된 index에 대해 오등큰수가 없음을 의미) --> -1 출력

예제
n: 7
수열: [1 1 2 3 4 2 1]

초기 설정
cnt_list: [0 3 2 1 1 0 0 0...]
stack: [0]

1. i: 1일 때
   cnt_list[수열[i]]: 3 = cnt_list[수열[stack[-1]]: 3 이므로, i: 1일 때 오등큰수가 아직 없기 때문에 현재 index를 stack에 push
   stack: [0 1]
   수열: [1 1 2 3 4 2 1]

2. i: 2일 때
   cnt_list[수열[i]]: 2 < cnt_list[수열[stack[-1]]: 1 이므로, i: 2일 때 오등큰수가 아직 없기 때문에 현재 index를 stack에 push
   stack: [0 1 2]
   수열: [1 1 2 3 4 2 1]

3. i: 3일 때
   cnt_list[수열[i]]: 1 < cnt_list[수열[stack[-1]]: 2 이므로, i: 3일 때 오등큰수가 아직 없기 때문에 현재 index를 stack에 push
   stack: [0 1 2 3]
   수열: [1 1 2 3 4 2 1]

4. i: 4일 때
   cnt_list[수열[i]]: 1 = cnt_list[수열[stack[-1]]: 2 이므로, i: 4일 때 오등큰수가 아직 없기 때문에 현재 index를 stack에 push
   stack: [0 1 2 3 4]
   수열: [1 1 2 3 4 2 1]

5. i: 5일 때
   cnt_list[수열[i]]: 2 > cnt_list[수열[stack[-1]]: 1 이므로, stack에 있는 index를 참고하여 cnt_list[수열[i]] 값이 클동안 stack pop 한 후, 현재 index를 stack에 push
   stack: [0 1 2 5]
   수열: [1 1 2 2 2 2 1]

6. i: 6일 때
   cnt_list[수열[i]]: 3 > cnt_list[수열[stack[-1]]: 2 이므로, stack에 있는 index를 참고하여 cnt_list[수열[i]] 값이 클동안 stack pop 한 후, 현재 index를 stack에 push
   stack: [0 1 6]
   수열: [1 1 1 2 2 1 1]

7. stack에 있는 index는 오등큰수가 없음을 의미하므로 -1 출력
   수열: [-1 -1 1 2 2 1 -1]

💻 코드

import sys

def NGF(n, num_list, cnt_list):
    stack = list()
    stack.append(0)
    for i in range(1, n):

        while (stack and cnt_list[num_list[i]] > cnt_list[num_list[stack[len(stack) - 1]]]):
            num_list[stack[len(stack) - 1]] = num_list[i]
            stack.pop()
        stack.append(i)

    if (len(stack) != 0):
        for i in range(len(stack)):
            num_list[stack[i]] = -1

    return num_list

if __name__ == '__main__':

    n = int(sys.stdin.readline())
    num_list = [int(i) for i in (sys.stdin.readline().split())]
    cnt_list = [0 for i in range(0, 1000001)]

    for i in range(n):
        cnt_list[num_list[i]] += 1

    result = NGF(n, num_list, cnt_list)
    for i in range(n):
        print(result[i], end = " ")

💟 추가적으로 알게 된 점

• 문제에서 주어진 제한은 괜히 있는 것이 아님... 제한을 확인하고 초기 배열의 크기 정해주기