EC.crew (2기) 8주차 정기 모임

스택과 큐

 

스택: 어떠한 자료를 쌓아서 올려놓은 형태의 자료구조 (후입선출)
큐: 데이터들이 일렬로 줄 서서 기다리는 형태의 자료구조 (선입선출)

 

---

1. 스택 수열 (백준 1874번)

 

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

 

#include <stdio.h>

int main()
{
    int n;
    scanf("%d", &n);

    int in[n], out[n], stack[n], pushpop[2*n];

    for(int x = 0; x < n; x++)
    {
        in[x] = x + 1;
        scanf("%d", &out[x]);
    }

    int maxindex = 0;

    for(int x = 1; x < n; x++)
        if(out[x] > out[maxindex])
            maxindex = x;
    
    for(int x = maxindex; x < n; x++)
        if(out[x] < out[x+1])
        {
            printf("NO");
            return 0;
        }

    int i = 0, j = 0, k = 0, l = 0;
    int no = 0;

    while(1)
    {
        while(1)
        {
            pushpop[l] = 1;
            l++;
            stack[k] = in[i];
            i++;
            if(stack[k] == out[j])
                break;
            k++;
        }
        while(stack[k] == out[j])
        {
            pushpop[l] = 0;
            l++;
            stack[k] = 0;
            k--;
            j++;
            if(j >= n)
                break;
            if(out[j] < in[i])
                if(out[j] != stack[k])
                    no = 1;
        }
        k++;
        if(j >= n)
            break;
        if(no == 1)
            break;
    }

    if(no == 1)
        printf("NO");
    else
    {
        for(int x = 0; x < 2*n; x++)
        {
            if(pushpop[x] == 1)
                printf("+\n");
            else
                printf("-\n");
        }
    }

    return 0;
}

어려웠지만 집 가기 전에 풀어서 뿌듯했던 문제!
처음에는 불가능한 경우를 배제하고, 가능한 경우에 대해서만 생각해서 초기 코드를 작성했다. 들어가는 수열, 즉 순서대로 정렬되어 있는 배열을 in으로 두고, 나오는 수열, 즉 입력받은 배열을 out으로 두고, 스택 안에 있는 배열을 stack으로 뒀다. 그리고 배열 in, out, stack의 변수를 각각 i, j, k로 설정했다.
패드에 나와있는 예시의 경우에 어떻게 진행되는지, 각각의 변수는 어떻게 변화하는지를 보면서 반복문을 적었다. 큰 반복문 안에 스택에 넣는 반복문, 스택에서 빼내는 반복문을 넣었다. 이렇게 가능한 경우에는 제대로 작동하는 코드가 완성되었다.
이제 불가능한 경우에는 NO를 출력하도록 해야 되는데, 처음에는 입력받은 수열에서 최댓값 기준으로 그 후의 숫자가 전부 내림차순 되어있으면 가능하지만, 하나라도 증가하는 부분이 있다면 불가능한 것이라고 생각했다. 그렇게 해서 코드를 작성하고 제출했더니 출력 초과로 틀렸다. (오답)
내가 불가능한 경우를 전부 고려하지 않아서 틀렸던 것이었다. 불가능한 경우를 전부 카운트하기 위해서는 다음과 같은 방법으로 추려야 한다. (은채가 알려줬다!)
1. 내가 out 배열 중 이번에 빼내고자 하는 목푯값이 in 배열에서 아직 스택으로 들어가지 않은 값들보다 작다면 (이런 경우에는 in 배열을 스택에 더 넣는다고 해결되는 것이 아니다.)
2. 그런데 그 값이 스택에서 제일 위에 있는 값, 즉 stack 배열에서 가장 뒤에 있는 값과 다르다면
그 경우는 불가능한 경우이다. 이렇게 이중 if문으로 불가능한 경우를 골라낼 수 있다.
이 과정에서 내 원래 코드에서 수정할 점이 또 보였다. 원래는 스택에 넣고 뺄 때 그때 그때 +와 -를 출력하도록 했는데, 그렇게 하면 불가능한 경우에 +, -는 출력하지 않고 NO만 출력해야 하는데 이렇게 하지 못 한다. 그래서 아예 pushpop이라는 배열을 만들어 +일 때는 1을, -일 때는 0을 저장했다. 그리고 no라는 변수를 만들어 불가능한 경우에 1을 저장하도록 했다. 그래서 마지막에 no가 1이면 0을 출력하고, 아니라면 pushpop을 출력하는데 1이면 +를 0이면 -를 출력하도록 해서 마무리했다. (정답)
이게 가장 효율적인 풀이가 맞는지는 의심스럽지만 난 풀었다는 것만으로도 너무 감격스러웠다..!!!