[백준] 스택 수열_1874_자바

스택 수열 (1874)

---

이번 포스팅은 백준의 1874번 문제 [스택 수열]에 대해서 다루려고 합니다. 이름에서도 알 수 있듯이 문제의 분류는 스택에 해당합니다. 아래에 해당 문제에 대한 내용이 적혀있는데요. 상당히 애매하게 적혀있습니다. 그래서인지 문제를 이해하는데 어려움을 느낄 수 있습니다. 아래 풀이에서 자세하게 알아보도록 하겠습니다.

---

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

1874번: 스택 수열

 

1) 문제

2) 입, 출력

3) 예제 입, 출력

첫 번째 예제

두 번째 예제

---

풀이

---

먼저 문제를 해석해보겠습니다. 정수 N이 주어졌을 때, 스택을 통해서 1부터 N까지의 수열을 만들 수 있습니다. 

위에 첫 번째 예제의 입출력을 보도록 하겠습니다. 첫 줄이 정수 N에 해당합니다. 그리고 둘째 줄부터 1 이상 N 이하의 정수가 중복되지 않은 채 입력됩니다. 즉, [4, 3, 6, 8, 7, 5, 2, 1] 이라는 수열을 입력한 것이죠. 이제 스택에 1부터 N까지 오름차순으로 PUSH와 POP을 진행하는데요. 이렇게 연산을 마쳤을 때 우리가 입력했던 [4, 3, 6, 8, 7, 5, 2, 1] 형태의 수열이 완성되어야 합니다.

원리는 이렇습니다. 

1부터 N까지 스택에 PUSH를 하는데요. PUSH를 할 때는 연산자가 '+' 입니다. 그리고 우리가 입력했던 수열에 해당할 때 POP을 합니다. 그 이유는 Result에 우리가 입력했던 수열과 동일하게 만들기 위해서입니다. POP을 할 때 연산자는 '-' 입니다. 따라서 스택에서 모든 값을 꺼내면, Result는 우리가 입력했던 수열의 형태로 완성됩니다. 그리고 과정을 진행하며 나왔던 연산자를 출력하는 것입니다.

결과는 [ +, +, +, +, -, -, +, +, -, +, +, -, -, -, -, - ] 가 출력됩니다.

 

하지만 반례도 있습니다. Result 에 우리가 입력했던 형태의 수열이 완성되지 못하는 경우입니다. 그것이 위에서 보이는 두 번째 예제 상황인데요. 즉, 입력한 수열의 형태를 만들기 위해 스택에서 POP을 해야 하지만, 원하는 값이 제일 위에 있지 않다면 POP을 할 수가 없습니다. 이때는 NO라는 문자열을 출력합니다. 이제 코드를 보도록 하겠습니다.

 

1) 코드 구현

• 제한 시간 2초
• BufferedReader, StringBuilder 사용
• Stack 사용

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;

/**
 * 1~N 까지의 스택 생성
 * push와 입력한 수열처럼
 *
 * 수행시간 332ms
 */
public class StackSequence_1874 {

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

		// 정수 N 입력
        int N = Integer.parseInt(br.readLine());
        // 1부터 N까지 오름차순으로 쌓을 스택
        Stack<Integer> currStack = new Stack<>();

		//스택에 가장 위에 있는 값
        int top = 0;

        while (N > 0) {

			// 수열 입력
            int input = Integer.parseInt(br.readLine());
			
            // 입력한 값이 top보다 크다면,
            if (input > top) {
				
                //스택에 Push하고, sb에 + 를 append
                for (int i = top + 1; i <= input; i++) {
                    currStack.push(i);
                    sb.append('+').append('\n');
                }
                
                // 입력한 값이 스택의 가장 위에 위치한 값이 되므로, top에 대입
                top = input;
            
            // 반례 : 스택에서 가장 위에 있는 값이 input과 같지 않다면,
            } else if(currStack.peek() != input) {
            
            	// 결과로 NO를 출력하고 프로그램 종료
                System.out.println("NO");
                return;
            }

            // input 만큼 넣었으면 스택에서 가장 위에 데이터를 꺼냄
            // 또는 input 값이 index 보다 작으면, 스택에서 바로 값을 꺼냄
            currStack.pop();
            sb.append('-').append('\n');

            N--;
        }
        
        System.out.println(sb);
    }
}

 

2) 나만의 방법으로 작성한 코드

1) 입력한 수열을 배열에 넣음
2) 배열 안에 값이 스택에 있을 때까지 1부터 오름차순으로 PUSH 진행
3) 스택에 값이 있다면, 가장 위에 있는 값인지 체크하고 POP
4) 배열의 인덱스를 +1 하고, 해당 위치에 값이 스택에 있다면 반복을 통해서 POP 진행
5) 만약 해당 배열의 값이 스택의 가장 위에 있지 않다면, 반례로 NO 출력 후 프로그램 종료

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;

/**
 * 처음 풀이
 *
 * 수행 시간 4140 ms
 */
public class StackSequence_1874_2 {

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int N = Integer.parseInt(br.readLine());
        Stack<Integer> stack = new Stack<>();
        int[] sequenceArr = new int[N];

        for(int i = 0; i < N; i++) {

            sequenceArr[i] = Integer.parseInt(br.readLine());
        }

        int value = 1;
        int i = 0;

        while(value<=N) {

            stack.push(value);
            sb.append("+").append("\n");

            while(stack.contains(sequenceArr[i])) {
                if (stack.peek() == sequenceArr[i]) {
                    stack.pop();
                    sb.append("-").append("\n");
                    i++;

                    if(i > N-1) {
                        break;
                    }
                } else {
                    System.out.println("NO");
                    return;
                }
            }

            value++;
        }


        System.out.println(sb);


    }
}

두 번째 코드는 첫 번째에서 작성한 코드와 문제 접근은 거의 유사했습니다. 하지만 4140ms라는 어마어마한 시간이 발생했습니다. 제한시간이 2초인데 맞았다는 게 의아합니다. 이렇게 차이가 발생한 이유는 첫 번째 코드에서는 while을 한 번만 쓴 반면, 두 번째 코드에서는 while을 두 번이나 쓰고 있죠. 심지어 배열에 값을 넣고, 빼고를 하며 많은 시간이 발생한 것 같습니다.

점점 문제의 난이도가 높아질수록 시간과 메모리 제한이 까다로워지네요. 앞으로 조금 더 효율적인 방법으로 코드를 작성하는 연습을 해야할 것 같습니다.