Cooper's devlog

스택수열 : 1874번 - JAVA 본문

Algorithm/Baekjoon

스택수열 : 1874번 - JAVA

cooper_dev 2020. 7. 7. 12:22

1. 문제 링크

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

 

2. 문제 설명

 

3. 문제 접근법

예제 입력1

(1) 4 입력 시

  • 1 ~ 4까지 stack에 추가
  • stack에 추가하는 동시에, '+'가 result에 추가됨
  • 4 발견 시, stack에서 4 제거
  • '-'가 result에 추가

stack(Stack)

1 2 3 (4)        

result(ArrayList)

+ + + + -      

 

(2) 3 입력 시

  • 3이 나올 때까지 출력
  • '-'가 result에 추가

stack(Stack)

1 2 (3)          

result(ArrayList)

+ + + + - -    

(3) 6 입력 시

  • ~6까지 stack에 추가
  • stack에 추가하는 동시에, '+'가 result에 추가
  • 6 발견 시, stack에서 6 제거
  • '-'가 result에 추가

stack에 추가하는 동시에, 

stack(Stack)

1 2 5 (6)        

result(ArrayList)

+ + + + - - + + -  

위와 같은 원리로 반복....

 

 

4. 문제 풀이

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
import java.util.ArrayList;
import java.util.Scanner;
import java.util.Stack;
 
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int cnt = 1;
        Stack<Integer> stack = new Stack<Integer>();
        ArrayList<Character> result = new ArrayList<Character>();
        
        int test_case = Integer.parseInt(sc.nextLine());
        for (int i = 0; i < test_case; i++) {
            int data = sc.nextInt();
            while (cnt <= data) {
                stack.push(cnt);
                cnt += 1;
                result.add('+');
            }
            
            if (stack.peek() == data) {
                stack.pop();
                result.add('-');
            }
            else {
                System.out.println("NO");
                return;
            }
        }
        
        for (int i = 0; i < result.size(); i++) {
            System.out.println(result.get(i));
        }
    }
}
 
  

 

5. 개선점 또는 트러블 슈팅

- 이전 코드에서 런타임 에러가 계속 떴는데, for문의 로직에 해당하는 부분을 다시 적었더니 된다;;

(이전 코드를 다시 한번 확인해봐야겠다)

 

'Algorithm > Baekjoon' 카테고리의 다른 글

조세퍼스 문제 : 1158번 - JAVA  (0) 2020.07.08
에디터:1406번 - JAVA  (0) 2020.07.08
괄호 : 9012번 - JAVA  (0) 2020.07.07
단어 뒤집기 : 9093번 - JAVA  (0) 2020.07.06
스택 : 10828번 - JAVA  (0) 2020.07.06
'Algorithm/Baekjoon' Related Articles more
Comments