화투의 개발 블로그

[문제 링크]

스택을 이용하면 쉽게 푸는 문제이다.

나는 입력 받으면서 스택에서 체크하여 값을 출력하는 방식으로 풀었다.

값을 입력받으면, 스택을 체크한다. 스택을 체크해서 스택이 비었으면 그 탑 왼쪽에는 탑이 없는 것이므로 0을 출력한다.

탑이 있을 경우, 현재 입력받은 탑의 높이와, 스택의 top에 있는 탑의 높이를 비교한다. 만약 값의 크기가 현재 탑보다 작으면, 스택을 pop하여 다음 값을 다시 비교한다.

top에 저장된 높이 값이 현재 입력받은 높이값보다 같거나 클경우, 혹은 스택이 비었을 경우까지 이를 반복한다. top의 값이 같거나 클 경우에는 top의 인덱스를 출력하고, 비었으면 0을 출력한다.

그 다음에 현재 입력받은 값을 탑의 인덱스와 함께 스택에 push한다.

문제에 제시된 예제를 통해 예를 들어보겠다.

5
6 9 5 7 4

현재 스택은 비어있는 상태이다.

1. 먼저 6을 입력 받는다. 스택을 체크한다. 현재 스택에 삽입된 값은 없다, 콘솔에 '0'을 출력하고, 스택에 탑의 인덱스와 크기를 pair로 묶어 삽입한다.

출력 : 0

스택 : (1,6)

2. 그 다음 9를 입력받는다. 스택을 체크한다. top에 있는 값의 크기는 6이다. 현재 입력받는 9보다 작으므로 스택을 pop한다. 

출력 : 0

스택 :

그리고 다시 스택을 체크한다. 스택이 비어있다. 콘솔에 '0'을 출력하고, 입력받은 값을 삽입한다.

출력 : 0  0

스택 : (2,9)

3. 다음은 5이다. 스택을 체크한다. top에 있는 값은 9이고 현재 입력값보다 크다. top에 있는 인덱스를 출력하고 스택에 입력값을 push한다.

출력 : 0  0  2

스택 : (2,9)  (3,5)

4. 다음은 7이다. 스택을 체크한다. top에 있는 값은 5이고 현재 입력값보다 작다. 스택을 pop한다.

출력 : 0  0  2

스택 : (2,9)

그리고 다시 스택을 체크한다. top에 있는 높이 값은 9이다. 입력값인 7보다 크므로 top의 인덱스를 출력하고 스택에 push한다.

출력 : 0  0  2  2

스택 : (2,9)  (4,7)

5. 마지막으로 4이다. 스택 top을 체크하는데 top의 값은 7이고 입력값보다 크다. 인덱스를 출력하고 스택에 push한다.

출력 : 0  0  2  2  4

스택 : (2,9)  (4,7)  (5,4)

5번 반복했으므로 반복문이 끝나고 프로그램을 종료한다.

즉 스택에는 이전값중의 가장 큰 값과, 현재 값 사이에 있는 값들은 전부 없앤다고 보면 된다.

이를 구현한 코드는 다음과 같다.

#include <cstdio>
#include <stack>
#include <utility>
using namespace std;
int n, k;
stack<pair<int, int> > st;
int main() {
    scanf("%d", &n);
    for (int i = 1; i<=n; i++) {
        scanf("%d", &k);
        while (!st.empty()) {
            //스택의 top이 현재 입력값보다 크다면 신호 수신 가능이므로 
            if (st.top().second > k){
                //top의 위치를 출력하고 반복문을 탈출한다. 
                printf("%d ", st.top().first);
                break;
            }
            st.pop();
        }
        //스택이 비었으면 0을 출력한다. 
        if(st.empty()) printf("0 ");
        //그리고 현재 탑을 스택에 push 
        st.push(make_pair(i, k));
    }
}

[문제 링크]

문제 의도는 스택으로 푸는 문제이지만, 굳이 스택으로 풀지 않아도 되는 문제이다.

그냥 레이저를 만났을 때, 여는 괄호의 갯수 만큼 더해줘도 되지만, 여기서는 스택을 이용해서 풀어보겠다.

이 문제를 풀기 위해선, 닫는 괄호가 나타났을 때, 이 것이 레이저인지, 아니면 파이프의 끝을 나타내는 것인지 구별해야 된다.

구별하는 방법은 정말 쉽다, 닫는 괄호가 나타났을 때, 바로 전 문자를 체크해서 이게 여는 괄호인지 아닌지만 확인하면 된다.

즉 여는 괄호를 만나면 전부 스택에 push하다가, 닫는 괄호를 만나면 스택에서 pop하고 괄호가 레이저면 스택 사이즈만큼 더해주거나, 파이프 끝이면 1만 더해주면 된다.

위 사진으로 예를 들어보자. 

처음에 '('를 만나서 스택에 push한다, 그리고 두번째에 ')'를 만난다. 스택에서 '('를 pop한다. 이전 문자는 '('이므로 레이저이다. 결과값에 스택 사이즈(0)만큼 더해준다.

result += 0

그다음 '('를 4개 만난다. 스택에 '('가 4개 들어가고 스택 사이즈는 4이다. ')'를 만나서 스택을 pop한다. 바로 전이 '('이므로 이는 레이저이다. 결과값에 스택 사이즈(3)만큼 더해준다.

result += 3

바로 다음에 괄호를 다시 여닫고 스택을 그에따라 push,pop해준다. 레이저이므로 스택 사이즈(3)을 다시 더해준다.

result += 3

닫는 괄호를 만난다. 바로 전 문자는 ')'이므로 레이저가 아닌 파이프의 끝이다. 파이프 꼭다리가 남으므로 1을 더해준다.

result +=1

위의 방법을 계속 반복하면 된다. 나머지는 직접 해보자.

이를 구현한 코드는 다음과 같다.

#include <iostream>
#include <string>
#include <stack>
using namespace std;
string str;
int pipe(const string& str){
    stack<char> st;
    int result=0;
    for(int i =0; i<str.length();i++){
        //여는 괄호면 스택에 넣는다. 
        if(str[i]=='(') st.push(str[i]);
        //닫는 괄호면 이 괄호가 레이저인지, 파이프 끝인지 알아본다.
        else{
            st.pop();
            //레이저면 
            if(str[i-1]=='(') 
                result += st.size(); //잘린 갯수 추가. 
            //파이프의 끝이면 
            else result++; //닫혀서 잘려진 갯수 추가. 
        }
    }
    return result;
}
int main(){ 
    cin >> str;
    cout<<pipe(str);
}