[백준] 1874번 스택 수열 JAVA (자바) 풀이

문제 1874번

 : 1부터 n까지의 수를 스택에 넣고 뽑아 하나의 수열을 만들 수 있다. (스택에 push 순서는 반드시 오름차순)  
   임의의 수열이 주어졌을 때 스택을 이용해 그 수열을 만들 수 있는지 없는지 보고
   있다면 어떤 순서로 push와 pop 연산을 수행해야 하는지 작성하라

 

 [입력]

 

 : 첫 줄에 n
 : 둘째 줄부터 n개의 줄에는 수열을 이루는 1이상 n이하의 정수가 하나씩 순서대로 주어진다
 : 물론 같은 정수가 두 번 나오는 일은 없다

 

 [출력]

 

  : 한 줄에 한 개씩 출력 
  : push연산은 +로, pop 연산은 -로 표현
  : 불가능한 경우 NO를 출력

 

 [문제 이해]

 

입력받은 숫자까지 순서대로 수열을 만들어 push (이때 +출력) 그리고 해당 수 pop (이때 - 출력)

다음입력이 수열 안에 있으면 바로 pop하고 수열 안에 없으면 새롭게 push 해서 pop

 

(예)

입력 4 = 4까지 수열 만들기 → push 4번 → {1,2,3,4} → 4 빼기 → pop 1번 → {1,2,3} → + + + + -

입력 3 = 전 수열 {1,2,3} 맨 위에 3이 포함되어 있으므로 push 없이 바로 pop 1번 → {1,2} → -

입력 6 = 전 수열 {1,2} 에 6 없어서 6 까지 push 2번 → {1,2,5,6} → 6빼기 → pop 1번 → {1,2,5} → + + -

              (이때 3, 4를 넣지 않은 것은 모든 수가 중복되지 않고 그 전에 이미 pop해서 없다)

입력 2 = 전 수열 {1,2,5} 안에 2가 있으나 맨 위의 값이 아니라 pop 해줄 수 없다 → NO

               (즉 불가능한 연산 NO를 출력한다)

 

 

 [스택 연산]

 

init()	스택을 초기화
create()	스택을 생성
is_empty(s)	스택이 비어있는지 검사
is_full(s)	스택이 가득 찼는지 검사
push(e)	스택의 맨 위에 요소 e 추가
pop(s)	스택의 맨 위 요소를 삭제
peek(s)	스택의 맨 위 요소를 삭제하지 않고 반환
top()	스택 맨 위에 있는 데이터 값 반환
push()	스택에 데이터 삽입
pop()	스택에서 데이터 삭제하여 반환
isEmpty()	스택에 원소가 없으면 'True', 있으면 'False' 값 반환
isFull()	스택에 원소가 없으면 'False', 있으면 'True' 값 반환

 

[코드]

 

import java.io.*;
import java.util.*;
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 t = Integer.parseInt(br.readLine());
     int s = 0;
     while(t-->0){
         int n = Integer.parseInt(br.readLine());
         if(n>s){ // 스택안에 내가 찾고자 하는 수가 없을 때 PUSH
             for(int i=s+1;i<n+1;i++){
                 stack.push(i);
                 sb.append('+').append('\n');
             }
             s = n;
         }
         else if(stack.peek()!= n){ 
             System.out.println("NO");
             return; //이거 안쓰면 출력 초과
         }
         stack.pop(); // 후입선출, 스택안에 내가 찾고자 하는 수가 top에 있을 때 POP
         sb.append('-').append('\n');
     }
        System.out.println(sb);
    }
}

 

 [해설]

 

:  StringBuilder sb = new StringBuilder(); 기존의 문자에 다른 문자열를 합칠때 유용

:  Stack<Character> stack = new Stack<>(); 문자별로 스택에 넣고 빼기

:  int a = Integer.parseInt(br.readLine()); 는 입력 첫줄에 받아온 숫자

:  int n = Integer.parseInt(br.readLine()); 는 두번째 줄부터 받아오는 숫자들

:  if(n>s){  s(초깃값은 0)는 현재위치, n은 입력되는 수

:  for(int i=s+1;i<n+1;i++){  s = 0 이니까 i가 1부터 n이하의 숫자까지 증가

            stack.push(i);  그럼 i가 1부터 시작해 원하는 n까지 스택에 push를 한다

            sb.append('+').append('\n'); push 할때마다 + 출력하기
             }
            s = n; (현재위치 s를 n으로 변경) 그럼 1부터 다시 push하는게 아니라  n 다음 수부터 push 이어서 가능
         }

: else if(stack.peek()!= n){  
           System.out.println("NO");
           return; 이거 안쓰면 출력 초과된다, System.exit(0); 으로 써도 괜찮다
             } 맨위에 있는 숫자가 n이 아니면 내가 원하는 수를 pop 할 수가 없어서 NO출력
         

: stack.pop();  후입선출

: sb.append('-').append('\n');  pop 할 때 마다 - 출력
         

 

 

이제 풀어보러 갈께요 :)

 

 

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

1874번: 스택 수열

 

* 독학으로 익히는 코딩이라 틀린 것이 있을 수 있습니다. 오류가 있다면 댓글을 통해 알려주세요. 감사합니다. *