boj 17299 오등큰수

www.acmicpc.net/problem/17299

17299번: 오등큰수

emoney96.tistory.com/49

boj 17298 오큰수

위의 문제와 같은 문제입니다.

오큰수는 오른쪽에 있는 자신보다 큰 수 중에 가장 왼쪽에 있는 수를 출력하는 문제이고, 

이 문제는 오른쪽에 있는 자신보다 등장횟수가 많은 수 중에 가장 왼쪽에 있는 수를 출력하는 문제입니다.

자신보다 큰 수 -> 자신보다 등장횟수가 많은 수 의 차이이며 풀이는 같습니다.

 

이 문제 역시 수열을 역순으로 탐색하였고,

list[i]를 스택에 넣기 전에 자신보다 등장횟수가 적은 값들을 모두 pop해줍니다.

 

스택이 비어있으면 -1, 아니면 top을 출력해주시면 됩니다.

 

 

[C++]

#include <iostream>
#include <stack>
using namespace std;
 
stack<int> s;
int list[1000001], num[1000001], ans[1000001];
int N;
 
void print() {
    for (int i = 1; i <= N; i++) {
        cout << ans[i] << ' ';
    }
 
    cout << '\n';
}
 
void func() {
    for (int i = N; i > 0; i--) {
        while (!s.empty() && num[list[i]] >= num[s.top()]) s.pop();
 
        if (s.empty()) ans[i] = -1;
        else ans[i] = s.top();
 
        s.push(list[i]);
    }
}
 
void input() {
    cin >> N;
    for (int i = 1; i <= N; i++) {
        cin >> list[i];
        num[list[i]]++;
    }
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
    print();
 
    return 0;
}

 

 

[Java]

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Stack;
import java.util.StringTokenizer;
 
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static Stack<Integer> s = new Stack<>();
    static int list[], num[], ans[];
    static int N;
 
    static void print() {
        StringBuffer sb = new StringBuffer();
        for (int i = 1; i <= N; i++)
            sb.append(ans[i]).append(" ");
        System.out.println(sb.toString());
    }
 
    static void func() {
        for (int i = N; i > 0; i--) {
            while (!s.isEmpty() && num[list[i]] >= num[s.peek()])
                s.pop();
 
            if (s.isEmpty())
                ans[i] = -1;
            else
                ans[i] = s.peek();
 
            s.push(list[i]);
        }
    }
 
    static void input() throws Exception {
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        list = new int[N + 1];
        num = new int[1000001];
        ans = new int[1000001];
 
        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= N; i++) {
            list[i] = Integer.parseInt(st.nextToken());
            num[list[i]]++;
        }
    }
 
    public static void main(String[] args) throws Exception {
        input();
        func();
        print();
    }
}