[코딩 테스트/백준 알고리즘] BOJ.1874 : 스택 수열 (Java 풀이)

문제

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

 

1874번: 스택 수열

---

문제 이해

나는 일단 이 문제 이해부터가 쉽지 않았다. 문제 아래 힌트를 보고 겨우 이해할 수 있었다.

테스트 케이스를 나타내면 아래 표와 같다. 

 

case 1

연산	스택	sNum	스택 수열 (4 3 6 8 7 5 2 1)
push(+)	{1}	4
push(+)	{1, 2}	4
push(+)	{1, 2, 3}	4
push(+)	{1, 2, 3, 4}	4
pop(-)	{1, 2, 3}	3	4
pop(-)	{1, 2}	6	4 3
push(+)	{1, 2, 5}	6	4 3
push(+)	{1, 2, 5, 6}	6	4 3
pop(-)	{1, 2, 5}	8	4 3 6
push(+)	{1, 2, 5, 7}	8	4 3 6
push(+)	{1, 2, 5 ,7 ,8}	8	4 3 6
pop(-)	{1, 2, 5, 7}	7	4 3 6 8
pop(-)	{1, 2, 5}	5	4 3 6 8 7
pop(-)	{1, 2}	2	4 3 6 8 7 5
pop(-)	{1}	1	4 3 6 8 7 5 2
pop(-)	{}		4 3 6 8 7 5 2 1

case 2

연산	스택	sNum	스택 수열 (1 2 5 3 4)
push(+)	{1}	1
pop(+)	{}	2	1
push(+)	{2}	2	1
pop(-)	{}	5	1 2
push(+)	{3}	5	1 2
push(+)	{3, 4}	5	1 2
push(+)	{3, 4, 5}	5	1 2
pop(-)	{3, 4}	3	1 2 5
pop(-)	{3}	3	1 2 5 4       <- NO

---

자료구조

Stack<Integer> s = new Stack<>();	//스택
int n = sc.nextInt();	//n
int[] arr = new int[n];	//스택 수열
StringBuilder sb = new StringBuilder();	//출력 문자열
int num = 0;	//1 ~ n까지 증가하는 수
int index = 0;	//스택 수열 인덱스
int sNum = arr[index];	//꺼내야 하는 수

 

구현

if (sNum > num) {
    s.push(++num);
    sb.append("+\n");
}

 1부터 수를 증가시키면서 스택에 수를 push한다. 이 때, num이 sNum(꺼내야 하는 수)보다 작으면 무조건 push해야 한다.

 sNum이 4라면, 스택에서 4를 꺼내기 위해선 우선 스택에 {1, 2, 3, 4}가 들어있어야 하기 때문이다.

if (sNum <= num) {
    if (s.peek() == sNum) {	//s의 top과 꺼내야하는 수가 같다
        s.pop();
        sb.append("-\n");
        if(index + 1 != n) {    //index가 n보다 크면 참조 오류 발생
            sNum = arr[++index];
        }
        else {
            break;
        }
    }
    else {	//s의 top과 꺼내야하는 수가 다르다
        System.out.println("NO");
        return;
    }
}

 num이 sNum보다 크거나 같으면  스택의 top에 sNum과 같은 수가 위치해있는지 확인한다. 두 수가 다르면 무조건 실패하는 케이스이기 때문에 단호하게 "NO"를 출력하고 종료한다.

s의 top과 꺼내야하는 수가 같은 경우 index의 범위에 따라 하는 행동이 다르다.

index + 1의 값이 n과 같다는 말은 스택 수열의 모든 수를 읽어왔기 때문에 배열이 텅텅 비어있다는 소리다. 이 경우 이미 스택 수열이 완성 되었기 때문에 반복문을 탈출한다.

 index + 1의 값이 n과 다르다는 말은 index + 1 < n과 사실상 같은 뜻이다. 이 경우 아직 스택에 꺼내야하는 수가 남아있기 때문에 배열에서 꺼내야 하는 다음 수를 가져온다.

---

코드

import java.util.*;

class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        Stack<Integer> s = new Stack<>();	//스택
        int n = sc.nextInt();	//n
        int[] arr = new int[n];	//스택 수열
        StringBuilder sb = new StringBuilder();	//출력 문자열
        int num = 0;	//1 ~ n까지 증가하는 수
        int index = 0;	//스택 수열 인덱스
        
        for(int i = 0; i < n; i++) {	//수열 입력 받기
            arr[i] = sc.nextInt();
        }
        
        int sNum = arr[index];

        while (true) {
            if (sNum > num) {
                s.push(++num);
                sb.append("+\n");
            }
            if (sNum <= num) {
                    if (s.peek() == sNum) {
                        s.pop();
                        sb.append("-\n");
                        if(index + 1 != n) {
                            sNum = arr[++index];
                        }
                        else {
                            break;
                        }
                    }
                    else {
                        System.out.println("NO");
                        return;
                    }
            }
        }
        System.out.println(sb);
    }
}

---

총평

오늘 이 문제 풀다가 벽 느꼈다. 저녁 먹고 유튜브 보려다가 심심해서 하나 풀려고 한건데 이상하게 막혔다.

침착하게 어디가 문제인지 파악하고 코드를 수정했어야 하는 건데 계속 안되길래 짜증나서 막 수정하다가 더 꼬여서 3번은 갈아엎었다. 침착하게 노트에 쓰면서 검토하는 버릇을 들여야할 거 같다.

 그리고 이번 글은 어떻게 써야할 지 모르겠어서 나름 열심히 설명을 한다고 했는데도 말이 잘 안 나온다. 그냥 코드 참고용으로만 봤으면 좋겠다.