[Baekjoon] 17299_오등큰수

Gold III

문제(출처: https://www.acmicpc.net/problem/17299)

---

< 오등큰수 >

 

문제 풀이 & 생각

 

17298 오큰수 문제에서 수열에 등장한 횟수만 추가로 구하니 문제를 쉽게 해결할 수 있었다.

 

https://melody-coding.tistory.com/324

[Baekjoon] 17298_오큰수

 

 

 

 my solution (Java)

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Stack;
import java.util.StringTokenizer;

public class _17299_ { // 오등큰수

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;

		int n = Integer.parseInt(bf.readLine());
		int arr[] = new int[n];
		int result[] = new int[n];
		int f[] = new int[1000001];

		st = new StringTokenizer(bf.readLine());
		for (int i = 0; i < n; i++) {
			int num = Integer.parseInt(st.nextToken());
			arr[i] = num;
			f[num] += 1;
			result[i] = -1;
		}

		Stack<Integer> stack = new Stack<>();
		for (int i = 0; i < n - 1; i++) {
			if (f[arr[i]] < f[arr[i + 1]]) {
				result[i] = arr[i + 1];
				while (!stack.isEmpty()) {
					if (f[arr[stack.peek()]] < f[arr[i + 1]]) {
						int num = stack.pop();
						result[num] = arr[i + 1];
					} else {
						break;
					}
				}
			} else {
				stack.add(i);
			}
		}
		for (int i = 0; i < n; i++) {
			bw.write(result[i] + " ");
		}
		bw.flush();
	}
}

 

Main

- 수열 A의 크기 (n) 입력

- arr : 수열 저장

  result: 오등큰수 저장

  f : 수열에서 등장한 횟수 저장

- 수열을 탐색하며 현재 값의 등장 횟수와 다음 값의 등장 횟수를 비교 -> 다음 값이 현재 값 보다 크다면 오등큰수 이므로 result 배열에 저장, stack에 값이 있는지 확인 후 stack에 있는 값의 등장 횟수가 다음 값의 등장 횟수보다 작다면 stack에 있는 값의 오등큰수를 찾은 것이므로 오등큰수 저장  But 오등큰수가 아니라면 오등큰수를 찾기 위해 stack에 값을 저장

- result 배열 출력

 

---

---