[백준] 17299번 : 오등큰수 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트

 

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

 

1. 문제 설명

반응형

2. 풀이과정

해당 문제는 이전의 17298번 : 오큰수 문제와 유사한 문제이다.

이전의 오큰수 문제는 단순히 오른쪽에 있는 값들 중 큰 값에서 가장 왼쪽에 있는 값을 구하는 문제였지만,

해당 오등큰수 문제는 거기에 숫자의 개수도 커야 하는 조건이 추가되었다.

 

N의 최대 크기가 1,000,000이므로 반복문을 사용해 오등큰수를 찾으면 제한 시간을 초과하게 된다.

하여 스택을 활용해 문제를 해결한다.

오등큰수가 존재하지 않는 수는 -1을 출력하므로 오등큰수를 저장할 리스트를 -1로 초기화한다.

오등큰수는 해당 수 다음 수들에서 찾아야 하므로 숫자들의 개별 값이 아닌 인덱스를 저장할 스택을 생성한다.

스택에 원소가 있고 스택의 제일 마지막 인덱스 위치의 값의 개수가 현재 인덱스 위치의 값의 개수보다 작으면(오른쪽에 있으면서 해당 값보다 큰 수 중 가장 왼쪽에 있는 수 + 숫자의 개수가 큰 수) 스택의 제일 마지막 원소인 인덱스 위치에 해당하는 값을 오등큰수 리스트에서 현재 인덱스 위치에 저장한다.

이후 현재 인덱스를 스택의 제일 마지막 원소로 추가한다.

해당 과정을 제일 마지막 인덱스까지 반복하며 오등큰수를 구하고 구한 오등큰수를 출력한다.

 

1. sys.stdin.readline() 함수를 사용하기 위해 sys 모듈을 불러온다. import sys
2. 전체 수에서 각 숫자가 몇 번 나왔는지 세어주기 위해 Counter 함수를 사용한다. from collections import Counter
3. 전체 숫자의 개수를 입력받는다. N = int(sys.stdin.readline())
4. 각 숫자를 입력받아 리스트로 저장한다. A = list(map(int, sys.stdin.readline().split()))
5. 전체 수에서 각 숫자가 몇 번 나왔는지 세어 저장한다. F = Counter(A)
6. 최종 결과인 오등큰수를 저장할 리스트를 생성하고 -1로 초기화한다. NGF = [-1] * N
7. 오등큰수를 찾을 때 활용할 스택 자료구조를 생성하고 초기 위치인 0을 저장한다. stack = list()
8. 각 숫자의 인덱스를 가져오며 for i in range(N)
   1. 스택에 원소가 있고 스택의 제일 마지막 인덱스 위치의 값의 개수가 현재 인덱스 위치의 값의 개수보다 작으면 스택의 제일 마지막 원소인 인덱스 위치에 해당하는 값을 오등큰수 리스트에서 현재 인덱스 위치에 저장하고 이를 반복한다. while (stack and F[A[stack[-1]]] < F[A[i]]): NGF[stack.pop()] = A[i]
   2. 현재 인덱스를 스택의 제일 마지막 원소로 추가한다. stack.append(i)
9. 최종적으로 모두 구한 오등큰수를 공백으로 구분해 출력한다. print(*NGF)

728x90

3. 소스코드

import sys
from collections import Counter

N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))

F = Counter(A)

NGF = [-1] * N
stack = list()
for i in range(N):
    while (stack and F[A[stack[-1]]] < F[A[i]]):
        NGF[stack.pop()] = A[i]

    stack.append(i)

print(*NGF)