[JAVA] 자료구조 연습문제 - 백준 17299

ArrayIndexOutOfBounds 오류 해결

 

수열의 길이에 맞춰 freq배열을 생성하면,

수열의 숫자를 인덱스로 사용하는 freq배열에서 인덱스 범위오류가 난다.

 

ex) 1개 짜리 수열[3]을 위해서, freq[0,0,0,1]을 저장하는 최소 사이즈 3이상의 freq배열이 필요하다.

 

수열의 최대사이즈는 1,000,000이므로

freq배열을 1,000,001 사이즈로 만들고 0으로 초기화해주면 범위오류를 해결할 수 있다.

 

package com.company;
import java.io.*;
import java.util.*;
public class BOJ17299 {
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        Stack<Integer> st=new Stack<>();
        int t=sc.nextInt();
        int[] nums=new int[t];
        int[] NGF=new int[t];
        int[] freq=new int[1000001];

        Arrays.fill(NGF, -1);
        Arrays.fill(freq, 0);

        for(int i=0;i<t;i++){
            nums[i]=sc.nextInt();
            freq[nums[i]]+=1;
        }

        for(int i=1;i<t+1;i++){
            int numFreq=freq[nums[i-1]];

            if(st.empty()){
                st.push(i-1);
            }
            else{
                while(freq[nums[st.peek()]]<numFreq){
                    NGF[st.pop()]=nums[i-1];
                    if(st.empty())
                        break;
                }
                st.push(i-1);
            }
        }

        for(int i=0;i<t;i++){
            bw.write(NGF[i]+" ");
        }
        bw.flush();
    }
}