공부 86일차: 백준 17299번 오등큰수 자바 Java

17299 오등큰수

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

17299번: 오등큰수

 

 

 

---

백준 17299번 문제 오등큰수

---

문제

---

 

 

 

 

---

과정 생각해보기

---

 

https://gimbalja.tistory.com/163

바로 전 문제인 오큰수와 유사하게, 배열의 인덱스값을 스택에 넣는다

 

추가로 하나 더 구할 것이 있다

빈도수를 구해야 하기 때문에, 카운팅 정렬에서 사용했듯 배열의 인덱스 = 빈도수로 맞추고 구해둔다

 

예시의 1 1 2 3 4 2 1

arr[] = {1, 1, 2, 3, 4, 2, 1}

count[ 입력할 수 있는 수 범위+1 = 1,000,001] 

count[1] = 3

count[2] = 2

count[3] = 1

count[4] = 1

 

 

스택이 비어있다면 push

push(0)stack [ 0 ]

 

count[arr[push 다음 수 1]] = count[arr[st.peek() = 0]]count[1] = count[1]3 = 3바뀔 것 없으니 그대로 push(1)stack [ 0 1 ]

 

count[arr[push 다음 수 2]] < count[arr[st.peek() = 1]]count[2] < count[1]2 < 3빈도수가 크긴 하지만 2의 오른쪽에 있지 않으므로 push(2)stack [ 0 1 2 ]

 

count[arr[3]] < count[2]1 < 2빈도수가 크긴 하지만 2의 오른쪽에 있지 않으므로 push(3)stack [ 0 1 2 3 ]

 

count[4] = count[3]1 = 1바뀔 것 없으니 그대로 push(4)stack [ 0 1 2 3 4 ]

 

count[arr[5] = 2] > count[4]2 > 1좌변 = 현재 위치, 우변 = 이전 위치 이므로 좌변은 우변의 오른쪽에 있으면서 빈도수도 더 높은 게 된다따라서arr[st.pop() = 4] = arr[5] = 2stack [ 0 1 2 3 ]

 

count[arr[5]] > count[3]2 > 1역시나 조건을 만족하므로arr[3] = arr[5] = 2stack [ 0 1 2 ]

 

count[arr[5]] = count[2] 2 = 2바뀔 것 없으니 그대로 push(5)stack [ 0 1 2 5 ]

 

count[arr[6] = 1] > count[5]3 > 2조건을 만족하므로arr[5] = arr[6] = 1stack [ 0 1 2 ]

 

count[arr[6]=1] < count[2]3 > 2조건을 만족하므로arr[2] = arr[6] = 1stack [ 0 1 ]

 

count[arr[6]] = count[arr[1] = 1]3 = 3바뀔 것 없으니 그대로 push(6)

 

배열의 처음부터 끝까지 돌았으니 반복문 종료스택에 남은 인덱스값은 우등큰수를 가지지 못하는 숫자이므로 반복문으로 -1씩 넣어준다 

 

 

---

정답 인정 코드

---

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
import java.util.StringTokenizer;
 
public class Main {
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Stack<Integer> st = new Stack();
        StringBuilder sb = new StringBuilder();
        
        int n = Integer.parseInt(br.readLine());
        
        int arr[] = new int[n];
        int count[] = new int[1_000_001];
        
        StringTokenizer stn = new StringTokenizer(br.readLine());
        for(int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(stn.nextToken());
        }
        
        for(int i = 0; i < n; i++) {
            count[arr[i]]++;
        }
        
        for(int i = 0; i < n; i++) {
            
            //스택이 비어있지 않고 현재 위치가 스택에 들어있는 이전 숫자보다 빈도수가 높다면
            while(!st.empty() && count[arr[i]] > count[arr[st.peek()]]) {    
                arr[st.pop()] = arr[i];    //현재 숫자를 넣는다
            }
            
            st.push(i);
        }
        
        while(!st.empty()) {
            arr[st.pop()] = -1;
        }
        
        for(int i = 0; i < n; i++) {
            sb.append(arr[i]).append(' ');
        }
        
        System.out.println(sb);
 
    }
 
}
 

 

위에서 설명한 과정을 그대로 적었다

주석에 필요한 설명을 적기도 했다

현재 위치는 무조건 스택에 담겨 있는 숫자보다 오른쪽에 있으므로, 카운트값이 크기만 하다면 바로 넣으면 된다는 게 핵심 같다

 

 

 

---

오큰수 문제를 풀지 않았다면 절대 못풀었을 듯.. 사실 오큰수 푼 다음임에도 엄청 헤맸고 어려웠음..