솜이의 데브로그

백준 1874번 ) 스택 수열 (java) 본문

Algorithm/백준

백준 1874번 ) 스택 수열 (java)

somsoming 2022. 2. 22. 21:46

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

 

1874번: 스택 수열

1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다.

www.acmicpc.net

 

문제

 

풀이

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

public class BOJ_1874 {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int n = Integer.parseInt(br.readLine());
        int start = 0;

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

        while(n-->0){
            int value = Integer.parseInt(br.readLine());
            if(start<value){
                for(int i= start+1 ; i<= value; i++){
                    stack.push(i);
                    sb.append('+').append('\n');
                }
                start = value;
            }
            else if(stack.peek() != value){
                System.out.println("NO");
                return;
            }

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

        System.out.println(sb);

    }
    
}

 

설명

 

Stack 과 StringBuilder를 사용한 풀이. stack안에 push는 오름차순으로 입력하므로, 입력한 수를 start로 지정하여 저장한다.

출력해야하는 수를 value로 읽어와서, 해당 수까지 계속 push를 하고, 그때까지 넣어서, stack의 맨 위에 있는 수가 value라면 pop을 한다.

만약 stack의 맨 위에 있는 수가 value가 아니라면 수열을 만들 수 없으므로 NO 라고 출력한다.

 

 

새로 배운점

Stack<Integer> stack = new Stack<>();
  • stack 선언 방법.
  • stack.peek() 하면 빼내지 않고 맨 위의 수만 확인 가능.
  • Stringbuilder 를 System.out.print(sb) 하면 String으로 출력 가능.
  • StringBuilder 에는 문자열 append 해서 답 붙여넣는 방법이 효율적이다.
  • 사실 stack보다는 배열로 선언하는 방법이 조금 더 효율적이라고 한다. 하지만 큰 차이나지 않으면 stack이 편한듯.

'Algorithm > 백준' 카테고리의 다른 글

백준 2231번 ) 분해합 (java)  (0) 2022.02.24
백준 2630번 ) 색종이 만들기 (java)  (0) 2022.02.23
백준 11047번 ) 동전 0 (java)  (0) 2022.02.22
백준 4358번 ) 생태학 (java)  (0) 2021.10.08
백준 5525번 ) IOIOI (java)  (0) 2021.09.30