스택 & 큐 - 자바 백준 스택수열: 1874 오큰수: 17298

Stack

스택은 삽입과 삭제가 LIFO(Last-in First-out = 후입선출) 로 이루어지는 자료구조입니다.

LIFO 는 삽입과 삭제가 한쪽에서 만 일어나는 특징이 있습니다.

 

 

top: 삽입과 삭제가 일어나는 위치

push: top 위치에 새로운 데이터를 삽입하는 연산

pop: top 위치에 현재 있는 데이터를 삭제하고 확인하는 연산

peek: top 위치에 현재 있는 데이터를 단순 확인하는 연산.

 

Stack 은 DFS(Depth First Search = 깊이 우선 탐색), 백트래킹 종류의 코딩 테스트에 효과적이므로 반드시 알아두어야 합니다. LIFO 는 개념 자체가 재귀함수 알고리즘 원리와 일맥상통하기 때문입니다.

 

Queue

큐는 삽입과 삭제 연산이 FIFO(First-in First-out = 선입선출)로 이루어지는 자료구조입니다. 스택과 다르게 먼저 들어온 데이터가 먼저 나갑니다.

FIFO는 삽입과 삭제가 양방향에서 이뤄집니다.

 

 

새 값 추가는 rear 에서, 삭제는 front 에서 이루어 집니다.

rear: 큐에서 가장 끝 데이터를 가리키는 영역

front: 큐에서 가장 앞의 데이터를 가리키는 영역

add: rear 부분에서 새로운 데이터를 삽입하는 연산

poll: front 부분에 있는 데이터를 삭제하고 확인하는 연산

peek: front 에 있는 데이터를 확인하는 연산.

 

큐는 BFS(Breadth First Search = 너비 우선 탐색) 에서 자주 사용하므로 잘 알아 두어야 하는 개념입니다.

Priority Queue
우선순위 큐는 값이 들어간 순서와 상관없이 우선순위가 높은 데이터가 먼저 나오는 자료구조입니다.
큐 설정에 따라 front 에 항상 최대 혹은 최소값이 위치합니다.
일반적으로 Heap(힙)을 이용해 구현하는데 힙은 트리의 종류이므로 해당 부분 학습할 떄 자세히 공부하겠습니다.

 

 

백준 1874

1874번: 스택 수열

1874번: 스택 수열

 

1. 문제 분석

스택의 원리를 정확하게 알고 있는지 문제입니다.

스택의 pop, push 연상과 LIFO 개념을 정확히 이해하고 있다면 쉽게 풀 수 있습니다. 이 문제에서 스택에 넣는 값은 오름차순 정렬입니다.

2. 손으로 풀어보기

1 부터 자연수를 증가시키면서 입력으로 주어진 숫자와 비교하여 증가시킨 자연수를 스택에 추가하거나 빼는 방식으로 풀면 됩니다.

 

 

스택 연산 수행 방법

 

    a. 현재 수열 값 ≥ 자연수

 

현재 수열 값 ≥ 자연수일 때까지 자연수를 1씩 증가시키며 자연수를 스택에 push 한다. 그리고 push 가 끝나면 수열을 출력하기 위해 마지막 1회만 pop 한다.

 

    b. 현재 수열 값 < 자연수 일 때

 

현재 수열 값 < 자연수 이라면 스택에 있는 값을 pop 한다. 꺼낸 값이 현재 수열값일 수도 아닐 수도 있습니다.

만약 아니라면 LIFO 원리에 따라 수열을 표현할 수 없으므로 NO 을 출력하고 문제를 종료, 수열값이 맞다면 조건문을 빠져나온다.

 

 

3. 슈도코드 작성

N(수열 개수) A[](수열 배열)

수열 배열 채우기

for(N만큼 반복){
    if(현재 수열 값 >= 오름차순 자연수){
        while(값이 같아질 때까지){
            push()
            (+) 저장
        }
    	pop()
        (-) 저장
    } else {
        pop()
        if(스택 pop 결과값 > 수열의 수) NO 출력
        else { (-) 저장 }
    }
}

if(NO 값을 출력한 적이 없으면) 저장한 값 출력

 

4. 코드 구현

public class Main {
    public static void main(String[] args) {
        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<>();
        StringBuffer bf = new StringBuffer();

        int num = 1; // 오름차순 수
        boolean result = true;

        for (int i = 0; i < A.length; i++) {
            int su = A[i];  // 현재 수열의 수

            if (su >= num) { // 현재 수열 값 >= 오름차순 자연수 -> 값이 같아질 때까지 push() 수행.
                while (su >= num) { 
                    stack.push(num++);
                    bf.append("+\n");
                }
                stack.pop();
                bf.append("-\n");
            } else { // 현재 수열 값 < 오름차순 자연수: pop() 을 수행해 수열 원소를 꺼냄
                int n = stack.pop();

                // 스택의 가장 위의 수가 만들어야 하는 수보다 크면 수열을 출력할 수 없음.
                if (n > su) {
                    System.out.println("NO");
                    result = false;
                    break;
                } else {
                    bf.append("-\n");
                }
            }

        }
        if (result) {
            System.out.println(bf.toString());
        }
    }
}

 

 

 

백준 17298

17298번: 오큰수

17298번: 오큰수

 

1. 문제분석

N 의 최대 크기가 1,000,000 이므로 반복문으로 오큰수를 찾으면 제한시간을 초과합니다.

 

 

핵심 아이디어

• 스택에 새로 들어오는 수가 top 에 존재하는 수보다 크면 그 수는 오큰수가 된다
• 오큰수를 구한 후 수열에서 오큰수가 존재하지 않는 숫자에 -1 을 출력해야 한다.

손으로 문제를 풀어보면서 이 2가지 아이디어를 발전시키고 예외 상황까지 고려해봅시다.

 

2. 손으로 풀기

정답 배열의 값을 모두 채운 후에 출력하면 됩니다.

 

 

문제 푸는 순서

 

a. 스택이 채워져있거나 A[index] > A[top] 인 경우 pop 한 인덱스를 이용하여 정답 수열에 오큰수를 저장합니다. pop 은 조건을 만족하는 동안 계속 반복합니다. 과정 1을 마치면 과정 2로 넘어갑니다.

b. 현재 인덱스를 스택에 push 하고 다음 인덱스로 넘어갑니다.

c. 과정 1~2 을 수열 길이만큼 반복한 후 현재 스택에 남아있는 인덱스에 -1 을 저장합니다.

 

 

먼저 예제에서 제공하는 예제 입력 1 로 문제 푸는 순서를 적용해봅시다.

pop → 정답 배열에 값을 추가하는 것

push → 다음 인덱스를 본다.

 

• 처음에는 스택이 비어있으므로 바로 현재 인덱스 0 을 push 하고 다음 인덱스로 넘어갑니다.
• ( A[top] = A[0] = 3 ) < ( A[1] = 5 ) 이므로 스택에서 pop 을 수행하고 Result[0] 에 오큰수 5 = A[1] 을 저장합니다. 1회 반복으로 스택이 비었으므로 pop 은 더이상 진행하지 않고 인덱스 1을 push 하고 다음 인덱스로 넘어갑니다.
• ( A[top] = A[1] = 5 ) > ( A[2] = 2 ) 이므로 인덱스 2 을 push 하고 다음 인덱스로 넘어갑니다.
• ( A[top] = A[2] = 2 ) < ( A[3] = 7 ) 이므로 pop 하여 Result[1] 에 오큰수 7 = A[3] 저장,
  ( A[top] = A[1] = 5 ) > ( A[3] = 7) 이므로 pop 하여 Result[1] 에 오큰수 7 = A[3] 저장합니다. 그리고 나서 스택이 비었으므로 인덱스 3을 push 하고 다음 인덱스로 넘어갑니다.
• 스택 길이만큼 반복했으니 스택에 남아있는 index 에 -1 을 저장합니다.

예제 입력 2 에 대해서도 손으로 간단히 풀어봅시다.

 

 

3. 슈도코드

N(수열 개수) A[] (수열 배열) ans[](정답 배열)

수열 배열 채우기
최초 스택 초기화

for(N 만큼 반복){
    while(스택 notEmpty && 
        현재 수열 값이 top에 해당하는 수열값보다 클 때까지){
        pop()
        정답 배열에 오큰수를 현재 수열값으로로 저장
    }
    현재 수열값을 스택에 push()
}

while(스택이 빌 때까지){
    스택에 있는 인덱스의 정답 배열에 -1 저장하기
}

정답 배열 출력

 

4. 코드

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(bf.readLine());

        int[] A = new int[n]; // 수열 배열
        int[] ans = new int[n];

        String[] str = bf.readLine().split(" ");

        for (int i = 0; i < n; i++) {
            A[i] = Integer.parseInt(str[i]);
        }

        Stack<Integer> myStack = new Stack<>();
        myStack.push(0); // 처음에는 항상 스택이 비어있으므로 최초 값을 push 해서 초기화

        for (int i = 1; i < n; i++) {
            // 스택이 비어있지 않고 현재 수열값이 스택 top 인덱스가 가리키는 수열보다 클 경우
            while (!myStack.isEmpty() && A[myStack.peek()] < A[i]) {
                ans[myStack.pop()] = A[i]; // 정답 배열에 오큰수를 현재 수열로 저장하기
            }
            myStack.push(i);    // 신규 데이터 push
        }

        while (!myStack.isEmpty()) {
            // 반복문을 다 돌고 나왔는데 스택이 비어있지 않다면 빌 때까지
            // 스택에 쌓인 index 에 -1 을 넣기
            ans[myStack.pop()] = -1;
        }

        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        for (int i = 0; i < n; i++) {
            // 출력
            bw.write(ans[i] + " ");
        }

        bw.write("\n");
        bw.flush();
    }
}

 

정답의 크기는 이미 고정되어 있으니 정답 배열을 만들어 놓고, 스택에 값이 아닌 인덱스를 넣어야 쉽게 풀린다니….. 어렵네요..

스택의 후입선출이라는 독특한 성질이 시간 복잡도를 줄이거나 특정한 문제의 조건을 손쉽게 해결하는 실마리가 될 때가 있습니다.

 

Queue 문제는 다음 글에서 풀어보겠습니다.