1874) 15. 스택 : 스택 수열

 

문제

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

 

1874번: 스택 수열

 

풀이

   해결 방법은 입력된 수열 값과 일치할 때까지 값을 비교하며 스택에 넣다가, 일치하면 일치하지 않을 때까지 스택에서 빼는 것이다. 처음에는 값을 8번 입력하는 범위 안에서 임의로 넣어도 작동해야 하는 줄 알고 입력받은 값을 sort함수로 정렬시켜서 비교하려고 난리쳤는데 나중에 다시 보니 1부터 n까지 순서대로 값이 들어가는 것이었다. 풀기가 더 편해짐!

   vector를 사용하면서 이번에 알게 된 점은,

std::vector<int> a;
a.size();							// unsigned !

for(int i(0); i < a.size(); i++) { ... }		// the comparison isn't equal

라는 점이었다. vector는 a[i]와 같이 배열 만지듯 다루는 것이 가능하지만, 범위 반복을 할 때 위와 같이 비교하면 문제가 발생한다. XCode나 VS에서 돌리면 안된다고 하질 않아 문제가 없는 줄 알았는데 아니다!

int size(a.size());			// Implicit conversion loses integer precision

마찬가지로 위와 같이 int형으로 강제로 변환하려하면 XCode에선 저렇게 '암시적 형변환은 정수 정밀도를 잃습니다'라는 경고가 뜬다. 그 이유에 대해서는

 

• vector size를 int형과 비교하는 방법
• vector에서 unsigned를 다루는 방법(iterator를 활용하기)
• C++ Reference

 

여기를 참고. 요약하자면 vector의 size()는 명확히 말하면 unsigned긴 한데 unsigned int는 아니며 size_t도 아니다. 말 그대로 size_type인데 컴파일러에 따라 이걸 size_t와 같다고 보는 것도 있고, 아닌 것도 있다고 한다. 어쨌든 이게 단순한 int형이 아니므로 범위부터가 다르기 때문에 함부로 size_t로 단정짓거나 앞에 (unsigned int)로 강제 형변환하려하지 말고 iterator로 쓰던가, 아니면 vector<int>::size_type으로 변수형을 정해주자~

#include "iostream"
#include "vector"
#include "stack"
using namespace std;

// 일단 최대값이 될 때까지 push를 하다가, 4 3 6 8 7 5 2 1 이면 1 2 3 4'
// 최대값과 만나면 그다음 값과 일치하지 않을 때까지 pop 4 3
// 다시 push하다 일치하면 pop 1 2 6 -> 1 2 / 4 3 6
// 이랬는데 처음 수열과 일치하지 않으면 no, 일치하면 과정 출력
// 오름차순 정렬된 값을 가지고 스택에 쌓으면 될 듯.

bool isSequence(const vector<int>* seq, const int size, vector<char>* result) {
    stack<int> temp;
    for(int i(1), j(0); i <= size; i++) {
        // 값이 같을 때까지 push ( 1 2 3 4 //  4' 3 6 8 7 5 2 1 )
        temp.push(i);
        result->push_back('+');
        
        while(!temp.empty()) {
            if(temp.top() == seq->at(j)) {
                // 값이 다를 때까지 pop ( 1 2 // 4' 3' 6 8 7 5 2 1 )
                temp.pop();
                result->push_back('-');
                j++;
            }
            else break;
        }
    }
    
    if(!temp.empty()) return false;
    return true;
}

int main() {
    int repeat(0), data(0);
    vector<int> seq;
    vector<char> op;
    
    scanf("%d", &repeat);
    for(int i(0); i < repeat; i++) {
        // 일단 입력한 수열을 저장
        scanf("%d", &data);
        seq.push_back(data);
    }
    
    if(isSequence(&seq, repeat, &op)) {
        for(vector<int>::size_type i(0); i < op.size(); i++) printf("%c\n", op[i]);
    }
    else printf("NO\n");
    
    return 0;
}