[백준_1874/JAVA] 스택으로 오름차순 수열 만들기

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

문제풀이

이 문제는 문제를 꼼꼼히 읽고, 예제를 손으로 써보며 이해하는것이 중요하다.

아직 코딩 테스트 초보여서 문제를 이해하는데도 꽤 어려웠다.

 

이 문제는 1부터 자연수를 증가시키면서 주어진 숫자와 비교하여 증가시킨 자연수를 스택에 push/pop 하는 방식으로 풀면 된다.
스택 연산은 2가지 케이스에 따라서 수행할 수 있다.

스택 연산 수행 방법

1. 현재 수열 값 >= 자연수

• 현재 수열 값이 자연수보다 크거나 같을 때 까지 자연수++ 하며 스택에 push 한다.
• 그리고 push가 끝나면 수열을 출력하기 위해 마지막 1회만 pop 한다.
• 예를 들어 현재 수열 값이 4면 스택에는 1,2,3,4를 push하고 마지막 1회만 pop하여 4를 출력하고 조건문을 빠져 나온다.

2. 현재 수열 값 < 자연수

• 현재 수열 값보다 자연수가 크다면 pop으로 스택에 있는 값을 꺼낸다.
• 꺼낸 값이 현재 수열 값이거나 아닐 수도 있다.
  • 만약 아니라면 후입선출 원리에 따라 수열을 표현할 수 없으므로, NO를 출력하고 문제를 종료한다.
  • 현재 수열 값이라면 그대로 조건문을 빠져 나온다.
• 1번의 예를 이어 설명하면 자연수는 5, 현재 수열 값은 3이므로, 스택에서 3을 꺼낸다.
• 현재 수열 값과 스택에서 꺼낸 값은 같으므로 계속해서 스택 연산을 수행할 수 있다. 스택에는 1,2가 남아 있고, 자연수는 5 이다.

슈도 코드

N(수열 개수) A[] (수열 배열)
수열 배열 채우기

for(N 만큼 반복){
    if(현재 수열 값>=오름차순 자연수){
        while(값이 같아질 때 까지){
            push()
            (+)저장
        }
        pop() (-)저장
    }
    else (현재 수열 값 < 오름차순 자연수){
        pop()
        if(스택 pop 결과값 > 수열의 수 ) NO 출력
        else (-) 저장
   }
 }
if(NO 값을 출력한 적 없으면) 저장한 값을 출력한다.

코드

package dataStructure;
import java.io.IOException;
import java.util.Scanner;
import java.util.Stack;

public class Main {
    public static void main(String[] args) throws IOException {
        Scanner sc=new Scanner(System.in);

        int N=sc.nextInt();
        int A[]=new int[N];

        for(int i=0;i<A.length;i++) {
            A[i]=sc.nextInt();
        }

        Stack<Integer> stack=new Stack<>();
        StringBuffer bf=new StringBuffer();

        int num=1; boolean result=true;

        for(int i=0;i<A.length;i++) {
            int n=A[i];

            if(n>=num) {
                while(n>=num) {
                    stack.push(num++);
                    bf.append("+\n");
                }
                stack.pop();
                bf.append("-\n");
            }
            else {
                int p=stack.pop();

                // 스택의 가장 위 수가 만들어야 하는 수열의 수 보다 크다면 수열 출력 불가
                if(p>n) {
                    result=false;
                    System.out.println("NO");
                    break;
                }
                else {
                    bf.append("-\n");
                }
            }
        }

        if(result) {
        System.out.println(bf.toString());
        }
    }

}