백준 Java 문제풀이 (45) 스택 수열

 

 

어려운 문제가 아닌데 설명이 어려웠다.

N까지의 임의 수열을 2번째 인풋으로 주고, 1부터 N까지의 연속된 자연수를 스택에 오름차순으로 넣으면서 해당 수열을 출력할 수 있도록 기호로 표시하라고 했으면 훨씬 쉬웠을 텐데.. 

 

스택은 모든 개발 언어 입문 시 list와 함께 가장 먼저 배우는 개념이니 모르는 사람은 없다고 가정하겠다.

pop은 제일 마지막에 입력된 값을 리턴하고 제거하며, peek은 리턴하고 제거하지 않는다. push는 넣는다. 끝.

(스택의 기본은 push와 pop이고 peek은 optional이다. 다만 peek을 사용하는 게 더 편하니까 난 쓸것임.)

 

순서가 뒤섞인 스택을 정렬하거나 혹은 정렬되어있는 스택으로 임의 수열을 만드는 문제는 기본적인 사고력과 자료구조에 지식 대한 기초 문제다.

다만 이미 완성되어 있는 스택을 정렬하는 문제와 달리 스택을 쌓음과 동시에 임의 배열을 생성하는 문제라서 조금은 머리를 더 써야한다.

 

 

1. 첫 번째 입력값 N을 입력 받는다.

2(택1). 반복문을 만들어 2번째 입력값부터 마지막 입력값까지 모두 모아서 배열을 만든다.

2(택1). 반복문을 만들어 해당 반복문 내부에서 입력값을 매번 한 번씩 받아오면서 비교한다.

3. 반복문 외부에서 반복 횟수를 카운트하며 스택에 push해줄 변수를 선언하고, 이 변수는 1회 반복할 때마다 1씩 증가해야 한다.

4. stack.push(count++) 이런 형태가 나올 텐데

- stack.peek() > 입력값(혹은 대응하는 배열 인덱스) => stack.pop()

- stack.peek() < 입력값(혹은 대응하는 배열 인덱스) => stack.push(count++)

- stack.peek() == 입력값(혹.대.배.인) => stack.pop()

이런 식으로 하면 되겠네요.

다만 주의할 점은 각 조건문의 위치입니다.

조건문 위치가 달라지면 출력값이 달라지는데 이건 알아서 하십시오.

 

 

이렇게 건방지게 주석으로 작성해놓고 문제 풀면 수도 코드보다 더 효율적이다.

난 진짜 이렇게 푼다.. ㅎ

 

아무튼 정답은 밑에 있읍니다.

위에서 알려주지 않은 것들

1. 조건문 순서

2. 조건문 형태

3. "+", "-" 기호 어떻게 출력할 것인지

4. "NO" 어떻게 구할 것인지 (힌트 : 다른 방법도 많지만 배열 하나 만들어서 사이즈 체크하면 편하다.)

 

이 네 가지만 해결하면 정답이다.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

import java.util.*;
import java.io.*;
 
public class Main {
    public static void main(String[] args) throws Exception {
//        첫 번째 줄 수열 개수 N
//        1개의 줄에 수열 이루는 1 이상 n이하 정수
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        Stack<Integer> stack = new Stack<>();
        StringBuilder sb = new StringBuilder();
        int[] num = new int[N];
 
        for(int i=0; i<N; i++) {
            num[i] = Integer.parseInt(br.readLine());
        }
 
        int count = 1;
        ArrayList<Integer> temp = new ArrayList<>();
 
        for(int i=0; i<N; i++) {
 
            while (stack.size()==0 || num[i] > stack.peek()) {
                stack.push(count++);
                sb.append("+").append("\n");
            }
 
            while (stack.size()!=0 && stack.peek() > num[i]) {
                stack.pop();
                sb.append("-").append("\n");
            }
 
            while (stack.size()!=0 && stack.peek() == num[i]) {
                temp.add(stack.pop());
                sb.append("-").append("\n");
            }
 
            if (temp.size() == N) {
                break;
            }
        }
 
        if (temp.size() != N) {
            System.out.println("NO");
        } else {
            System.out.println(sb);
        }
    }
}