[백준] 1874 - 스택 수열 JAVA

Solved.ac Class 완전정복 프로젝트

Class : 2 ~ 2 ++

 

---

링크

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

1874번: 스택 수열

문제

스택 (stack)은 기본적인 자료구조 중 하나로, 컴퓨터 프로그램을 작성할 때 자주 이용되는 개념이다. 스택은 자료를 넣는 (push) 입구와 자료를 뽑는 (pop) 입구가 같아 제일 나중에 들어간 자료가 제일 먼저 나오는 (LIFO, Last in First out) 특성을 가지고 있다.

1부터 n까지의 수를 스택에 넣었다가 뽑아 늘어놓음으로써, 하나의 수열을 만들 수 있다. 이때, 스택에 pushpush 하는 순서는 반드시 오름차순을 지키도록 한다고 하자. 임의의 수열이 주어졌을 때 스택을 이용해 그 수열을 만들 수 있는지 없는지, 있다면 어떤 순서로 push와 pop 연산을 수행해야 하는지를 알아낼 수 있다. 이를 계산하는 프로그램을 작성하라.

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

출력
입력된 수열을 만들기 위해 필요한 연산을 한 줄에 한 개씩 출력한다. push연산은 +로, pop 연산은 -로 표현하도록 한다. 불가능한 경우 NO를 출력한다.

접근방법

 문제부터 이해하는 게 난해하다. 다른 것보다 이 문제는 문제에 대한 설명을 이해하는데 오랜 시간이 걸렸던 것 같다. 요약하자면, 1부터 n개의 숫자를 스택에 담고 뺀다. 단, 입력에 주어진 순서대로 빼야 하며, 1부터 n개의 정수는 한 번씩만 사용한다. 본 문제가 스택의 특징인 LIFO특성을 활용한다는 것 정도만 인지하고 풀이로 넘어가자.

풀이

 문제가 이해가 안 될 땐 예제를 그려보는 것이 답이다. 첫 번째 예제의 입력은 8 4 3 6 8 7 5 2 1이다.  둘째 줄부터 수열을 이루는 정수이므로, 첫번째 입력 4를 예로 그려보자.

예제 1, 입력 4를 처리하는 과정

 입력 4를 꺼내고 싶다면, 1부터 4까지 순차적으로 푸시하여 스택에 넣는다. 그다음 스택 가장 위에 있는 정수 4를 pop 하여 output으로 꺼낼 수 있다. 이 과정을 문제에 조건처럼 표현한다면, '+ + + + -'이다. 나 같은 경우 이 정도 그려보니, 그제야 출력이 의미하는 것을 깨달았다.

 

1~n까지의 순차적인 숫자를 stack을 이용해 push/pop을 이용하여, 완벽하게 뽑아낼 수 있는 수열인지 아닌지 판단하는 것이다. 

 

 풀이는 간단하다. 스택 인덱스(이하, 스택 포인터)를 기억하고 있는 포인터 변수(그림에서는 idx)를 하나 만들고, push 할 때, 그 위치를 증가시킨다. 다음 입력이 들어왔을 때, 스택 포인터보다 작다면, 이미 stack 이후의 과정에 있는 것으므로, pop을 통해 확인한다. 다음 입력이 크다면, 아직 스택에 들어오지 못한 데이터 이므로, 스택에 넣고 pop과정을 거친다.

 

그렇다면 수열이 안 만들어지는 경우는 어떠한 경우인가?

 해당 문제에서 같은 숫자는 나올 수 없다고 하였으므로, 이미 stack에 들어간 정수 값은 재사용이 불가능하다. 즉, 특정 값을 찾기 위해 pop 하여, 다른 정수 값들을 내보냈다면, 입력을 다 처리하기 전에 스택이 비어 버리게 된다. 따라서 입력보다 먼저 스택이 비는 경우에 흐름 제어를 해준다면, 충분히 만들어지지 않는 경우도 구현이 가능하다.

 

실패 원인

 문제 자체는 이해한 다음부터는 쉽게 구현하였는데, 시간 초과에서 엄청난 스트레스를 받았다. 때문에 programmars 형태인 solution 메서드에 로직을 때려 박아 구현하는 방식도 포기하며, 구현했다. 처음 ArrayList로 변수를 저장한 다음 처리하였는데, 그것도 아끼기 위해 입력을 받는 대로 처리했다. 그러나 문제는 다른 곳에 있었다. 실패 코드는 더보기로 접어둔다.

 

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;

public class Main {


    public static void main(String[] args) throws IOException {
        Main test = new Main();
    }

    public Main() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int tc = Integer.parseInt(br.readLine());
        Stack<Integer> stack = new Stack<>();
        boolean[] visit = new boolean[tc+1];
        int stack_pointer = 1;

        boolean toggle = true;
        for (int i = 0; i < tc; i++) {
            int target = (Integer.parseInt(br.readLine()));

            if(toggle){
                if (stack_pointer <= target) {
                    for (int k = 1; k <= target; k++) {
                        if (!visit[k]) {
                            visit[k] = true;
                            stack.push(k);
                            sb.append("+\n");
                        }
                    }
                }

                if (stack.contains(target)) {
                    while (stack.peek() >= target) {
                        stack_pointer = stack.pop();
                        sb.append("-\n");
                        if (stack.isEmpty()) {
                            break;
                        }

                    }
                } else {
                    toggle =false;

                }
            }

        }

        if(toggle){
            System.out.println(sb);
        }else{
            System.out.println("NO");
        }
    }
}

 

시간초과에 정신이 나갈 뻔 했다.

 

 

 

 나는 Stack에서 해당 입력값이 있는지 없는지 contains로 확인하여, 수열이 가능한지 불가능한지를 확인했다. 하지만 이게 문제였다.

 

. contains() 

 Stack 클래스는 Collections 하위의 Vector 클래스를 상속받은 클래스이다. contains 클래스를 따라가다 보면, Vector 클래스의 indexOf를 이용하는데, 이 메서드의 내용은 아래와 같다.

public synchronized int indexOf(Object o, int index) {
        if (o == null) {
            for (int i = index ; i < elementCount ; i++)
                if (elementData[i]==null)
                    return i;
        } else {
            for (int i = index ; i < elementCount ; i++)
                if (o.equals(elementData[i]))
                    return i;
        }
        return -1;
    }

 

 순차 접근 방식을 보아, 결론적으로 시간 복잡도 O(n)을 갖게 된다. 때문에 pop을 처리할 때마다 O(n) 짜리 검색 함수를 쓴 꼴이 된 것이니, 시간이 오래 걸릴 수밖에 없었다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;

public class Main {


    public static void main(String[] args) throws IOException {
        Main test = new Main();
    }

    public Main() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int tc = Integer.parseInt(br.readLine());
        Stack<Integer> stack = new Stack<>();
        int stack_pointer = 1;

        boolean toggle = true;
        for (int i = 0; i < tc; i++) {
            int target = (Integer.parseInt(br.readLine()));

            if(toggle){
                //Push logic
                if (stack_pointer <= target) {
                    for (int k = stack_pointer; k <= target; k++) {
                            //스택포인터 증가
                            stack.push(k);
                            stack_pointer++;
                            sb.append("+\n");
                    }
                }
                //Pop logic
                //스택이 텅빈상태로 왔다면 이미 잘못된 흐름임
                if (!stack.isEmpty()) {
                    while (stack.peek() >= target) {
                        stack.pop();
                        sb.append("-\n");
                        if (stack.isEmpty()) {
                            break;
                        }
                    }
                } else {
                    toggle =false;
                }
            }
            if (!toggle)
                break;
        }

        if(toggle){
            System.out.println(sb);
        }else{
            System.out.println("NO");
        }
    }
}

결과

33114920,33114850 - stack.Isempty() 메서드 사용

33114873 -stack.contains() 메서드 사용(억지로 변수 줄여서 사용)

 

 

contains 메서드 하나 차인데 저 압도적인 시간 차이를 보인다.

collections 인터페이스 구조부터 쭉 타고 내려오면서, vector의 indexof 메서드까지 깊게 공부할 수 있는 좋은 문제였다.

 

---

포스팅에 문제가 있거나, 설명이 잘못된 부분 지적 환영합니다.

더 나은 퀄리티의 콘텐츠를 제공할 수 있도록 노력하겠습니다.

읽어주셔서 감사합니다.