[Beakjoon, C++] 17298번 : 오큰수

백준 단계별 풀기에서 스택 6번째 마지막 문제이다.

링크는 아래와 같다.

www.acmicpc.net/problem/17298

17298번: 오큰수

---

백준 17298번 문제, 입력, 출력

---

백준 입출력 예제 1,2

---

 '시간 초과'로 인해서 꾀나 고생한 문제였다. 처음으로, 프로그램의 결과물을 만들어내는 것뿐만 아니라, 효율적인 프로그래밍은 어떤 것인가에 대한 고민을 해보았던 문제였다.

 처음 디자인한 것은, N만큼 숫자를 받으면 vector<int> 변수(a)와 stack<int> 변수(b)를 선언하고 각각 push하였다. 또, 결과값을 저장할 vector변수(c)를 선언하였다. a는 나중에 for문으로 처리 할 때 기준을 담당하기 위함이고, b는 for문 처리 할 때 기준으로 부터 숫자들을 top pop하면서 크기를 비교할 예정이였다. 입출력 예제 1을 예로 들어, a[1]=3 일 때, b.top()과 b.pop()을 사용해, 7 2 5가 3보다 큰지 작은지를 비교하여 크다면 c에 넣는 방식을 이용하였다. 하지만, 이렇게 되면 변수 b가 한번씩 처리할 때 마다, 값이 바뀌게 되어서, a가 바뀔 때마다 새로운 stack<int> 변수(d)를 선언하여 b를 넣어주고 a와 d를 비교하는 방식으로 구현을 하였다.

---

 

#include<iostream>
#include<stack>
#include<vector>

using namespace std;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int sizeOfsequence;
    int num;
    int firstNum;
    stack<int> st;
    vector<int> stNum;
    vector<int> rightFirstBig;

    cin >> sizeOfsequence;

    for (int i = 0; i < sizeOfsequence; i++) {
        cin >> num;
        
        st.push(num);
        stNum.push_back(num);
    }

    for (int i = 0; i < sizeOfsequence; i++) {
        stack tst;
        tst = st;
        int rightNum = tst.top();
        int rightBigNum = -1;
        firstNum = stNum[i];
        for (int j = sizeOfsequence - 1 - i; j > 0; j--) {
            if (firstNum < rightNum) {
                rightBigNum = rightNum;
            }
            tst.pop();
            rightNum = tst.top();
        }
    
        rightFirstBig.push_back(rightBigNum);
    }

    for (int x : rightFirstBig) {
        cout << x << " ";
    }
    
    return 0;
} 

---

하지만, 결과는 다음과 같이 '시간 초과' 였다. 연산을 더 적게 하는 시간이 초과하지 않는 방법이 있다는 것이다. 

---

 어떤 방법이 있을까 한참을 고민했었다. stack<int> 변수(tst)를 굳이 사용해야 할까? 계속해서 복사해서 쓰기 때문에 sizeOfSequence가 커지면 그만큼의 메모리를 계속해서 만들어주기 때문에 속도가 오래 걸릴 것 같았다. 그렇다면 스택을 복사 하지 않고, 입력 받은 수열을 각각 한개씩 처리해서 rightFirstBig에 넣어주는 것이 아니라, 한번의 처리 과정에서 결과를 모두 구해서 넣어주어야 할 것이다.

 그렇다면 stack 변수에 수열을 넣어두고 꺼내서 비교하는 것이 아닌, stack 변수(stIndex)에 vector 변수(numSeqVector)의 위치를 저장해서 while문으로 처리를 해주었다.

---

 

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

int main()
{
	int sizeOfsequence;
	int num;
	vector<int> numSeqVector;
	stack<int> stIndex;

	scanf("%d", &sizeOfsequence);

	for (int i = 0; i < sizeOfsequence; i++) {
		scanf("%d", &num);
		numSeqVector.push_back(num);
	}

	vector<int> rightFirstBig(numSeqVector.size(), -1);

	for (int i = 0; i < numSeqVector.size(); i++) {
		while (!stIndex.empty() && numSeqVector[stIndex.top()] < numSeqVector[i]) {
			rightFirstBig[stIndex.top()] = numSeqVector[i];
			stIndex.pop();
		}
		stIndex.push(i);
	}

	for (int x : rightFirstBig) {
		cout << x << " ";
	}

	return 0;
}

 

이상으로 17298번 마지막 스택 문제를 마치겠다.