바킹독 0x05 문제3 / 백준 10773번 스택 수열

 

오늘 날씨가 시원했다.

가을은 정말 금방 가는 거 같다.

 

스택을 공부했으니 스택수열을 풀어보자.

 

---

 

 

아무리 읽어도 이해가 안가는 문제..

도대체 왜지

push를 4번해서 ++++인가.. 그렇다면 3이 될 때 - 한번 해야 하는데 두 번 한다..

도대체 무슨 패턴이지.. 하며

지선생에게 도움을 요청했다.

 

그의 말에 따르면

"저기 위에 1부터 n가지의 수를 스택에 넣었다가 뽑아 늘어놓음"

이걸 통해

1부터 차례대로 스택에 들어간다는 사실을 알 수 있고!

그래서 뽑았다가 늘어놓기 때문에

4 해서 push 4번

1,2,3,4 해주고

뽑아준다 했으니 pop이다. 그래서

top 해주고 pop을 해주기 때문에

1,2,3  4 출력

여기까지가

++++- 인 것!

내가 왜 4번 하고 3에 -이 두 번인가 했던 건 이 이유였던 거 같다.

 

자 그렇다면,

그다음에 3에서 한번 해줘야 하니

1,2  4,3 이 뽑히고

그다음에 위에서 중복되는 숫자가 없다고 했으니..

그다음에 들어올 숫자는 무조건 5이고

그러면 1,2,5 일 테니 +이고

다음 6까지니까!!!  1,2,5,6까지 두 번 ++ 더해주고

마지막에 또 빼서 1,2,5    4,3,6 이 되는 것

그래서 빼는 거까지 ++- 마지막에 - 이 필요하다!!

 

오케이 문제를 이해했습니다. ( 드디어 ) 

풀어보겠습니다.

 

뭔가 하나씩 풀어나가서 기뻤는데..

음.. 가장 중요한 예외처리가 안된다.

이게 그니까 예제 2처럼

1 2 5 3 4와 같이

맨 끝번호가 나온 뒤에는 내림차순으로 나와야 하는데..

왜냐! pop 하기 때문에 3에서 이미 4를 버렸는데 어째 다시 4를 가져오나..

그래서 이런 경우에는 NO를 출력해야 하는데..

문제는 어디에 이런 예외처리를 해줘야 하는가에 해결책이 안 나오고 있다. 

맨 앞에 해주면 s.top()은 값이 아무것도 안 들어있어서 런타임 에러 날 거 같고

중간에 넣자니.. 어디에 넣어야 할지 모르겠고

 

그러다가 좋은 자리를 찾았다.

사실 이건 좋은 자리라고 하긴 웃기지만 top에 맨 처음에 0을 넣어두고,

맨 처음에 if문으로 top가 입력 값보다 크다면 no를 출력하도록 넣었다.

 

그랬더니

+-+--+ NO 가 뜨더라..

이러면 안 되는데.. NO만 떠야 하는데!!

 

오늘은 답지를 보지 말자! 하며 시작했다.

그래서 뭔가 마무리를 짓고 싶어서 고민했다.

나의 긴 고민을 보던 조력자가

그럼 +-만 들어있는 칸을 하나 만들어주면 되잖아!

 

그렇군..

배열도 되나?라는 질문에

아니 벡터로 만들어

알겠어요!

 

그렇게 벡터로 넣어서

거기에 +-를 채워 넣고 마지막에 출력시켰다.

또한 

예외처리 거기는 return 0으로 탈출시켰다!

원래는 break였는데

이렇게 해주면 결국 for문이 돌아서 이상해진다.

그냥 아예 나가는 게 좋다!! 이 말!!

 

그래서 전체 코드는!

#include <bits/stdc++.h>
using namespace std;

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

    int n;
    cin >> n;

    stack<int> s;
    s.push(0);
    int cnt = 1;
    vector<string> v;

    while (n--)
    {
        int a;
        cin >> a;
        if (s.top() > a)
        {
            cout << "NO";
            return 0;
        }
        else
        {
            if (cnt <= a)
            {
                for (int i = cnt; i <= a; i++)
                {
                    cnt++;
                    s.push(i);
                    v.push_back("+");

                    if (i == a)
                    {
                        s.pop();
                        v.push_back("-");
                    }
                }
            }
            else
            {
                s.pop();
                v.push_back("-");
            }
        }
    }

    for (int i = 0; i < v.size(); i++)
    {
        cout << v[i] << "\n";
    }
}

선언해 주고

 

while를 돌며 구해주고,

no를 먼저 계산하게 하고 return까지

 

그다음에 cnt <=a 해서 더해주고

같아지면 빼주고 

cnt > a면 그냥 빼주고

 

 

그리고 마지막 출력

 

벡터 또한 하나씩 출력해줘야 한다고 한다!

 

 

오케이!

오늘 답지를 보지 않고 문제를 풀었다.

 

답지를 확인해 보니 나랑 굉장히 비슷했다.

하지만 내 거보다 쉬우면서도 어려웠다.

쉬운 느낌은 코드가 간결해 보였는데

뭔가 어려웠다.

vector로 안 쓰고 여기선 string로 쓰던데 그것도 신기했다.

 

조력자의 도움이 있었지만 ㅎ 답지 없이 풀어서 좋다.