[백준] 스택 수열 JAVA

728x90

반응형

[백준] 스택 수열

1874번: 스택 수열 (acmicpc.net)

---

접근

• 스택

---

풀이

문제의 제목에부터 스택이 들어가는 스택 문제이다. 도대체 백준에 문제 설명들은 왜 다 이런 모양인지 이해가 가질 않는다. 저 설명을 보고 이해해서 문제를 풀려면 출제자쯤 돼야 하지 않나 싶다. 문제를 읽어봐도 이해는 가지 않고 내가 아는 수열이 아닌 건가 싶고 예시 케이스를 봐도 뭔 짓을 한 건지 도저히 이해가 가질 않아서 질문 게시판을 찾아봤다. 질문 게시판에서 누군가 유튜브에 해당 문제 해설을 올려둔 걸 보고 나서야 문제를 이해했다. 해설을 보고 나니 그걸 이해한 사람도 신기하고 문제가 저건데 설명을 이렇게 올린 사람도 참 신기했다.

 

문제는 주어지는 입력을 스택을 가지고 처리할 수 있는지 없는지를 구하는 문제이다. 예제 입력인 4, 3, 6, 8, 7, 5, 2, 1에 대해 보면 첫 입력인 4의 처리를 위해 스택에는 1부터 4까지 순차적으로 스택에 들어가게 된다.

Stack

4

3

2

1

 

그리고 입력받은 수인 4를 스택에서 꺼낸다.

Stack

3

2

1

 

그렇게 스택에는 1,2,3이 남게 되고 입력받은 수 4 처리를 위해 push 연산이 4번 +,+,+,+ 그리고 4를 꺼내주는 pop 연산이 한 번으로 입력받은 숫자 4에 대한 처리 결과는 +,+,+,+,-가 된다. 그리고 다음 3을 처리해야 하는데 3의 경우 스택의 최상단에 존재하므로 pop연산, - 한 번으로 처리가 끝난다.

Stack

2

1

 

현재 3까지의 입력 처리가 끝나고 스택에는 1,2가 남아있는 상황에서 다음 숫자 6을 처리하려면 문제 내용대로 라면 누구라도 스택에 3, 4, 5, 6을 채우는 + 연산을 4번 하고 6을 꺼내는 - 연산을 한 번 해서 6의 처리로 +,+,+,+,-를 할 것이다. 그런데 예제 결과 출력에서 6의 처리로 +,+,- 밖에 없는 걸 볼 수 있다. 여기서 숨어있는 이상한 조건이 하나 있는데 스택에 채우는 숫자도 전부 한 번만 쓸 수 있다고 생각을 해야 한다. 아까 첫 입력으로 4를 채우면서 1, 2, 3, 4를 한 번씩 썼기 때문에 스택에 넣을 수 있는 숫자는 5부터로 6 처리를 위해 5,6이라는 숫자 두 개만 스택에 들어가기 때문에 +연산이 두 번밖에 일어나지 않았던 것이다.

Stack

6

5

2

1

 

이렇게 두 번의 + 연산이 발생하고 

Stack

5

2

1

 

한 번의 - 연산이 발생한다. 이런 조건이 있는걸 왜 문제 설명이 아닌 예시 출력을 보고 분석을 해야 하는 건지 모르겠지만 이런 식으로 모든 입력받는 수 처리가 된다면 그 숫자들을 스택 수열이라 부를 거다라는 문제였다.

int n = Integer.parseInt(br.readLine());
Stack<Integer> stk = new Stack<>();
StringBuilder sb = new StringBuilder();

int max = 0;

어이없음을 뒤로하고 사용할 스택과 출력을 위한 문자열을 만들 StringBuilder와 저렇게 스택에 넣을 값을 어디까지 사용했는지를 체크할 변수 하나를 선언했다.

for (int i = 0; i < n; i++) {
	int num = Integer.parseInt(br.readLine());

	if(stk.isEmpty()){
	   for (int j = max + 1; j <= num; j++) {
		   stk.push(j);
		   sb.append("+\n");
	   }
	max = num;
	sb.append("-\n");
	stk.pop();
	}

스택이 비어있을 때 넣어주는 조건이다. 현재 최댓값을 기준으로 그 값 다음값부터 입력받는 값까지 넣어준다. StringBuilder에는 꾸준히 연산값을 넣어주고 push가 끝나면 최댓값을 최신화하고 pop 연산을 수행한다.

if(!stk.isEmpty() && max < num && stk.peek() < num){
   for (int j = max+1; j <= num; j++) {
      stk.push(j);
      sb.append("+\n");
   }
   max = num;
   sb.append("-\n");
   stk.pop();
}

스택에 수가 들어있고 최댓값이 입력받는 수 보다 작고 스택의 최상단도 입력받는 수 보다 작을 때다. 예시 케이스에서 스택에 1,2 가 있고 처리했던 최댓값이 4, 입력받는 수가 6인 경우를 생각하면 된다. 처리했던 최댓값 다음값부터 입력받는 값까지 push 해주고 최댓값을 최신화하고 pop 연산을 한다. 위의 케이스와 수행 내용을 똑같다.

else if (!stk.isEmpty() && stk.peek() > num) {
   for(int j = stk.peek(); j > num; j=stk.peek()){
      stk.pop();
      sb.append("-\n");

   }
}

스택이 비어있지 않고 스택 최상단이 입력받은 수 보다 클 때이다. 최상단부터 입력받은 수가 나올 때까지 pop 연산을 해준다.

else if(!stk.isEmpty() && max > num && stk.peek() < num){
   sb.setLength(0);
   sb.append("NO");
   break;
   }

스택이 비어있지 않고 최댓값이 입력값 보다 크고 스택 최상단이 입력 값보다 작을 때이다. 처리했던 최댓값이 6이고 입력값이 4인데 스택의 최상단이 2일 경우이다. 4를 처리하기 전 3을 먼저 처리했다면 3을 처리하는 과정에서 4가 pop 되어 처리가 불가능한 경우이다. 더 이상 진행이 불가능하기 때문에 StringBuilder에 쌓아둔 연산들을 모두 제거하고 NO를 넘긴 뒤 반복을 종료한다.

else if (!stk.isEmpty() && stk.peek() == num) {
   sb.append("-\n");
   stk.pop();
}

제일 간단한 경우이다. 현재 스택의 최상단이 입력값일 경우 pop 연산 한번 수행하고 끝난다.

---

전체 코드

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = Integer.parseInt(br.readLine());
        Stack<Integer> stk = new Stack<>();
        StringBuilder sb = new StringBuilder();

        int max = 0;
        for (int i = 0; i < n; i++) {
            int num = Integer.parseInt(br.readLine());

            if(stk.isEmpty()){
                for (int j = max + 1; j <= num; j++) {
                    stk.push(j);
                    sb.append("+\n");
                }
                max = num;
                sb.append("-\n");
                stk.pop();
            }

            if(!stk.isEmpty() && max < num && stk.peek() < num){
                for (int j = max+1; j <= num; j++) {
                    stk.push(j);
                    sb.append("+\n");
                }
                max = num;
                sb.append("-\n");
                stk.pop();
            }
            else if (!stk.isEmpty() && stk.peek() > num) {
                for(int j = stk.peek(); j > num; j=stk.peek()){
                    stk.pop();
                    sb.append("-\n");

                }
            }
            else if(!stk.isEmpty() && max > num && stk.peek() < num){
                sb.setLength(0);
                sb.append("NO");
                break;
            }
            else if (!stk.isEmpty() && stk.peek() == num) {
                sb.append("-\n");
                stk.pop();
            }
        }

        bw.write(sb.toString());
        bw.flush();
        bw.close();
        br.close();
    }
}

문제를 풀면서 생각을 하다보니 빠트린 조건이 생각나서 추가하고 수정하고 코드가 깔끔하지 않다. 아마 필요없는 조건이나 훨씬 간결하게 만들 수 있을 거지만 문제가 참 맘에 들지 않는다. 문제 설명이 너무나도 이상해 들고와본 문제이고 이 문제를 마지막으로 class 2의 문제를 모두 풀었다. 이제 class 3의 문제로 넘어가면 좀 더 복잡해진 문제들이 나올 텐데 설명이 어떻게 되어있을지 참 두렵다.