오등큰수

NJW·2023년 4월 9일

코테

목록 보기

150/170

문제 설명

크기가 N인 수열 A가 있다고 하자. 여기서 F(Ai)는 배열 A의 i번째 수가 얼마나 많이 나오는지를 의미한다.

오등큰수는 현재 숫자의 오른쪽에 있는 수 중 제일 왼편에 있는 F()가 현재 숫자의 F()보다 큰 수이다. 각 숫자의 오등큰수를 구하고 만일 오등큰수가 없다면 -1을 구하라.

문제 풀이

첫 번째 접근

바로 떠오른 건 map과 반복문을 이용하는 것이었다. 각 숫자가 얼마나 나왔는지 (숫자, 숫자가 나온 개수) map을 만들어준 뒤 이차원 반복문을 돌리면서 계속 검사를 해주는 거다.

하지만, 나는 열심히 풀면서 본능적으로 느꼈다. 내가 푼 풀이는 분명 시간 초과가 날 것이라는 거... 배열의 최대 크기가 무려 1,000,000인데 이걸 반복문을 돌리면서 하나씩 비교해 준다고? 골드 3문제가 이렇게 쉽게 풀릴 리 없지. 그리고 나의 생각대로 첫 번째 풀이는 보기 좋게 시간 초과가 났다.

첫 번째 풀이 이차원 반복문 비교


# for i in range(0, len(nums)-1):
    # current = nums[i]
    # for j in range(i+1, len(nums)):
        # post = nums[j]
        # if current != post:
            # if dic[current] < dic[post]:
                # max_count = post
                # break

    # answer[i] = str(max_count)

두 번째 풀이

어... 그러면 어떻게 풀어야 할까. 솔직히 말해서 잘 모르겠다. ㅋㅋㅋㅋㅋㅋㅋㅋㅋ... 결국 10달 전에 내가 푼 풀이를 봤다. 이때는 java로 풀었었는데, 이 당시에도 못 풀어서 답을 봤을 거다.

일단 각 숫자로 map을 만들어 준다(python은 dictionary라고 하지만). 그리고 배열의 각 숫자를 반복문으로 돌려준다.

또 while문으로 반복문을 돌려서 값들을 비교해주는 데, 여기서 첫 번째 반복문의 현재 값을 기준으로 왼쪽에 있는 것들을 비교해야 한다.
문제에서는 현재 위치보다 오른쪽에 있으면서 빈도수가 제일 큰... 이렇게 되어 있어서 i를 기준으로 오른쪽을 생각하기 쉽지만, 문제를 풀 때는 i를 기준으로 왼쪽에 있는 걸 생각해야 한다. 이래서 stack이 필요한 것이다.

stack는 i를 기준으로 왼쪽에 있는 값들의 위치 모음이다. 그리고 stack에 있는 제일 첫 값은 제일 왼쪽에서 제일 오른쪽에 있는 값 즉, i를 기준으로 왼쪽에 있으며 i와 제일 거리상으로 가까운 값의 위치이다.

그래서 스택에 값이 있고 현재 위치의 dic의 값과 스택의 top에 있는 값의 dic와 비교해서 만일 현재 있는 값(top의 dic의 오른쪽에 있는 값)이 더 크면 해당 스택의 top 값을 빼서 answer에 현재의 값을 넣어주면 된다.

그리고 현재 값을 스택에 넣어주면 된다.

후에는 answer을 문자열로 만들어서 출력하면 된다.

세 번째 풀이

두 번째 풀이처럼 했는데 54% 정도에서 계속 시간초과가 났다. 아니 다 했는데 뭐가 문제야 하고 찾아보니 어떤 사람이 Counter 클래스를 사용한 것을 보았다.

Counter 클래스는 collections 모듈의 하위 클래스로 어떤 리스트의 개수를 dictionary처럼 만들어주는 것을 의미한다. Counter 클래스를 쓰면 (key: 해당 값, Value: 해당 값의 개수)로 dictionary가 만들어 진다. 그 이유는 Counter 클래스가 dictionary를 확장하고 있기 때문인데...

그래서 배열을 돌려서 dictionary를 만들어 주는 것 대신 Counter을 써주니 통과가 됐다.

코드

Python

from sys import stdin
from collections import deque
from collections import Counter

N = int(stdin.readline().strip())
nums = list(map(int, stdin.readline().strip().split(" ")))
dic = Counter(nums)
answer = ['-1']*N
max_count = -1
stack = []

for i in range(len(nums)):
    while len(stack) != 0 and dic[nums[stack[-1]]] < dic[nums[i]]:
        answer[stack.pop()] = str(nums[i])

    stack.append(i)

answer = ' '.join(answer)
print(answer)