오등큰수

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초	512 MB	12276	5501	4227	44.169%

문제

크기가 N인 수열 A = A1, A2, ..., AN이 있다. 수열의 각 원소 Ai에 대해서 오등큰수 NGF(i)를 구하려고 한다.

Ai가 수열 A에서 등장한 횟수를 F(Ai)라고 했을 때, Ai의 오등큰수는 오른쪽에 있으면서 수열 A에서 등장한 횟수가 F(Ai)보다 큰 수 중에서 가장 왼쪽에 있는 수를 의미한다. 그러한 수가 없는 경우에 오등큰수는 -1이다.

예를 들어, A = [1, 1, 2, 3, 4, 2, 1]인 경우 F(1) = 3, F(2) = 2, F(3) = 1, F(4) = 1이다. A1의 오른쪽에 있으면서 등장한 횟수가 3보다 큰 수는 없기 때문에, NGF(1) = -1이다. A3의 경우에는 A7이 오른쪽에 있으면서 F(A3=2) < F(A7=1) 이기 때문에, NGF(3) = 1이다. NGF(4) = 2, NGF(5) = 2, NGF(6) = 1 이다.

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다.

출력

총 N개의 수 NGF(1), NGF(2), ..., NGF(N)을 공백으로 구분해 출력한다.

예제 입력 1

7
1 1 2 3 4 2 1

예제 출력 1

-1 -1 1 2 2 1 -1

풀이

1) 작성한 풀이 → 시간초과로 오답

import sys


def print_NGF(sequence):
    N = len(sequence)
    stack = []
    result = [-1] * N

    for i in range(N):
        while stack and sequence.count(sequence[stack[-1]]) < sequence.count(sequence[i]):
            index = stack.pop()
            result[index] = sequence[i]
        stack.append(i)

    return result


if __name__ == "__main__":
    input = sys.stdin.readline
    N = int(input())
    sequence = list(map(int, input().split()))
    result = print_NGF(sequence)
    print(' '.join(map(str, result)))

2) 개선한 풀이

import sys
from collections import Counter


def print_NGF(sequence):
    N = len(sequence)
    stack = []
    result = [-1] * N
    counter = Counter(sequence)  # 빈도수를 미리 계산하여 저장합니다.

    for i in range(N):
        while stack and counter[sequence[stack[-1]]] < counter[sequence[i]]:
            index = stack.pop()
            result[index] = sequence[i]
        stack.append(i)

    return result


if __name__ == "__main__":
    input = sys.stdin.readline
    N = int(input())
    sequence = list(map(int, input().split()))
    result = print_NGF(sequence)
    print(' '.join(map(str, result)))

풀이과정
1. sys 모듈을 가져옵니다.
1. collections 모듈에서 Counter 클래스를 가져옵니다.
1. print_NGF 함수를 정의합니다. 입력 파라미터는 sequence입니다.
1. 수열의 길이를 N으로 지정합니다.
1. 스택을 초기화합니다.
1. 결과 리스트를 초기화합니다. 모든 요소를 -1로 설정합니다.
1. 빈도수를 미리 계산하여 counter 변수에 저장합니다. 이를 위해 Counter 클래스를 사용합니다.
1. 수열의 인덱스를 순회합니다.
1. 스택이 비어 있지 않고 스택의 가장 높은 인덱스에 있는 요소의 빈도수가 현재 요소의 빈도수보다 작은 동안 반복합니다.
1. 스택의 가장 높은 인덱스 요소를 index에 할당하고 스택에서 제거합니다.
1. 결과 리스트의 index 위치에 현재 요소를 할당합니다.
1. 현재 인덱스를 스택에 추가합니다.
1. 결과 리스트를 반환합니다.
1. 현재 스크립트가 메인 스크립트로 실행되면 다음을 실행합니다.
1. sys.stdin.readline 함수를 사용하여 입력을 받습니다.
1. 정수를 입력 받아 N에 할당합니다.
1. 정수들을 입력 받아 sequence 리스트에 할당합니다.
1. print_NGF 함수를 호출하여 결과를 얻습니다.
1. 결과를 출력합니다.

3) 다른 풀이

freq = [0] * 1000001
n = int(input())
a = list(map(int,input().split()))
for i in range(n):
    freq[a[i]] += 1
ans = [0]*n
s = [0]
for i in range(1, n):
    if not s:
        s.append(i)
    while s and freq[a[s[-1]]] < freq[a[i]]:
        ans[s.pop()] = a[i]
    s.append(i)
while s:
    ans[s.pop()] = -1
print(' '.join(map(str,ans)))

풀이과정
1. 최대 1,000,000개의 빈도수를 저장할 수 있는 리스트 freq를 생성합니다. 초기값은 모두 0입니다.
1. 정수 n을 입력 받습니다.
1. n개의 정수를 입력 받아 리스트 a에 저장합니다.
1. a의 원소들의 빈도수를 계산하여 freq 리스트에 저장합니다.
1. 결과를 저장할 리스트 ans를 초기화합니다. 길이는 n이고 모든 요소는 0입니다.
1. 스택 s를 초기화하고 첫 번째 인덱스 (0)를 추가합니다.
1. 수열의 인덱스 1부터 n까지 순회합니다.
1. 스택이 비어 있지 않으면 스택에 인덱스를 추가합니다.
1. 스택이 비어 있지 않고 스택의 가장 높은 인덱스에 있는 요소의 빈도수가 현재 요소의 빈도수보다 작은 동안 반복합니다.
1. 결과 리스트의 스택의 가장 높은 인덱스 위치에 현재 요소를 할당하고 스택에서 제거합니다.
1. 현재 인덱스를 스택에 추가합니다.
1. 스택이 비어 있지 않은 동안 반복합니다.
1. 결과 리스트의 스택의 가장 높은 인덱스 위치에 -1을 할당하고 스택에서 제거합니다.
1. 결과를 출력합니다.
두 코드의 의미적 차이는 거의 없으나 나는 첫 번째 코드가 가독성이 더 익숙하다.

Uploaded by N2T

'Algorithm' 카테고리의 다른 글

[백준 1934 파이썬/python] 최소공배수 (0)	2023.04.09
[백준 1978 파이썬/python] 소수 찾기 (0)	2023.04.09
[백준 17298 파이썬/python] 오큰수 (0)	2023.04.08
[백준 10799 파이썬/python] 쇠막대기 (0)	2023.04.08
[백준 17413 파이썬/python] 단어 뒤집기 2 (0)	2023.04.08