[백준] 17299 : 오등큰수

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

---

문제

---

시도

 

이전에 풀어봤던 오큰수 로직을 약간 수정하여 시도해봤다.

 

import java.io.IOException;
import java.io.BufferedReader;
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));
        StringTokenizer st;

        // N 입력 받기
        final int range = 1000000;
        int n = Integer.parseInt(br.readLine());
        int[] seq = new int[n];
        int[] answer = new int[n];

        int[] freq = new int[range + 1];
        for (int i = 1; i <= range; i++) {
            freq[i] = 0;
        }

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            seq[i] = Integer.parseInt(st.nextToken());
            freq[seq[i]]++;
        }

        int freqMax = -1;
        for (int i = n - 1; i >= 0; i--) {
            if (freq[seq[i]] >= freqMax) {
                freqMax = freq[seq[i]];
                answer[i] = 0;
            } else {
                for (int j = i + 1; j < n; j++) {
                    if (freq[seq[i]] < freq[seq[j]]) {
                        answer[i] = j;
                        break;
                    } else if (freq[seq[i]] < freq[seq[answer[j]]]) {
                        answer[i] = answer[j];
                        break;
                    }
                    answer[i] = 0;
                }
            }
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++)
            sb.append(answer[i] == 0 ? -1 : seq[answer[i]]).append(" ");

        System.out.print(sb);
    }
}

 

908ms로 성공했다.

 

---

풀이

 

조금 더 좋은 방법을 찾기 위해 다른 사람의 풀이를 참고했다.

 

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);
    }
}

 

이 또한 이전과 동일하게 오등큰수가 만족되지 않는 수만 스택에 남도록 로직을 구현했다.

 

70023220: 본인 풀이 // 70013757: 참고 풀이

 

 

소요 시간은 참고한 풀이가 월등히 빨랐으나, 메모리 사용 면에선 내가 작성한 로직이 괜찮을지도..?

---

알게 된 점

 

스택으로 이 정도 난도의 문제를 만들 수 있다는 발상이 신기했다.