[24/11/03] 스택

1874

import java.util.*;
import java.lang.*;
import java.io.*;
// The main method must be in a class named "Main".
class Main {
    static int top=-1;
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        List<Integer> arr = new ArrayList<>();
        boolean flag = false;

        boolean[] checkArr = new boolean[n+1];
        List<String> resultArr = new ArrayList<>();
        
        for(int i=0; i<n; i++){
            int k = Integer.parseInt(br.readLine());
            pushSn(arr,checkArr,resultArr,k);
            if(peek(arr)>k){
                resultArr.add("NO");
                flag=true;
                break;
            }
            else{
                pop(arr);
                resultArr.add("-");
            }
        }

        if(flag==true){
            System.out.printf("%s","NO");
            return;
        }
        for(int i=0; i<resultArr.size(); i++){
            System.out.printf("%s\n",resultArr.get(i));
        }
    }
    public static int pop(List<Integer> arr){
        if(top==-1){
            return -1;
        }
        return arr.remove(top--);
    }

    public static int peek(List<Integer> arr){
        if(top==-1){
            return -1;
        }
        return arr.get(top);
    }

    public static void push(List<Integer> arr,boolean[] checkArr,int num){
        arr.add(num);
        checkArr[num]=true;
        top++;
    }

    public static void pushSn(List<Integer> arr, boolean[] checkArr,List<String> resultArr, int num){
        for(int i =1; i<=num;i++){
            if(checkArr[i]==true){
                continue;
            }
            resultArr.add("+");
            push(arr,checkArr,i);
        }
    }


}

위의 코드는 힌트 얻기 전에 누가봐도 타임아웃 걸릴줄 알고 있었지만 일단 짜봤다.

아래와 같은 생각을 했었다.

1) NO가 나올때 기존 출력을 진행하다가 NO가 나오는게 아니라 NO가 있으면 그냥 NO만 나와야 된다. == + 와 - 를 저장했다가 한번에 출력해야된다.

 

2) 만약 숫자 k를 수열 원소로 가지면 문제 조건에 따라서 sequence~k까지 전부 push해야되는건 무조건 해야된다. 그러면 현재의 sequence를 어디까지 진행했나를 저장해야되는데 이것을 무식하게 checkArr의 1~n까지 true/false로 저장해서 매번 k에 대하여 checkArr의 1부터 탐색하여 k까지 false인 부분을 전부 push하겠다 이다. 여기서 타임아웃이 예상되었는데 매번 1~k 인덱스까지 검사하는게 O(k)이고, 이것이 n번 존재하니까 O(k*n) 이었다. 이것을 전체적으로 본다면

O(n*(n+1)/2)의 O(n^2)이 걸릴거고 n이 현재  100,000 번이라 타임아웃 예상되었다.

 

import java.util.*;
import java.lang.*;
import java.io.*;
// The main method must be in a class named "Main".
class Main {
    static int top=-1;
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        List<Integer> arr = new ArrayList<>();
        List<String> resultArr = new ArrayList<>();
        int sequence=1;

        for(int i=0; i<n; i++){
            int k = Integer.parseInt(br.readLine());
            while(sequence<=k){
                resultArr.add("+");
                push(arr,sequence++);
            }
            if(peek(arr)>k){
                System.out.printf("%s","NO");
                return;
            }
            else{
                pop(arr);
                resultArr.add("-");
            }
        }

        for(int i=0; i<resultArr.size(); i++){
            System.out.printf("%s\n",resultArr.get(i));
        }
    }
    public static int pop(List<Integer> arr){
        if(top==-1){
            return -1;
        }
        return arr.remove(top--);
    }

    public static int peek(List<Integer> arr){
        if(top==-1){
            return -1;
        }
        return arr.get(top);
    }

    public static void push(List<Integer> arr,int num){
        arr.add(num);
        top++;
    }


}

위 코드가 진짜 깡으로 Stack까지 구현해서 타임아웃 걸리지 않게 바꿔보았다.

 

문제가 되었던 2)은 굳이 배열에서 첫번째부터 False를 탐색하는것보다 int sequence값으로 어디까지 진행했나만 저장해놓으면 push하면서 O(n)의 시간복잡도로 풀이가 가능해진다.

 

아래는 답지 풀이다.

import java.util.*;
import java.lang.*;
import java.io.*;
// The main method must be in a class named "Main".
class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int A[] = new int[N];
        for(int i=0; i<N; i++){
            A[i] = sc.nextInt();
        }
        Stack<Integer> stack = new Stack<>();
        int num=1;
        StringBuffer bf = new StringBuffer();
        for(int i=0; i<A.length; i++){
            int su = A[i];
            if(su>=num){
                while(su>=num){
                    stack.push(num++);
                    bf.append("+\n");
                }
                stack.pop();
                bf.append("-\n");
            }else{
                int n = stack.pop();
                if(n>su){
                    System.out.println("NO");
                    return;
                }else{
                    bf.append("-\n");
                }
            }
        }
        System.out.println(bf.toString());

    }
}

 

1) 미련하게 Stack 직접 구현하지 말자.

Stack<> 내장 자료구조 이용하자.

2) StringBuffer

https://hstory0208.tistory.com/entry/Java%EC%9E%90%EB%B0%94-StringBuffer%EC%9D%98-%EC%82%AC%EC%9A%A9%EB%B2%95

 

내가 풀때는 List<String>으로 썼는데 이 문제에서는 문자열을 수정할 일이 없어서 괜찮았다.

근데 일반적으로 문자열을 수정하거나 저런 문자열을 이어붙힐때는 리스트나 배열 요소를 하나씩 출력해서 만드는것보다

가변성을 가지는 StringBuffer을 통해 기존 String 객체의 값을 수정하게 해보자.