섹션 2. 코딩테스트 - 자료구조 (2) 파트

⬛ 03-4. ‘슬라이딩 윈도우’ 알고리즘

🟦 슬라이딩 윈도우 알고리즘

• 2개의 포인터로 고정 범위 지정한 뒤, 고정 범위를 옆으로 밀면서 이동함.
• O(n)으로 해결 원할 때 多 사용
• 크기를 유지한 상태로 이동하면서 조건에 맞는지 유효성 검사하며 탐색함

⬛ 03-5. 스택과 큐

🟦 스택 (Stack)

• 삽입/삭제 연산이 후입선출 LIFO 로 이루어지는 자료구조
• top 지칭하는 값(한쪽)에서만 삽입과 삭제가 일어남

🟧 스택 용어

1) 위치

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

2) 연산

push : top 위치에 새 데이터 삽입 연산

pop : top 위치의 데이터 삭제 & 확인 연산

peek : top 위치의 데이터 단순 확인 연산

🟧 스택 활용

• DFS(깊이 우선 탐색), 백트래킹 에서 多 활용

🟦 큐 (Queue)

• 삽입/삭제 연산이 선입선출 FIFO 로 이뤄지는 자료구조
• 먼저 들어온 데이터가 먼저 나가는 양방향 자료구조
• 새 값 추가는 rear(뒤), 값 삭제는 front(앞) 에서 일어남

🟧 큐 용어

1) 위치

rear : 큐의 가장 뒷 데이터 지칭 (삽입 연산 일어나는 위치)

front : 큐의 가장 앞 데이터 지칭 (삭제 연산 일어나는 위치)

2) 연산

add : rear 위치에 새 데이터 삽입 연산

poll : front 위치의 현재 데이터 삭제 & 확인 연산

peek : front 위치의 현재 값 단순 확인 연산

🟧 큐 활용

• BFS(너비 우선 탐색)에서 多 사용

🏓(추가) 우선순위 큐 (Priority Queue)

• 들어간 순서와 상관없이 ‘우선순위’ 높은 데이터를 먼저 처리함
• Heap(힙) 이용하여 구현

🟦 백준 17298번. 오큰수

문제

크기가 N인 수열 A = A1, A2, ..., AN이 있다. 수열의 각 원소 Ai에 대해서 오큰수 NGE(i)를 구하려고 한다. Ai의 오큰수는 오른쪽에 있으면서 Ai보다 큰 수 중에서 가장 왼쪽에 있는 수를 의미한다. 그러한 수가 없는 경우에 오큰수는 -1이다.

예를 들어, A = [3, 5, 2, 7]인 경우 NGE(1) = 5, NGE(2) = 7, NGE(3) = 7, NGE(4) = -1이다. A = [9, 5, 4, 8]인 경우에는 NGE(1) = -1, NGE(2) = 8, NGE(3) = 8, NGE(4) = -1이다.

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다.

출력

총 N개의 수 NGE(1), NGE(2), ..., NGE(N)을 공백으로 구분해 출력한다.

풀이

• 이 문제는 데이터 크기가 10^6 이고, 시간 제한이 1초이므로 이중 for문 사용 불가능하다.
• 스택을 사용할 건데, 수열의 값이 아닌 인덱스값을 스택에 push 하고 top지칭값 vs 현재 값과 크기를 비교하여 큰 값 나타나면 해당 인덱스에 대한 오큰수 발견. pop.
• 만약 끝까지 돌았는데도 더 큰 값이 나타나지 않는다면, pop하고 해당 인덱스의 값에는 -1을 세팅할 것.
• Scanner 와 System.out.print() 함수 사용 시 시간초과가 뜬다.
• BufferedReader와 BufferedWriter 사용하여 시간초과 안뜨게 할 것.

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

/*17298번. 오큰수 구하기 */
public class Main {
    //정적변수로 입출력 변수 세팅 
    static BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));    

    //실행 메인 
    public static void main(String[] args) throws IOException {
        // TODO Auto-generated method stub

        int n = Integer.parseInt(bf.readLine());
        int[] arr = new int[n];//하나씩 받는 용도 

        int[] setO = new int[n];//오큰수 저장용
        String[] str = bf.readLine().split(" ");
        for(int i =0; i<n; i++) arr[i] =Integer.parseInt(str[i]);

        Stack<Integer> st = new Stack<>();

        //초기화 일단 최초값 세팅
        st.push(0);//0번 값과 수열값 비교할거야 

        for(int i =0; i<n; i++) {
            //스택 비지않고, 현재 수열값이 > top값보다 큰 동안 pop
            while(!st.isEmpty() && arr[st.peek()] < arr[i]) {
                setO[st.pop()] = arr[i];//현재값을 pop한 인덱스값 정답배열에 세팅 
            }
            st.push(i); //신규 데이터 push 
        }

        //반복문 탈출 이후에도 여전히 스택에 특정값이 존재 == 오큰수 없는 인덱스 존재하는 거임 -1 세팅 
        while(!st.isEmpty()) {
            //반복문 모두 돌고나왔는데, 스택 빈 상태가 아닌 경우 -1 세팅 없다는 거니까 
            setO[st.pop()] = -1;
        }

        //정답 출력
        for(int x : setO) {
            bw.write(x+" ");
        }

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

🟦 백준 2164번. 카드 게임

문제

N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다.

이제 다음과 같은 동작을 카드가 한 장 남을 때까지 반복하게 된다. 우선, 제일 위에 있는 카드를 바닥에 버린다. 그 다음, 제일 위에 있는 카드를 제일 아래에 있는 카드 밑으로 옮긴다.

예를 들어 N=4인 경우를 생각해 보자. 카드는 제일 위에서부터 1234 의 순서로 놓여있다. 1을 버리면 234가 남는다. 여기서 2를 제일 아래로 옮기면 342가 된다. 3을 버리면 42가 되고, 4를 밑으로 옮기면 24가 된다. 마지막으로 2를 버리고 나면, 남는 카드는 4가 된다.

N이 주어졌을 때, 제일 마지막에 남게 되는 카드를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 정수 N(1 ≤ N ≤ 500,000)이 주어진다.

출력

첫째 줄에 남게 되는 카드의 번호를 출력한다.

풀이

• 시간 제한은 2초이고, 데이터 크기 최대 5*10^5 라서 시간복잡도의 제약 적다.
• 큐의 선입선출 성질 이용하여 풀면 된다.

package to_0605_4;

import java.util.*;

/* 2164번. 카드 게임 
 * */
public class Main {

    //실행 메인 
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner kb = new Scanner(System.in);

        int n = kb.nextInt();//카드 개수

        Queue<Integer> queue = new LinkedList<>();
        //1~n까지 차례로 큐에 세킹 
        for(int i=1; i<=n; i++) queue.add(i);

        while(queue.size() > 1) { //1보다 사이즈 큰 동안 반복 
            //1) 맨 앞 카드 제외
            queue.poll();
            //2)다음 카드 빼서 뒤에 담기 
            queue.add(queue.poll());
        }
        //최후 남은 카드 출력 
        System.out.println(queue.poll());

    }

}

🟦 백준 11286번. 절댓값 힙

문제

절댓값 힙은 다음과 같은 연산을 지원하는 자료구조이다.

1. 배열에 정수 x (x ≠ 0)를 넣는다.
2. 배열에서 절댓값이 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다. 절댓값이 가장 작은 값이 여러개일 때는, 가장 작은 수를 출력하고, 그 값을 배열에서 제거한다.

프로그램은 처음에 비어있는 배열에서 시작하게 된다.

입력

첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이라면 배열에서 절댓값이 가장 작은 값을 출력하고 그 값을 배열에서 제거하는 경우이다. 입력되는 정수는 -231보다 크고, 231보다 작다.

출력

입력에서 0이 주어진 회수만큼 답을 출력한다. 만약 배열이 비어 있는 경우인데 절댓값이 가장 작은 값을 출력하라고 한 경우에는 0을 출력하면 된다.

package to_0605_5;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.LinkedList;
import java.util.PriorityQueue;

/*11286번. 절댓값 힙 구현하기 */
public class Main {
    //정적변수로 입출력 변수 세팅 
    static BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));

    //실행 메인 
    public static void main(String[] args) throws IOException {
        // TODO Auto-generated method stub

        int n = Integer.parseInt(bf.readLine());
        PriorityQueue<Integer> pQ = new PriorityQueue<>((o1, o2) -> {
          int first_abs = Math.abs(o1);
          int second_abs = Math.abs(o2);
          if (first_abs == second_abs)
            return o1 > o2 ? 1 : -1;// 절대값이 같은 경우 음수 우선 정렬
          else
            return first_abs - second_abs;// 절대값을 기준으로 정렬
        });

        for(int i =0; i<n; i++) {
            int request = Integer.parseInt(bf.readLine());
            if(request == 0) {
                if(pQ.isEmpty()) {
                    System.out.println("0");
                }else {
                    System.out.println(pQ.poll());
                }
            }else {
                pQ.add(request);
            }
        }
    }
}