[BOJ] 백준 17299 오등큰수 (JAVA)

자료구조 응용!

📑 문제

백준 17299 오등큰수

---

🌱 아이디어

위 문제에서 말하는 “오등큰수” 는 NGF(i) 일 때 자기 자신 오른쪽에 있는 숫자 중 자신보다 많은
등장 횟수를 가지는 숫자 중 가장 왼쪽에 있는 수이다.

 

예를 들어보자!

 

ex.) 1 1 1 1 3 1 1인 경우 NGF(3) = 1이다. 반대로 NGF(1) = -1이다, 1보다 큰 등장 횟수가 없기 때문이다.

그리고 출력은 입력된 순서를 지켜야 하기 때문에 -1 -1 -1 -1 1 -1 -1이다.

 

위 문제는 스택을 사용해야 한다. 내가 스택을 사용해야겠다고 유추한 근거는 두 가지이다

 

1. 답을 정하는 조건이 자신의 오른쪽 즉 방향이 정해져 있다.

2. N ≤ 1,000,000이며 이는 O(N^2)를 가지는 단순한 구조로 구현 불가능 -> 시간 초과 발생

 

결론은 효율적인 구조 ex.) O(N)로 로직을 만들어야 하며, 이를 위해서는 자료구조를 사용해야 함.

 

인덱스를 스택에 저장하면서 풀었다.

 

인덱스를 통해 해당 자리의 숫자 검색 + 숫자 등장 횟수를 검색하고

인덱스를 통해 조건에 맞게 출력한다.

---

🌱 코드 및 풀이

---

🌱 느낀 점

최근 자료구조를 연습한 게 도움이 되었다. 

처음 골드 문제를 풀었을 때는 벽을 느꼈는데 요즘은 골드 중하위 문제는 잘 풀 수 있을 정도로 성장한 것 같다 ㅎ

결국 아이디어를 떠올리고 증명하는 것이 핵심이라고 느껴진다.