[Gold-3] 17299번 | 스택 | 자바(Java)

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

 

 

해당 백준 문제는 오등큰수를 스택 알고리즘을 사용해 풀이하는 문제이다.

예시를 보면 어떤 문제인지 이해할 수 있다.

 

우선 문제에 맞게

1. N개의 수를 저장할 배열

2. 배열 내에서 특정 숫자가 몇 번 등장했는지 frequency를 저장할 배열

3. NGF를 저장할 배열

을 만들어주면 된다.

 

 

int N = Integer.parseInt(br.readLine());
        int[] A = new int[N];
        int[] NGF = new int[N]; // 결과 배열
        int[] freq = new int[1000001]; // 등장 횟수 기록 배열
        
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            A[i] = Integer.parseInt(st.nextToken());
            freq[A[i]]++; // 등장 횟수 계산
        }

 

 

이렇게 하면

초기 상태 :

freq[1] = 3, freq[2] = 2, freq[3] = 1 ,freq[4] = 1 이 될 것이다.

 

그리고, 이제 스택을 활용해 조건에 맞는 인덱스를 스택에 추가하여 해당 인덱스의 숫자와의 빈도수를 비교할 것이다.

 

Stack<Integer> stack = new Stack<>();
        for (int i = N - 1; i >= 0; i--) {
            // 스택의 최상단에 있는 수가 등장 횟수가 적을 경우 제거
            while (!stack.isEmpty() && freq[A[stack.peek()]] <= freq[A[i]]) {
                stack.pop();
            }
            
            // 조건을 만족하는 수를 결과에 저장
            if (stack.isEmpty()) {
                NGF[i] = -1;
            } else {
                NGF[i] = A[stack.peek()];
            }
            
            // 현재 인덱스를 스택에 추가
            stack.push(i);
        }

 

오른쪽에서 왼쪽으로 탐색:

• i=6,A[6]=1i = 6, A[6] = 1i=6,A[6]=1
  • 스택 비어 있음 → NGF[6] = -1
  • 스택에 6 추가 → stack = [6]
• i=5,A[5]=2i = 5, A[5] = 2i=5,A[5]=2
  • freq[2]=2>freq[1]=3freq[2] = 2 > freq[1] = 3freq[2]=2>freq[1]=3: 스택에서 제거
  • NGF[5] = 1
  • 스택에 5 추가 → stack = [5]
• i=4,A[4]=4i = 4, A[4] = 4i=4,A[4]=4
  • NGF[4] = 2
  • 스택에 4 추가 → stack = [5, 4]
• ...

이런식으로 최종 스택 상태를 사용해 결과를 계산하면 된다.

 

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        
        // 입력 처리
        int N = Integer.parseInt(br.readLine());
        int[] A = new int[N];
        int[] NGF = new int[N]; // 결과 배열
        int[] freq = new int[1000001]; // 등장 횟수 기록 배열
        
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            A[i] = Integer.parseInt(st.nextToken());
            freq[A[i]]++; // 등장 횟수 계산
        }
        
        // 스택 활용
        Stack<Integer> stack = new Stack<>();
        for (int i = N - 1; i >= 0; i--) {
            // 스택의 최상단에 있는 수가 등장 횟수가 적을 경우 제거
            while (!stack.isEmpty() && freq[A[stack.peek()]] <= freq[A[i]]) {
                stack.pop();
            }
            
            // 조건을 만족하는 수를 결과에 저장
            if (stack.isEmpty()) {
                NGF[i] = -1;
            } else {
                NGF[i] = A[stack.peek()];
            }
            
            // 현재 인덱스를 스택에 추가
            stack.push(i);
        }
        
        // 결과 출력
        for (int i = 0; i < N; i++) {
            sb.append(NGF[i]).append(" ");
        }
        System.out.println(sb.toString());
    }
}