[백준/BOJ] 17298번: 오큰수 ( NGE, Next Greater Element ) - C++ 문제 풀이

 

문제 설명

 

문제 링크: https://www.acmicpc.net/problem/17298

 

풀이

이 문제는 입력된 A의 오큰수 NGE(A)를 구하는 문제입니다.

NGE( Next Greater Element )는 문제설명에도 있듯이, 숫자 A보다 크면서, A에 가장 가까운 숫자를 말합니다.

 

오큰수를 구하는 과정은 다음과 같습니다.

 

1. 첫 번째 숫자를 스택에 넣는다.

2. 그다음 숫자 A가 스택에 있는 숫자 X보다 크면, 스택에 있는 숫자 X의 NGE(X) = A이다.

    오큰수를 구했으므로 숫자 X를 스택에서 제거한다.

    이 과정을 스택에 있는 숫자가 A보다 작은 동안 반복한다.

    (참고로, 스택은 top에 있는 숫자만 꺼낼 수 있으므로, 스택에 있는 숫자는 top을 말합니다.)

3. 만일, 숫자 A가 스택에 있는 숫자보다 작거나 스택이 비워지면, A를 스택에 추가한다.

4. 입력된 다음 숫자에 대하여 2의 과정을 반복한다.

5. 모든 숫자를 비교한 후, 스택에 남아있는 숫자의 NGE는 -1이 된다.

 

스택 사용법에 관한 내용은 여기에 정리해 두었습니다.

[백준/BOJ] 28278번 : 스택 2 ( Stack 자료 구조 사용하기 ) - C++ 문제 풀이

 

예를 들어, 위의 예제 입력 1을 [ 3, 5, 2, 7 ] 위의 과정에 따라 처리하면 다음과 같습니다.

1. 스택에 3을 넣습니다.

2. 다음 숫자 5가 3보다 크기 때문에 NGE(3) = 5입니다.

    숫자 3을 스택에서 제거합니다.

3. 5를 스택에 넣습니다.

4. 2를 스택에 넣습니다.

 

2-1. 숫자 7이 2보다 크므로 NGE(2) = 7. 스택에서 2 제거.

2-2. 7이 스택에 있는 5보다 크므로 NGE(5)  = 7. 스택에서 5 제거.

3-1. 숫자 7을 스택에 넣습니다.

5. 모든 숫자를 전부 비교했으므로, 스택에 남아있는 7의 NGE(7) = -1입니다.

 

이 과정을 코드로 작성하면 다음과 같습니다.

vector<int> vec;
stack<int> buff;

for(int i = 0; i < N; i++){	// N은 입력받은 숫자의 수
    
    A = vec[i];	// 입력받은 숫자
    
    while ( !buff.empty()){
    
        int top = buff.top();
        
        if ( top < A){
            cout << A << " ";   // NGE 출력
            buff.pop();	// 스택에서 숫자 제거
        }
        else{
            break;
        }
    }

    buff.push(vec[i]);	// 스택에 숫자 입력
}

while( !buff.empty()){	// 스택에 남은 숫자들의 NGE는 -1 이다.
    buff.pop();
    cout << -1 << " ";
}

 

그런데, 한 가지 문제가 더 남았습니다.

문제에서는 NGE 출력 시, 입력받은 숫자의 순서대로 출력할 것을 요구하고 있습니다.

 

그래서, 숫자와 NGE를 pair로 구성해서, 모든 숫자의 NGE를 구한 후, 차례대로 출력을 해야 됩니다.

이를 구현하면 다음과 같이 바꿀 수 있습니다.

typedef pair<int, int> MPAIR;

int main(){

    int N, A;
    cin >> N;
        
    vector<MPAIR> vec;
    stack<MPAIR*> buff;	
    
    for(int i = 0; i < N; i++){
        
        cin >> A;

        MPAIR data(A, -1);	// NGE의 초기값을 -1로 
        vec.push_back(data);
    }

    for(int i = 0; i < N; i++){
        
        A = vec[i].first;
        
        while ( !buff.empty()){
            MPAIR* pTop = buff.top();
            
            if ( pTop->first < A){
                pTop->second = A;   // NGE 값을 구함
                buff.pop();
            }
            else{
                break;
            }
        }

        buff.push(&vec[i]);	// 스택에는 포인터를 저장해서 값을 변경할 수 있도록
    }
    
    // 스택에 남은 숫자의 NGE는 초기값 설정 시 이미 -1로 입력되었기 때문에
    // 다시, 값을 수정할 필요가 없습니다.

    for(int i = 0; i < N; i++){
        cout << vec[i].second << " ";	// NGE를 입력받은 순서대로 출력
    }

    return 0;
}

 

입력을 받는 시간이 너무 길기 때문에, 입력 시 한 번에 읽어오는 방식을 사용했습니다.

아래의 소스 코드에는 이 방식을 사용한 버전입니다.

중요한 것은 오큰수를 구하는 방식이므로, 입력을 받는 방식에 너무 집중할 필요는 없다고 생각합니다.

 

소스 코드

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

// 입출력 소스 --------------------------------------------
#define WBUF_SIZE (1 << 20)

char rbuf[WBUF_SIZE];
char wbuf[WBUF_SIZE];
int widx, ridx, nidx;

inline char read() {
	if (ridx == nidx) {
		nidx = fread(rbuf, 1, 1 << 20, stdin);
		if (!nidx) return 0;
		ridx = 0;
	}
	return rbuf[ridx++];
}
inline int readInt() {
	int sum = 0;
	char now = read();
	bool flg = false;

	while (now <= 32) now = read();
	if (now == '-') flg = true, now = read();
	while (now >= 48) sum = sum * 10 + now - '0', now = read();

	return flg ? -sum : sum;
}
int unitSize(int n) { // 자리 수
	if (n < 0)n = -n;
	int ret = 1;
	while (n >= 10) {
		ret++;
		n /= 10;
	}
	return ret;
}
void wbflush() {
	fwrite(wbuf, 1, widx, stdout);
	widx = 0;
}
void write(char c) {
	if (widx == WBUF_SIZE) wbflush();
	wbuf[widx++] = c; 
}
void writeInt(int n) {
	int isz = unitSize(n);
	if (isz + widx >= WBUF_SIZE) wbflush();

	if (n < 0) {
		wbuf[widx++] = '-';
		n = -n;
	}

	int next = widx + isz;
	while (isz--) {
		wbuf[widx + isz] = n % 10 + '0';
		n /= 10;
	}
	widx = next;
	write('\n'); // 구분자
}

//----------------------------------------------------------

typedef pair<int, int> MPAIR;

int main(){

    int N, A;
    N = readInt();	// 데이터를 한 번에 읽어오는 방식
        
    vector<MPAIR> vec;
    stack<MPAIR*> buff;
    
    for(int i = 0; i < N; i++){
        
        A = readInt();

        MPAIR data(A, -1);
        vec.push_back(data);
    }

    for(int i = 0; i < N; i++){
        
        A = vec[i].first;

        while ( !buff.empty()){
            MPAIR* pTop = buff.top();
            
            if ( pTop->first < A){
                pTop->second = A;   // NGE
                buff.pop();
            }
            else{
                break;
            }
        }

        buff.push(&vec[i]);
    }

    for(int i = 0; i < N; i++){
        writeInt(vec[i].second);
    }

    wbflush();

    return 0;
}