[스택] 17299 : 오등큰수

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

17299번: 오등큰수

전에 푼 오큰수와 비슷한 문제여서 쉽게 풀었다.

다만 처음에 빈스택에 접근할 때 생기는 오류가 발생하여 런타임에러가 발생했다.

pop 메소드를 사용할 때 한 번 더 체크하는 습관을 가지도록 하자.

 

내코드

메모리 : 143728 KB

시간 : 1072 ms

코드길이 : 1436 B

 

[내코드]

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));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st;
		
		int N = Integer.parseInt(br.readLine());
		int[] arr = new int[N];
		int[] TimesOfNum = new int[1000001];
		st = new StringTokenizer(br.readLine());
		for(int n = 0; n < N; n++) {
			arr[n] = Integer.parseInt(st.nextToken());
			TimesOfNum[arr[n]] += 1;
		}
		
		int[] NGF = new int[N];
		Stack<Integer> stack = new Stack<>();
		
		for(int i = 0; i < N; i++) {
			if(stack.isEmpty())
				stack.push(i);
			else {
				//현재인덱스의 등장횟수가 이전인덱스의 등장횟수보다 크면
				if(TimesOfNum[arr[stack.peek()]] < TimesOfNum[arr[i]]) {
					//현재인덱스의 등장횟수가 큰 동안 스택의 인덱스들을 pop해준다.
                    //pop후에 빈 스택이 되면 peek할 때 오류가 생길 수 있으므로 비어있지 않을 때의 조건을 붙여줘야 함
					while(!stack.isEmpty() && TimesOfNum[arr[stack.peek()]] < TimesOfNum[arr[i]])
						NGF[stack.pop()] = arr[i];
					//다 빼면 현재 인덱스를 스텍에 넣어줌
					stack.push(i);
				}
				else
					stack.push(i);
			}
		}
		while(!stack.isEmpty())
			NGF[stack.pop()] = -1;
		
		for(int i = 0; i < NGF.length; i++) {
			sb.append(NGF[i]).append(' ');
		}
		
		System.out.print(sb);

	}

}

 

1등 코드

메모리 : 54536 KB

시간 : 568 ms

코드길이 : 990 B

 

[상위권 코드]

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();

        int[] origin = new int[N];
        int[] stack = new int[N];
        int[] freq = new int[10000001];
        int top = -1;

        for(int i=0; i<N; i++){
            origin[i] = Integer.parseInt(st.nextToken());
            freq[origin[i]]++;
        }

        stack[++top] = 0;
        for(int i=1; i<N; i++){
            while(top != -1 && freq[origin[i]] > freq[origin[stack[top]]]){
                int idx = stack[top--];
                origin[idx] = origin[i];
            }
            stack[++top] = i;
        }
        while(top != -1){
            int idx = stack[top--];
            origin[idx] = -1;
        }

        for(int i : origin ){ sb.append(i + " "); }
        System.out.print(sb);
    }
}