[백준 17298 17299] 오큰수 , 오등큰수 C++

17298번: 오큰수

17299번: 오등큰수

자료구조, 스택 문제

---

1. 문제풀이 아이디어

N이 최대 1,000,000이므로 단순히 2중 for문으로 해결하는건 시간제한에 걸리게 된다.

(N이 최대 5,000 정도면 가능할듯..)

풀이 흔적

(1) 오큰수

1. 스택이 비어있을때 지금 보는 배열의 원소와 원소의 인덱스를 스택에 넣어준다

2. 비어있지 않을때 지금 보고있는 배열의 원소(arrnow)가 스택의 top()보다 크다면 NGE[스택 최상단 원소의 인덱스위치]에 arrnow를 입력해주고 스택을 pop()한다. <- 이 작업을 스택에 원소가 없거나 스택의 top()보다 arrnow가 더 작을때까지 반복.

3. 그리고 arrnow와 그 인덱스를 스택에 push한다.

 

 

(2) 오등큰수

1. 입력 받을 때 카운팅 정렬에서 사용한 방법을 통해 현재 원소가 몇 번 나왔는지 배열에 입력(배열의 인덱스가 원소를 의미)

2. 스택이 비어있을때 지금 보는 배열의 등장 횟수와 원소의 인덱스를 스택에 넣어준다

3. 비어있지 않을때 지금 보고있는 배열의 등장 횟수(countingnow)가 스택의 top()보다 크다면 NGE[스택 최상단 원소의 인덱스위치]에 arrnow를 입력해주고 스택을 pop()한다. <- 이 작업을 스택에 원소가 없거나 스택의 top()보다 countingnow가 더 작을때까지 반복.

4. 그리고 arrnow와 그 인덱스를 스택에 push한다.

---

2. 코드

(1) 오큰수

#include <iostream>
#include <stack>
#include <cstring>
 
#define pii pair<int, int>
using namespace std;
 
int N, NGE[1000001], arr[1000001];
stack<pii> stk;
 
int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> N;
    for(int i = 1; i <= N; i++){
        cin >> arr[i];
    }
    
    memset(NGE, -1, sizeof(NGE));
    
    int arrnow;
    pii stktop;
    
    for(int i = 1; i <= N; i++){
        if(stk.empty()) stk.push({arr[i], i});
        else{
            arrnow = arr[i];
            stktop = stk.top();
            while(stktop.first < arrnow){
                NGE[stktop.second] = arrnow;
                stk.pop();
                if(!stk.empty()) stktop = stk.top();
                else break;
            }
            
            stk.push({arr[i], i});
        }
    }
    
    for(int i = 1; i <= N; i++){
        cout << NGE[i] << " ";
    }
    
    return 0;
}
 

#include <iostream>
#include <stack>
#include <cstring>
 
#define pii pair<int, int>
using namespace std;
 
int N, NGE[1000001], arr[1000001], counting[1000001];
stack<pii> stk;
 
int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> N;
    for(int i = 1; i <= N; i++){
        cin >> arr[i];
        counting[arr[i]]++;
    }
    
    memset(NGE, -1, sizeof(NGE));
    
    int arrnow, countingnow;
    pii stktop;
    
    for(int i = 1; i <= N; i++){
        if(stk.empty()) stk.push({counting[arr[i]], i});
        else{
            arrnow = arr[i];
            countingnow = counting[arr[i]];
            stktop = stk.top();
            while(stktop.first < counting[arr[i]]){
                NGE[stktop.second] = arr[i];
                stk.pop();
                if(!stk.empty()) stktop = stk.top();
                else break;
            }
            
            stk.push({counting[arr[i]], i});
        }
    }
    
    for(int i = 1; i <= N; i++){
        cout << NGE[i] << " ";
    }
    
    return 0;
}
 

 

오등큰수를 풀기전 풀면 좋은 문제

(카운팅 정렬)

10989번: 수 정렬하기 3

 

이모티콘 처음 써본날