[Python - 17299] 오등큰수 (G3)

문제

17299번: 오등큰수

문제

문제

문제 이해

• 크기가 N인 수열 A = A1, A2, A3, ..., AN이고, 각 원소 Ai에 대한 오등큰수 NGF(i)를 구함
• Ai가 수열 A에 등장한 횟수 = F(Ai)
• Ai의 오등큰수는 오른쪽에 있고 수열 A에서 등장한 횟수가 F(Ai) 보다 큰 수 중 가장 왼쪽에 있는 수, 없으면 -1

문제 예시 설명

N = 7  # 수열의 크기
A = [1, 1, 2, 3, 4, 2, 1]  # 크기가 N인 수열 A
F(1) = 3, F(2) = 2, F(3) = 1, F(4) = 1  # 각 숫자가 등장한 횟수

A1 = 1, 오른쪽에 F(1)보다 큰 수는 없으므로 -1
A2 = 1, 오른쪽에 F(1)보다 큰 수는 없으므로 -1
A3 = 2, 오른쪽에 F(2)보다 큰 수는 1
A4 = 3, 오른쪽에 F(3)보다 큰 수는 2와 1이지만 더 왼쪽에 있는 2
A5 = 4, 오른쪽에 F(4)보다 큰 수는 2와 1이지만 더 왼쪽에 있는 2
A6 = 2, 오른쪽에 F(2)보다 큰 수는 1
A7 = 1, 오른쪽에 F(1)보다 큰 수는 없으므로 -1
따라서, 최종 출력은 -1 -1 1 2 2 1 -1

풀이 (1)

각 숫자의 등장 횟수를 리스트에 저장 후 앞에서부터 수열 A를 순회하며 각 NGF(i)를 계산
가장 단순한 풀이이자 시간초과가 나오는 풀이
시간 복잡도 : O(N^2)

1. 크기 N, 수열 A 입력
2. 등장 횟수를 0으로 초기화 후 Ai 등장 횟수 count
3. 수열 A를 순회하며 각 NGF(i) 계산

코드

역시나 시간초과가 나왔다.

import sys
input = sys.stdin.readline

N = int(input())
A = list(map(int, input().split()))
Ai_count = [0 for _ in range(max(A) + 1)]
NGF = []

for i in range(N):
    Ai_count[A[i]] += 1

max_count = max(Ai_count)

for i in range(N):
    if Ai_count[A[i]] == max_count:
        NGF.append(-1)
    else:
        Ai_NGF = -1
        for j in range(i, N):
            if Ai_count[A[i]] < Ai_count[A[j]]:
                Ai_NGF = A[j]
                break
        NGF.append(Ai_NGF)

print(*NGF)

풀이 (2)

스택 2개를 활용하여 수열 A를 역순회하며 각 NGF(i)를 계산
[Ai, 등장 횟수]를 스택에 저장하여 등장 횟수를 비교하여 클 경우에 해당 숫자 저장
시간 복잡도 : O(N)

1. 크기 N, 수열 A 입력
2. 등장 횟수를 0으로 초기화 후 Ai 등장 횟수 count
3. 수열 A를 역순회하면서 각 NGF(i) 계산
   1. 처음은 무조건 -1, 1번 스택에 [Ai, 등장 횟수] push
   2. 1번 스택의 top에 현재 Ai의 count보다 크면 해당 숫자를 NGF에 append 및 1번 스택에 현재 [Ai, 등장 횟수] push
   3. 1번 스택의 top에 현재 Ai의 count보다 작으면, 2번 스택에 pop 및 다시 1번 스택의 top과 비교
   4. 1번 스택의 top이 비어있으면, -1
   5. NGF에 저장 후 2번 스택이 비어있을 때까지 1번 스택에 push

스택

다음과 같이 역순회를 진행하며 stack_1에는 [Ai, 등장 횟수]가 저장된다. stack_2에는 Ai의 등장 횟수보다 Stack_1의 등장 횟수가 작은 경우 stack_2로 넘겼다가 다음 숫자로 진행되기 전에 다시 stack_1으로 옮긴다.

Stack

코드

결과적으로 시간 복잡도는 O(N)이지만, 스택을 옮겨가는 과정에서 많은 연산을 사용해서 시간 초과가 발생하였다.

import sys
input = sys.stdin.readline

N = int(input())
A = list(map(int, input().split()))
Ai_count = [0] * (max(A) + 1)
NGF = []

stack_1 = []
stack_2 = []

for i in range(N):
    Ai_count[A[i]] += 1

NGF.append(-1)
stack_1.append([A[-1],Ai_count[A[-1]]])

for i in range(N-2, -1, -1):
    try:
        while stack_1[-1][1] <= Ai_count[A[i]]:
            stack_2 += [stack_1[-1]]
            del stack_1[-1]
        NGF.append(stack_1[-1][0])
    except:
        NGF.append(-1)
    finally:
        stack_1 += stack_2
        stack_2 = []
        if Ai_count[A[i]] != 1:
            stack_1.append([A[i],Ai_count[A[i]]])

print(*NGF[::-1])

풀이 (3)

스택을 하나만 사용하여 NGF(i)를 계산
시간 복잡도 : O(N)

1. 크기 N, 수열 A를 입력
2. 등장 횟수를 0으로 초기화 후 Ai 등장 횟수 count
3. 수열 A를 역순회하면서 각 NGF(i) 계산
   1. 현재 숫자의 빈도보다 작거나 같은 빈도를 가진 숫자는 스택에서 제거
   2. 스택이 비어있지 않다면 NGF를 현재 스택의 맨 위 숫자로 설정
   3. 현재 숫자를 스택에 추가

코드

import sys
input = sys.stdin.readline

N = int(input())
A = list(map(int, input().split()))

# 각 숫자의 빈도를 계산
Ai_count = [0] * (max(A) + 1)
for num in A:
    Ai_count[num] += 1

# 결과를 저장할 리스트
NGF = [-1] * N
stack = []

# 리스트를 역순으로 순회
for i in range(N-1, -1, -1):
    print(stack)
    # 현재 숫자의 빈도보다 작거나 같은 빈도를 가진 숫자는 스택에서 제거
    while stack and Ai_count[stack[-1]] <= Ai_count[A[i]]:
        stack.pop()
    # 스택이 비어있지 않다면 NGF를 현재 스택의 맨 위 숫자로 설정
    if stack:
        NGF[i] = stack[-1]
    # 현재 숫자를 스택에 추가
    stack.append(A[i])

print(*NGF)