[백준/G3/Stack/자바] 17299 오등큰수

💡 문제

 

크기가 N인 수열 A = A1, A2, ..., AN이 있다.

수열의 각 원소 Ai에 대해서 오등큰수 NGF(i)를 구하려고 한다.

Ai가 수열 A에서 등장한 횟수를 F(Ai)라고 했을 때,

 Ai의 오등큰수는 오른쪽에 있으면서 수열 A에서 등장한 횟수가 F(Ai)보다 큰 수 중에서 가장 왼쪽에 있는 수를 의미한다. 그러한 수가 없는 경우에 오등큰수는 -1이다.

예를 들어, A = [1, 1, 2, 3, 4, 2, 1]인 경우 F(1) = 3, F(2) = 2, F(3) = 1, F(4) = 1이다.

A1의 오른쪽에 있으면서 등장한 횟수가 3보다 큰 수는 없기 때문에, NGF(1) = -1이다.

A3의 경우에는 A7이 오른쪽에 있으면서 F(A3=2) < F(A7=1) 이기 때문에, NGF(3) = 1이다.

NGF(4) = 2, NGF(5) = 2, NGF(6) = 1 이다.

 

⌨ 입력

 

첫째줄 수열 A의 크기 ( 1 <= N <= 100만 )

둘째줄 수열 A의 원소 A....( A <= A <= 100만 )

 

💻 출력 / 제한

 

총 N개의 수 NGF(1), NGF(2), ..., NGF(N)을 공백으로 구분해 출력한다.

 

 

---

 

풀이 방법

 

문제 유형 : Stack ( 자료 구조 )

 

 

예시로 보는편이 이해가 잘되서 예제를 사용 하겠습니다. ( 저도 못 풀었어요 )

 

Stack 에는 오등큰수를 찾지 못한 원소의 Index가 들어 있습니다.

ans 배열은 해당 원소의 오등큰수를 저장 합니다.

 

i = 0 인 경우 (  for문을 통해 수열의 크기 만큼 탐색 ) 

비교 대상이 없으므로 stack.add(0)

i = 1 인 경우

stack.peek = 0;
data[0] = 1; → count[1] = 3;

즉 3보다 큰 값이 들어 와야 오등큰수 입니다.
조건문 !stack.isEmpty() && count[data[stack.peek()]] < count[data[i]]   -> 3 <  3; 
조건문이 종료 되고 현재 Index stack.add(1) 합니다.

 

i = 2 인 경우

count[data[stack.peek()]] = 3 count[data[2]] =2

3보다 작은 수가 들어 왔으므로 조건문을 종료 하고 현재 Index를 stack 넣습니다.
2보다 큰 수를 찾아야 합니다.

 

i = 3 인 경우

2 < 1

stack.add(3)
1보다 큰수를 찾아야 합니다.

 

i = 4 인 경우

1 < 1

stack.add(4)
1보다 큰수를 찾아야 합니다.

 

i = 5 인 경우

1 < 2

1 보다 큰 값이므로
ans[stack.pop()] = count[data[i]]; 업데이트 합니다.

ans[4] = 2;

stack.peek() = 3 이 됩니다.
마찬가지로 count[data[stack.peek()]] = 1 이므로
ans[3] = 2; 가 됩니다.

 

i = 6인 경우

For 문을 마친 경우

(Stack에 남아있는 Index는 오등큰수를 찾지 못한 원소의 Index 입니다. )

 

남은 Index를 ans[stack.pop]  =  -1 업데이트 합니다.

 

---

 

전체 코드

import java.io.*;
import java.util.Stack;
import java.util.StringTokenizer;

public class RankFiveNumber17299 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuffer sb = new StringBuffer();

        int N = Integer.parseInt(br.readLine());
        int[] data = new int[N];
        int[] count = new int[1000001];
        int[] ans = new int[N];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i = 0; i < N; i++) {
            data[i] = Integer.parseInt(st.nextToken());
            count[data[i]]++;
        }

        Stack<Integer> stack = new Stack<>();
        for(int i = 0; i < N; i++){
            while(!stack.isEmpty() && count[data[stack.peek()]] < count[data[i]]){
                ans[stack.pop()] = data[i];
            }
            stack.add(i);
        }

        while(!stack.isEmpty())
            ans[stack.pop()] = -1;

        for(int i = 0; i<N; i++)
            sb.append(ans[i]).append(" ");

        System.out.println(sb);
    }
}