[자료구조(연습)] [BJ17299] 오등큰수

코드 플러스

🚩 문제 설명

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

17299번: 오등큰수

BJ17299

 

⏱️ 시간 복잡도
▪ 수열의 크기가 100만에 해당한다.
▪ O(N^2)이 되면 시간초과가 된다.
▪ 따라서 O(N)의 시간복잡도로 문제를 해결해야 한다.

◾ 오등큰수

• 해당 수의 오른쪽에 있다.
• 해당 수의 등장횟수보다 큰 수 중에서 가장 왼쪽에 있는 수

◾ 오큰수 문제 처럼 수열의 오등큰수를 구해 출력하는 문제

 

 

 

---

 

 

 

✅ 입출력

1) 수열 A의 수 N이 주어진다.
2) 오등큰수를 구해야하는 수열 A가 주어진다.
return ➡️ 수열 A의 오등큰수를 출력한다.

✔️ 예제 1

7
1 1 2 3 4 2 1

-1 -1 1 2 2 1 -1

 

 

 

---

 

 

 

📑 문제 풀이

with 파이썬 (Python)

import sys

N = int(sys.stdin.readline()) # 수열 A의 크기
A = list(map(int, sys.stdin.readline().split())) # 수열 A
F = {} # F(A[i]) 등장 횟수 배열

stack = [0] # 오등큰수 찾지못한 인덱스 담는 배열
ans = [-1] * N # 출력 배열

# F(A[i]) 세기
for i in A:
    if i not in F:
        F[i] = 1
    else:
        F[i] += 1

# 오등큰수
for i in range(1, N):
    while stack and F[A[i]] > F[A[stack[-1]]]:
        ans[stack.pop()] = A[i]
    stack.append(i)


print(*ans)

💬 Point

➡️  등장횟수를 세는 딕셔너리 F
➡️  stack을 사용

◾ 반복문은 1부터 시작한다.

◾ stack의 top의 요소 값 보다 해당 인덱스의 등장횟수가 더 크다면 ans에 A[i]를 넣는다.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

➕ 참고

https://yeomss.tistory.com/113?category=985840 

[자료구조(연습)] [BJ17298] 오큰수

 

 

# 코드플러스 오등큰수 파이썬

# 백준 17299 오등큰수 파이썬

# 백준 오등큰수 파이썬

---