[백준/JAVA] 1874번: 스택 수열

🔺 문제

1874번: 스택 수열

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
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;
        
        while(n --> 0) {
            int value = Integer.parseInt(br.readLine());
            
            // 1) 원하는 숫자가 나올 때까지 push
            if(value > start) {
                for(int i = start + 1 ; i <= value; i ++) {
                    stack.push(i);
                    sb.append('+').append("\n");
                }
                start = value;
            }
            // 2) 원하는 숫자가 아닌 경우
            else if(stack.peek() != value) {
                System.out.println("NO");
                return;
            }
            
            // 3) 원하는 숫자가 나오면 pop
            stack.pop();
            sb.append("-").append("\n");
        }
        
        System.out.println(sb);
    }
}

✅ 해결 아이디어
✔ 스택
- 현재 수열 값 ≥ 자연수 → 현재 수열 값이 자연수보다 크거나 같을 때까지 자연수를 1씩 증가시키며 자연수를 스택에 push함. push가 끝나면 수열을 출력하기 위해 마지막 1회만 pop
- 현재 수열 값 < 자연수 →  pop으로 스택에 있는 값을 꺼냄.

 

---

🔺 다른 풀이들

- 항상 친절한 풀이에 감사드리는..

[백준알고리즘-JAVA]1874번 풀이(스택 수열) - 초보도 이해하는 풀이

---

💬 느낀 점

어렵지 않은데.. 내가 못 하는 거....ㅠ

암튼 이로써 스택 완!

 

1회독	2회독	3회독	4회독	5회독
V	6/12

 

 

(+ 6/12 2회독)

import java.util.*;
import java.io.*;
 
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int n = Integer.parseInt(br.readLine());
        int[] A = new int[n]; // 수열 배열
        
        for(int i = 0 ; i < n ; i++) {
            A[i] = Integer.parseInt(br.readLine());
        }
        
        Stack<Integer> stack = new Stack<>();
        StringBuilder sb = new StringBuilder();
        int num = 1;    // 오름차순 수
        boolean result = true;
        
        for(int i = 0 ; i < n ; i++) {
            int cur = A[i]; // 현재 수열의 수
            
            // 현재 수열 값 >= 오름차순 자연수 : 값이 같아질 때까지 push
            if(cur >= num) {    
                while(cur >= num) {
                    stack.push(num++);
                    sb.append("+\n");
                }
               stack.pop(); // 마지막 1회만 pop
                sb.append("-\n");
            }
            // 현재 수열 값 < 오름차순 자연수 : pop()으로 수열 원소 꺼냄
            else {
                int top = stack.pop();  // 스택의 최상단에 있는 수
                
                if(top > cur) {
                    System.out.println("NO");
                    result = false;
                    break;
                }
                else {
                    sb.append("-\n");
                }
            }
        }
        
        if(result) System.out.println(sb.toString());    
    }
}

 

---

(참고)

✔ 뭔 소린가..하다가 선생님 블로그 글 보고 작성...

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

 

✔ Do it 알고리즘 코딩테스트 자바편