[BOJ/C++]17299_오등큰수(작성중)

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

##문제 풀기 전 내가 알고 있었어야 할 개념 :

1_ 백준 17298번 문제인, "오큰수" 문제부터 이해하고 오기 [ https://www.acmicpc.net/problem/17298 ]

2_★ 입력된 정수 배열에 중복된 개수 Check => cnt배열 이용

ex)

3_ 17298번 vs 17299번 논리 비교

3_1) 공통 논리

• A배열 Scan 중. 1번째값은 Stack에 인덱스 그냥 Push()
• Stack에는 A배열의 원소가 아닌 인덱스 값을 넣는다.
• A[Stack.top()] 과 지칭값 비교(문제 조건에 따라 달라지는 규칙)

if_ⓐ 지칭값이 이기는 논리라면 => 결과배열[Stack.top()의 인덱스]  = 지칭값; => Stack,top()을 Pop()

   => 다시 Stack의 top()과 지칭값 비교(while) 

else if_ⓑ A[Stack.top()]이 이기는 논리라면 => 그냥 Push(지칭값의 인덱스);

3_2) 차이

• 17298 : A[Stack.top()] < 지칭값 => ⓐ / else => ⓑ (오큰수 조건 때문)
• 17299 : A[Stack.top()]의 중복횟수 < 지칭값의 중복횟수 => => ⓐ / else => ⓑ  (오등큰수 조건 때문)

##예제입력1 분석해보기 (작성중 미완성)

 

##코드

#include <iostream>
#include <stack>
#include <vector>
 
using namespace std;
 
void init() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
}
 
int main() {
 
    init();
 
    int N,max=0,min=0;
    cin >> N;
    vector <int> A(N);
    vector <int> B(N,-1);
    stack <int> S;
 
    for (int i = 0; i < N; i++) {
        int input;
        cin >> input;
        A[i]= input;
        //최대 최소 구하기
        if (input > max) {
            max = input;
        }
        if (input < min) {
            min = input;
        }
    }
 
    vector <int> cnt(max - min + 1+1, 0);
 
    for (int i = 0; i < N; i++) {
        cnt[A[i]]++;
    }
 
 
    for (int i = 0; i < N; i++) {
        while (S.size() > 0 && cnt[A[S.top()]] < cnt[A[i]]) {
            B[S.top()] = A[i];
 
            S.pop();
        }
 
        S.push(i);
    }
 
    for (int i = 0; i < N; i++)cout << B[i] << '\n';
    
 
    return 0;
}