/<BOJ 백준 1874번> 스택 수열 - Java

문제 1874번 : 스택 수열

문제 해설

본 문제의 이름과 본문에서는 스택을 이용하라는 내용이 제시되어있다. 따라서 자료구조 스택을 이용하여 이 문제를 해결해 보려고 한다. 다른 복잡한 조건이 없으므로 문제 해결 아이디어는 다음과 같다.

1. 주어진 정수 n에 대하여 1부터 n까지의 수열을 스택에 추가(push)한다.
2. 스택의 top에 있는 숫자와 입력받은 정수가 같을 때까지 스택에서 삭제(pop)한다.
3. 1번과 2번 과정으로 수열을 만들 수 있는 경우 push와 pop한 과정을 각각 "+"와 "-"로 나타낸다.
3-1. 수열을 만들 수 없는 경우 "NO"를 출력한다.

 

이를 코드로 구현하면 다음과 같다.

 

int[] sequence = new int[n];
int currentNumber = 1;

for(int i = 0; i < n; i++) {
    sequence[i] = Integer.parseInt(br.readLine());
}

for (int number : sequence) {
    while (currentNumber <= number) {
        stack.push(currentNumber);
        sb.append("+\n");
        currentNumber++;
    }

    if (stack.peek() == number) {
        stack.pop();
        sb.append("-\n");
    } else {
        System.out.println("NO");
        return;
    }
}

 

입력받은 수를 정수형 배열 sequence에 저장한다. currentNumber = 1로 지정하고 sequence 내부에 있는 정수의 개수만큼 1씩 추가하여 스택에 추가(push)한다. stack 내장 메소드 peek()과 pop()은 둘다 스택의 최상단(top)의 값을 반환하는 공통점이 있지만 peek()는 스택에서 삭제하지 않고 pop()은 해당 값을 반환하고 스택에서 삭제한다. 

 

해당 코드의 시간복잡도에 대해 알아보자. sequence 배열에 정수를 추가하는 for 반복문은 n에 따라 수행 시간이 다르므로 시간복잡도 O(n)을 갖는다.  stack 내장 메소드 push(), pop(), peek()는 모두 시간복잡도 O(1)을 갖는다. 따라서 코드 전체적으로 시간복잡도 O(n)을 갖는다.

코드

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

public class Main {

    public void solution() throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        Stack<Integer> stack = new Stack<>();
        StringBuilder sb = new StringBuilder();
        int[] sequence = new int[n];
        int currentNumber = 1;

        for(int i = 0; i < n; i++) {
            sequence[i] = Integer.parseInt(br.readLine());
        }

        for (int number : sequence) {
        while (currentNumber <= number) {
            stack.push(currentNumber);
            sb.append("+\n");
            currentNumber++;
        }

        if (stack.peek() == number) {
            stack.pop();
            sb.append("-\n");
        } else {
            System.out.println("NO");
            return;
        }
    }

    	System.out.println(sb);
    }

    public static void main(String[] args) throws Exception{
    	new Main().solution();
    }
}