[do it 알고리즘] 백준 1874 (스택)

문제 설명

 

풀기 전 생각

• 일단 어디까지 반복을 해야 하는지 너무 헷갈렸다.
• 평소 반복문처럼 증가수를 arrLen까지 반복을 돌리기로 결정
• 증가수가 배열보다 작으면 같아질 때까지 stack에 넣고 같으면 빼고 arrIndex++
• 증가수가 배열 수 보다 작으면 pop만 하고 arrIndex++
• 대신, pop이 배열 숫자보다 크면 불가능하므로 NO출력

import java.util.Scanner;
import java.util.Stack;

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int arrLen = sc.nextInt();
        int[] arr = new int[arrLen];
        Stack<Integer> s = new Stack();
        for(int i = 0; i < arrLen; i++){
            arr[i] = sc.nextInt();
        }
        int increasingNum = 1;
        int arrIndex = 0;
        StringBuffer sb = new StringBuffer();

        while(increasingNum <= arrLen){
            if(increasingNum <= arr[arrIndex]){
                while(increasingNum <= arr[arrIndex]){
                    s.push(increasingNum++);
                    sb.append("+");
                }
                s.pop();
                sb.append("-");
                arrIndex++;
            }else {
                if(s.pop() > arr[arrIndex] ){
                    System.out.println("NO");
                    break;
                }
                s.pop();
                sb.append("-");
                arrIndex++;
            }

        }
        System.out.println(sb.toString());

    }
}

오류 및 개선

• 첫 번째 테스트케이스에서 증가값이 arrLen에 멈추므로 남아있는 것을 다 출력 못하고 끝남
• 두 번째도 arrLen에서 멈추므로 NO 조건을 검사를 못하고 그대로 출력
• s.pop()은 이미 한번 빠지므로 if문안에 쓰고 또 s.pop()하면 두 번 빠짐
• 기본기가 부족한 것 같아 강의 참조

최종

import java.util.Scanner;
import java.util.Stack;

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int arrLen = sc.nextInt();
        int[] arr = new int[arrLen];
        int increasingNum = 1;
        Stack<Integer> s = new Stack();
        boolean result = true;

        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < arrLen; i++){
            arr[i] = sc.nextInt();
        }

        for(int i = 0; i < arrLen; i++){
            if(increasingNum <= arr[i]){
                while(increasingNum <= arr[i]){
                    s.push(increasingNum++);
                    sb.append("+\n");
                }
                s.pop();
                sb.append("-\n");
            }else{
                int n = s.pop();
                if(n > arr[i]){
                    result = false;
                    System.out.println("NO");
                    break;
                };
                sb.append("-\n");
            }
        }
        if(result)System.out.println(sb.toString());
    }
}

• 반복은 배열을 기준으로 배열 끝까지 하기
• 배열을 순회할 i와 increasingNum 따로 분리
• if문은 increasingNum과 arr [i]를 비교하여 조건 설정
• increasingNum이 arr [i]와 같을 때까지 증가시키고 같으면 빼기
• increasingNum이 arr [i]보다 크면 넣지 말고 pop을 해서 꺼내기
• s.pop 숫자를 따로 빼서 변수에 저장
• s.pop이 arr [i] 보다 크면 스택 구조상 불가능
• boolean변수로 불가능하면 NO만 출력하고 프로그램 끝내기

참고

[자바 공부] 컬렉션(4) Stack & Queue

[자바 공부] 문자열 (String, StringBuffer, StringBuilder)

이론이 쉽다고 구현을 스킵하지 말자