b.17299 오등큰수

 

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

 

 

 

 

📌 자바(Java)로 푸는 오등큰수 문제 풀이

🔎 문제 개요

주어진 수열에서 각 숫자의 등장 횟수를 고려하여 오른쪽에서 가장 가까운 "더 자주 등장한 숫자"를 찾아야 하는 문제입니다.
일반적인 오큰수(NGE, Next Greater Element) 문제와 달리 "숫자의 크기"가 아닌 "등장 횟수"를 기준으로 비교한다는 점이 다릅니다.

💡 예제 입력

7
1 1 2 3 4 2 1

💡 예제 출력

-1 -1 1 2 2 1 -1

위 예제에서 각 숫자의 등장 횟수를 보면:

• 1 → 3번 등장
• 2 → 2번 등장
• 3 → 1번 등장
• 4 → 1번 등장

각 숫자에 대해 오른쪽에서 더 자주 등장한 숫자를 찾으면 위와 같은 결과가 나옵니다.

---

🛠 알고리즘 접근 방식

이 문제를 해결하기 위해 스택(Stack) 과 배열(Hash Table) 을 활용합니다.

1. 숫자의 등장 횟수를 먼저 구한다.
2. 오른쪽에서 왼쪽으로 숫자를 탐색하며, 스택을 이용해 "더 자주 등장한 수"를 빠르게 찾는다.
3. 스택을 활용하여 시간 복잡도를 O(N)으로 최적화한다.

---

🔹 Java 코드 해설

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

public class Main {

    static int N;               // 수열의 길이
    static int[] numbers;       // 입력된 수열
    static int[] checkNum;      // 각 숫자의 등장 횟수를 저장하는 배열
    static int[] answer;        // 결과를 저장하는 배열

    public static void main(String[] args) throws IOException {
        input();
        logic();
        output();
    }

    // 결과 출력 메서드
    private static void output() {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < N; i++) {
            sb.append(answer[i]).append(" ");
        }
        System.out.println(sb.toString().trim());
    }

    // 알고리즘 실행
    private static void logic() {
        Deque<Integer> stack = new ArrayDeque<>();
        for (int i = N - 1; i >= 0; i--) {  // 오른쪽에서 왼쪽으로 순회
            while (!stack.isEmpty() && checkNum[numbers[i]] >= checkNum[stack.peek()]) {
                stack.pop();  // 현재 숫자보다 등장 횟수가 적은 숫자들을 제거
            }
            if (stack.isEmpty()) {
                answer[i] = -1;  // 더 자주 등장한 숫자가 없으면 -1
            } else {
                answer[i] = stack.peek();  // 가장 가까운 오등큰수를 저장
            }
            stack.push(numbers[i]);  // 현재 숫자를 스택에 넣음
        }
    }

    // 입력 처리
    private static void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());  // 숫자의 개수 입력
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        numbers = new int[N];
        checkNum = new int[1000001];  // 등장 횟수를 저장하는 배열
        answer = new int[N];

        for (int i = 0; i < N; i++) {
            numbers[i] = Integer.parseInt(st.nextToken());
            checkNum[numbers[i]]++;  // 등장 횟수 증가
        }
    }
}

---

🔍 코드 설명

📌 1. 입력 처리 (input())

• numbers[i] 배열에 수열을 저장합니다.
• checkNum 배열을 이용해 각 숫자의 등장 횟수를 저장합니다.
  → checkNum[숫자]++ 형태로 카운팅.

---

📌 2. 오등큰수 찾기 (logic())

💡 오른쪽에서 왼쪽으로 순회하면서 스택을 활용합니다.

1. stack.pop()을 통해 현재 숫자보다 등장 횟수가 작은 숫자들을 제거합니다.
2. 스택이 비었다면 -1, 아니라면 가장 가까운 오등큰수를 정답 배열에 저장합니다.
3. 현재 숫자를 스택에 push하여 이후 숫자와 비교합니다.

📍 중요한 점

• checkNum[numbers[i]] >= checkNum[stack.peek()]이면 스택을 계속 비운다.
• 즉, 현재 숫자의 등장 횟수가 더 많다면 기존 스택의 숫자는 필요 없음!

---

📌 3. 출력 처리 (output())

• StringBuilder를 활용해 결과를 출력합니다.
  → 성능 최적화를 위해 System.out.println() 대신 StringBuilder 사용.

---

🔥 시간 복잡도 분석

연산 최악의 경우 수행 횟수 시간 복잡도

checkNum 배열 초기화	N	O(N)
logic()에서의 반복	N	O(N)
stack의 push/pop	N	O(N)
총합	O(N)

📌 결론
👉 모든 연산이 O(N) 이내로 수행되므로 효율적입니다.

---

🏆 정리

✅ 핵심 포인트

1. 등장 횟수 배열 (checkNum)을 미리 계산한다.
2. 오른쪽에서 왼쪽으로 탐색하면서, 스택을 활용하여 등장 횟수가 더 많은 수를 찾는다.
3. 스택을 이용해 불필요한 비교를 줄여서 시간 복잡도를 O(N)으로 최적화한다.

🎯 이 알고리즘의 장점

✔ 기존 오큰수 문제를 확장한 형태
✔ 스택을 활용해 O(N)으로 최적화
✔ 메모리 사용량이 적고 빠르다.

 

이제 이 방법을 적용하면 오등큰수를 빠르게 찾을 수 있습니다!
💡 스택을 활용한 알고리즘을 익혀두면, 다른 문제에서도 큰 도움이 될 것입니다. 🚀

이 글이 도움이 되었다면, 좋아요와 공유 부탁드립니다! 😊