17299번 - 오등큰수

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

17299번: 오등큰수

오큰수 문제와 비슷하다. 그런데... "시간초과" 이게 날 괴롭혔다.

애초에 문제를 잘못읽은 부분이 있었다. 

빈도만 따지면 되는데 수까지 커야 한다고 생각한 것이다.  따라서 조건을 아래와 같이 두 개로 선정하였다.

A[i] <= stack[-1] and F[A[i]-1]>=F[stack[-1]-1]

그리고 리스트의 count 연산은 시간을 많이 소모한다.  따라서... 아래처럼 count를 쓰기 보다는 for 반복문으로 직접 세는게 더 낫다. 그리고 생각해보건데, A에 포함되지 않은 수까지 count 연산을 진행하는 것도 영향이 있을 것 같다. 1번의 경우, 0부터 A의 최댓값까지 모두 A에 접근하여 count 연산을 진행하기 때문이다.

# 1: count 사용
F = [A.count(i+1) for i in range(max(A))]

# 2: 반복문 사용
F = [0 for i in range(max(A)+1)]
for i in range(N):
    F[A[i]] += 1

 

제출한 최종 코드는 아래와 같다.

# 오등큰수
import sys
input = sys.stdin.readline

N = int(input())
A = list(map(int, input().split()))
F = [0 for i in range(max(A)+1)]
for i in range(N):
    F[A[i]] += 1
stack = []
result = ['' for _ in range(N)]
for i in range(N-1, -1, -1): 
    while stack and F[A[i]]>=F[stack[-1]]:
        stack.pop()
    if stack:
        result[i] = str(stack[-1])
    else:
        result[i] = '-1'
    stack.append(A[i])
    
print(' '.join(result))