[17299] 오등큰수 - Java

 

1. 문제

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

17299번: 오등큰수

 

2. 풀이

1. Stack + 배열을 활용한 풀이

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

public class Main {
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		
		// 1. Read the size of array
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		int N = Integer.parseInt(br.readLine());
		int [] intArray = new int[N];
		int [] count = new int [1000001];
		
		// a. Read each number
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		for(int i = 0; i < N; i++) {
			
			// b. Assign values to the array & calculate F()
			count[intArray[i] = Integer.parseInt(st.nextToken())]++;
		}
		
		// 2. Find NGFs using the concept of stack
		Stack <Integer> stack = new Stack();
		
		for(int i = 0; i < N; i++) {
			
			// a. if stack is not empty and F(stack's peek) < F(i) 
			while(!stack.isEmpty() && count[intArray[stack.peek()]] < count[(intArray[i])]) {
				intArray[stack.pop()] = intArray[i];
			}
			
			stack.push(i);
		}
		
		// b. the remaining indexs of the array, the value becomes -1
		while(!stack.isEmpty()) {
			intArray[stack.pop()] = -1;
		}
		
		// 3. Print result
		for(int i = 0; i < N; i++) {
			bw.write(intArray[i] + " ");
		}
		bw.flush();
		bw.close();
	}
}

 

2. HashMap을 활용한 풀이

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

public class Main {
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		
		// 1. Read the size of array
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		int N = Integer.parseInt(br.readLine());
		int [] intArray = new int[N];
		HashMap <Integer, Integer> F = new HashMap<Integer, Integer>();
		
		// a. Read each number
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		for(int i = 0; i < N; i++) {
			
			// b. Assign values to the array & calculate F()
			
			if(F.containsKey(key)) {
				F.replace(key, F.get(key)+1);
			}else {
				F.put(key, 0);
			}
		}
		
		// 2. Find NGFs using the concept of stack
		Stack <Integer> stack = new Stack();
		
		for(int i = 0; i < N; i++) {
			
			// a. if stack is not empty and F(stack's peek) < F(i) 
			while(!stack.isEmpty() && F(intArray[stack.peek()]) < F((intArray[i]))) {
				intArray[stack.pop()] = intArray[i];
			}
			
			stack.push(i);
		}
		
		// b. the remaining indexs of the array, the value becomes -1
		while(!stack.isEmpty()) {
			intArray[stack.pop()] = -1;
		}
		
		// 3. Print result
		for(int i = 0; i < N; i++) {
			bw.write(intArray[i] + " ");
		}
		bw.flush();
		bw.close();
	}
}

풀이 참고 : https://binghedev.tistory.com/49

 

3. 배운점

- 배열로 간단히 푸는 방법이 생각나지 않아 먼저 HashMap을 활용해보았다. 문제가 풀리긴 하지만 매번 값이 입력될 때마다 key값이 존재하는지 확인해야 해서 시간이 좀 더 소요된다.

 

1. HashMap

2. Array

 

4. 개선할 점

---

풀이 오류 지적, 다른 접근법 공유, 그 밖에 질문 등 모든 의견을 환영합니다.