[백준] 1874번 : 스택 수열 - JAVA [자바]

www.acmicpc.net/problem/1874

1874번: 스택 수열

 

 

---

• 문제

 

 

 

 

 

스택의 원리만 이해한다면 쉽게 풀 수 있는 문제다.

 

 

 

 

 

 

 

 

---

• 알고리즘 [접근 방법]

 

 

아마 이 문제를 처음 접한다면 무슨 말인가 할 수도 있겠지만, 이해만 한다면 정말 쉬운 문제다.

 

스택 자료구조는 본문에서도 나와있듯이 LIFO(후입선출) 특성을 갖고있다. 스택에 대한 기본적인 이해는 다음 포스팅을 참고하시길 바란다.

 

자바 [JAVA] - Stack (스택) 구현하기

 

 

 

그럼 문제를 살펴보도록 하자.

 

스택에 1 부터 n까지 수를 스택에 넣고(push) 빼는(pop) 과정을 통해 임의의 수열이 주어졌을 때 해당 수열을 만들 수 있는지를 판단하는 문제다.

 

이 때 스택에 수를 넣을 때(push)는 반드시 오름차순을 지켜야 한다.

 

무슨 말인가 이해하기 어렵다면 예제로 한 번 보면 이렇다.

 

 

 

이런 식의 과정을 거치게 된다.

 

 

그럼 어떻게 풀어야 할까?

 

예제에서의 처음 수열 입력값은 '4'다. (8은 입력의 개수이므로 제외)

그럼 1부터 4까지의 정수를 스택에 push한다.

 

	int start = 0;
	/* ------N번 반복----- */
	int value = input();
	if(value > start) {
	for(int i = start + 1; i <= value; i++) {
	stack.push(i);
	}
	start = value;
	}

 

그리고 숫자를 push 할 때는 반드시 오름차순이어야 하기 때문에 이전에 어디까지 입력 받았는지를 알기 위한 변수 start를  value 값으로 초기화 해주어야 한다. (4까지 push했기 때문에 다음에 push 할 경우 5 부터 push하기 위함이다.)

 

 

 

 

 

그런 다음 스택의 맨 위 원소가 입력받은 4와 같다면 pop을 해주고, 만약 같지 않다면 주어진 수열을 만족하지 못하는 것이므로 "NO" 가 된다.

int start = 0;


/* ------N번 반복----- */
int value = input();

if(value > start) {
for(int i = start + 1; i <= value; i++) {
stack.push(i);
}
start = value;
}

// top에 있는 원소가 입력받은 값과 같이 않은 경우
else if(stack.peek() != value) {
print("NO");
return; // 더이상 탐색 할 필요가 없으므로 프로그램을 종료시켜 버린다.
}

// value 값까지 push가 되어있다면 pop을 해준다.
stack.pop();

 

 

 

위 구조를 조금 가다듬어서 전체적으로 반복을 하면 된다.

 

전체적으로 보면 입력받은 value 값 까지 push 한 이력이 없을경우 stack에 value까지 push 한 후 마지막 원소를 pop해주면 되는 문제다. 참고로 결과적으로 출력해야 할 것은 + 또는 - 이므로 StringBuilder 을 사용하여 push할 땐 '+'를, pop할 때는 '-' 를 저장해준 뒤 만약 반복문이 정상적으로 끝날 경우 저장해둔 문자열을 한 번에 출력해주고, 그 외의 경우 이미 "NO"가 출력되어 프로그램이 종료된 상태이므로 출력될 일이 없다.

 

자세한 건 아래 풀이에서 알 수 있을 것이다.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

---

• BurreredReader + Stack으로 풀이하기

 

이전 포스팅과 여타 다를 바 없이 스택 라이브러리를 사용하는 방법과 배열을 선언하여 스택처럼 사용하는 방법을 보여주고자 한다.

 

 

 

 

 

 

---

• 풀이

- 방법 : [BufferedReader + StringBuilder]

 

 

 

입력 방법을 BufferedReader 을 사용하여 풀이하는 방법이다.

 

 

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

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

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();	// 출력할 결과물 저장

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

        int N = Integer.parseInt(br.readLine()); //입력할 숫자개수

        int start = 0;

        // N 번 반복
        while(N -- > 0) { //해당루프에서 N을 1씩 줄임 0보다 클때까지만 루프돔

            int value = Integer.parseInt(br.readLine());

            if(value > start) {
                // start + 1부터 입력받은 value 까지 push를 한다.
                for(int i = start + 1; i <= value; i++) { //4를 입력받으면 1부터 4까지 push
                    stack.push(i);
                    sb.append('+').append('\n');	// + 를 저장한다.
                }
                start = value; 	// 다음 push 할 때의 오름차순을 유지하기 위한 변수 초기화
            }

            // top에 있는 원소가 입력받은 값과 같이 않은 경우
            else if(stack.peek() != value) {
                System.out.println("NO");
                return;		// 또는 System.exit(0); 으로 대체해도 됨.
            }

            stack.pop();
            sb.append('-').append('\n');

        }

        System.out.println(sb);
    }
}

 

해당 글은 https://st-lab.tistory.com/182 에서 발췌하였습니다.