백준 17299번: 오등큰수

문제

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

17299번: 오등큰수

---

풀이

크기가 N인 수열 A = A1, A2,..., AN이 있을 때 오른쪽에 있으면서 Ai보다 수열 A에서 등장한 횟수가 큰 수 중에서 가장 왼쪽에 있는 수인 Ai의 오큰수를 구하는 문제입니다.

---

코드

C언어

정수 배열 arr를 동적할당하여 입력받고 입력받은 수가 등장한 횟수를 정수 배열 cnt에 기록합니다. 이후 i를 포함한 for문에 들어가며 이때 스택에는 배열의 인덱스 값이 들어갑니다.

for문 안에있는 while문 안에서 스택이 비어있지 않을 때 cnt[arr[i]]가 cnt[arr[스택의 최상단 데이터(인덱스)]]보다 클 때까지 arr[pop한 인덱스]을 arr[i]로 바꿔줍니다. (이때 새로운 정수 배열을 만들지 않은 이유는 어차피 이미 지나간 인덱스는 다시 확인하지 않기 때문입니다.) while문이 끝나면 i를 스택에 push합니다.

for문이 끝났을 때 arr[스택에 남아있는 데이터들]는 오른쪽에 자신보다 등장한 횟수가 큰 수가 없다는 것을 의미하므로 모두 -1을 넣어줍니다.

문제는 다르지만 이 코드가 어떤 방식으로 돌아가는지에 대한 자세한 내용은 제가 이전에 작성한 오큰수 문제에 있습니다. 이 글에서는 arr[스택의 최상단 데이터]와 arr[i]를 비교했지만 이 문제에서는 cnt[arr[스택의 최상단 데이터]]와 cnt[arr[i]]를 비교한다는 차이만 있을 뿐입니다. 이를 유의하여 이 글에서의 예시를 { 1, 1, 2, 3, 4, 2, 1 }로 바꿔서 생각하면 됩니다.

#include <stdio.h>
#include <stdlib.h>
int stack[1000000], cnt[1000001] = { 0 };
int idx = -1;
void push(int value) {
	stack[++idx] = value;
}
int pop() {
	return stack[idx--];
}
int is_empty() {
	return (idx == -1);
}
int peek() {
	return stack[idx];
}
main() {
	int n;
	scanf("%d", &n);
	int* arr = (int*)malloc(sizeof(int) * n);
	for (int i = 0; i < n; i++) {
		scanf("%d", &arr[i]);
		cnt[arr[i]]++;
	}
	for (int i = 0; i < n; i++) {
		while (!is_empty() && cnt[arr[peek()]] < cnt[arr[i]]) {
			arr[pop()] = arr[i];
		}
		push(i);
	}
	while (!is_empty()) {
		arr[pop()] = -1;
	}
	for (int i = 0; i < n; i++) {
		printf("%d ", arr[i]);
	}
}

자바

위의 C언어를 이용한 풀이와 동일하지만 스택을 따로 구현하지는 않고 자바 util 패키지의 Stack 클래스를 이용하였습니다. 또한 Stringbuilder를 이용하여 한꺼번에 출력하였습니다.

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

public class Main {
    public static void main(String[] args) throws IOException {
        Stack<Integer> stack = new Stack<Integer>();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] arr = new int[n];
        int[] cnt = new int[1000001];
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
            cnt[arr[i]]++;
        }
        for (int i = 0; i < n; i++) {
            while (!stack.empty() && cnt[arr[stack.peek()]] < cnt[arr[i]]) {
                arr[stack.pop()] = arr[i];
            }
            stack.push(i);
        }
        while (!stack.empty()) {
            arr[stack.pop()] = -1;
        }
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            sb.append(arr[i]).append(" ");
        }
        System.out.println(sb);
    }
}

 

---

결론

17298번 오큰수와 풀이가 크게 다르지 않은 비슷한 문제를 풀었습니다. 그래서 골드3이라는 난이도에 비해 푸는 데에 시간이 오래 걸리진 않았습니다. 이런 문제를 아무런 준비가 되어있지 않은 상태에서 마주했을 때 바로바로 생각날 수 있도록 계속 복습해야겠습니다.