[BOJ_17299/JAVA] 오등큰수

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

17299번: 오등큰수

문제

 

풀이

해당 문제는 스택으로 풀었다. 

1. 숫자가 나온 횟수를 배열에 저장한다.  (number[])

2. 입력 받은 숫자만큼 for문을 돌면서 스택의 맨 위에 숫자가 같거나 크면 push. 이때 숫자의 인덱스를 push한다. (나중에 인덱스를 찾아 값을 변경하기때문)

3. 만약에 스택의 맨 위의 숫자가 더 작으면 큰 값이 나올 때까지 pop을 해주면서 result[] 인덱스 자리에 비교당한 값(스택에 들어올려는 값)을 넣어준다. 

4. for 문이 끝나고 스택에 값이 남아있으면 -1로 값을 넣어준다.

 

코드

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

public class BOJ17299 {

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		int num = Integer.parseInt(br.readLine());
		Stack<Integer> stack = new Stack<Integer>();
		
		String[] ss = br.readLine().split(" ");
		
		int input[] = new int[num];
		
		for(int i=0;i<num;i++) {
			input[i]=Integer.parseInt(ss[i]);
		}
		
		int number[]=new int[1000001]; 
		
		for(int j=0;j<num;j++) {		
			number[input[j]]+=1;
		}
		
		int result[]= new int[num];		
		
		stack.push(0);
		
		for(int i=1;i<num;i++) {
			
			if(stack.isEmpty()) {
				stack.push(i);
			} 
			
			while(!stack.isEmpty() && number[input[stack.peek()]] < number[input[i]]) {
				result[stack.pop()]=input[i];
			}
			
			stack.push(i);
		}
		
		while(!stack.isEmpty()) {
			result[stack.pop()]=-1;
		}		
		
		for(int x=0;x<num;x++) {
			sb.append(result[x]+" ");
		}
		
		System.out.println(sb);
	}

}

 

---

해당 문제는 17298 오큰수 문제를 풀면서 얻은 방법을 조금 변형하였다.

스택을 이용해서 문제를 푼다는 가장 핵심적인 힌트를 얻었기때문에 풀 수 있었다고 생각한다.

그래도 어려웠지만 ㅠㅠ

조금 더 익숙해질때까지 노력하자..