[BAEKJOON] 17299 | 오등큰수

🔎 17299 | 오등큰수

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

---

💡 Solution

✍🏻

Logic

1. 오른쪽에 있으면서 수열 A에서 등장한 횟수가 F(Ai)보다 큰 수 중에서 가장 왼쪽에 있는 수를 구해야 한다.

2. 수열 A에서 각각의 수가 등장한 횟수를 먼저 파악한다.

3. 오큰수 문제와 마찬가지로 스택이 비어있지 않고 stack의 top 원소 index에 해당하는 수의 count가 현재 index에 해당하는 수의 count보다 작으면 result에 stack의 top 원소에 해당하는 index -> 현재 index에 해당하는 수를 저장한다.

4. 그렇지 않으면 stack에 index를 push한다.

5. 다음의 과정을 수열의 끝에 도달할 때까지 반복한다.

from collections import Counter

n = int(input().rstrip())
num_list = list(map(int, input().split()))
count = Counter(num_list)

def getSGNE(num_list, count) :
    stack = []
    result = [-1] * len(num_list)
    for i in range(len(num_list)) :
        while len(stack) != 0 and count[num_list[stack[-1]]] < count[num_list[i]] :
            result[stack[-1]] = num_list[i]
            stack.pop()
        
        stack.append(i)
    
    return result
    
result = getSGNE(num_list, count)
    
print(' '.join([str(num) for num in result]))

---

▶ 📌 Note

∙ 설명
처음에는 list를 사용해서 count를 세었는데, 이러면 수열이 1,3처럼 중간에 수를 건너 뛰는 경우가 발생해 index error가 발생했다.

이후 dictionary의 setdefault를 활용했지만 반복문으로 숫자를 다 돌아야했기 때문에 시간초과가 일어났다.

최종적으로 collections의 Counter를 사용하여 시간초과를 해결했다.

○ setdefault(key, defaultValue)
- dictionary에 해당 key 값이 있으면 key에 해당하는 value를 반환하고, 없다면 {key: defaultValue}를 추가한다.
- 시간 복잡도가 O(1)이나 반복문을 돌면 O(n)이 된다.

○ Counter
- 반복 데이터를 빈도로 요약하는 데 최적화된 클래스
- 빈도 계산 자체는 O(n), 추가로 정렬 작업(most_common())이 필요하면 O(n log k)