[Coding Test] inflearn(4)

1. 슬라이딩 윈도우 실전 문제

DNA 비밀번호 (백준 12891)

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

public class P12891_DNA비밀번호 {
    static int myArr[];
    static int checkArr[];
    static int checkSecret;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int result = 0;                             // 결과값
        int S = Integer.parseInt(st.nextToken());
        int P = Integer.parseInt(st.nextToken());
        char[] A = new char[S];                     // 문자열을 char 형태로 입력 받을 배열
        checkArr = new int[4];                // A C G T 의 조건
        myArr = new int[4];                   // 현재 나의 문자열중 A C G T 의 개수가 몇 개인지 확인하는 배열
        checkSecret = 0;                        // 조건이 몇개 총족이 되었는지 확인하는 변수

        A = br.readLine().toCharArray();            // char 형태로 문자 입력 받기
        st = new StringTokenizer(br.readLine());    // A C G T 의 조건 입력 받기
        for (int i = 0; i < 4; i++) {
            checkArr[i] = Integer.parseInt(st.nextToken());
            if (checkArr[i] == 0) {
                checkSecret++;
            }
        }

        for (int i = 0; i < P; i++) {
            Add(A[i]);
        }

        if (checkSecret == 4)
            result++;

        for (int i = P; i < S; i++) {               // 슬라이딩 윈도우
            int j = i - P;
            Add(A[i]);
            Remove(A[j]);
            if (checkSecret == 4)
                result++;
        }

        System.out.println(result);
        br.close();
    }

    private static void Add(char c) {
        switch (c) {
            case 'A':
                myArr[0]++;
                if (myArr[0] == checkArr[0])
                    checkSecret++;
                break;
            case 'C':
                myArr[1]++;
                if (myArr[1] == checkArr[1])
                    checkSecret++;
                break;
            case 'G':
                myArr[2]++;
                if (myArr[2] == checkArr[2])
                    checkSecret++;
                break;
            case 'T':
                myArr[3]++;
                if (myArr[3] == checkArr[3])
                    checkSecret++;
                break;
        }
    }

    private static void Remove(char c) {
        switch (c) {
            case 'A':
                if (myArr[0] == checkArr[0])
                    checkSecret--;
                myArr[0]--;
                break;
            case 'C':
                if (myArr[1] == checkArr[1])
                    checkSecret--;
                myArr[1]--;
                break;
            case 'G':
                if (myArr[2] == checkArr[2])
                    checkSecret--;
                myArr[2]--;
                break;
            case 'T':
                if (myArr[3] == checkArr[3])
                    checkSecret--;
                myArr[3]--;
                break;
        }
    }
}

2. 스택 (stack)

스택은 삽입과 삭제 연산이 후입선출(LIFO)로 이뤄지는 자료구조이다.
후입선출은 삽입과 삭제가 한 쪽에서만 일어나는 특징이 있다.
스택은 깊이 우선 탐색(DFS), 백트래킹 종류의 코딩 테스트에 효과적이다.

스택 용어

• top : 삽입과 삭제가 일어나는 위치를 뜻한다.
• push : top 위치에 새로운 데이터를 삽입하는 연산이다.
• pop : top 위치에 현재 있는 데이터를 삭제하고 확인하는 연산이다.
• peek : top 위치에 현재 있는 데이터를 단순 확인하는 연산이다.

3. 큐 (queue)

큐는 삽입과 삭제 연산이 선입선출(FIFO)로 이뤄지는 자료구조이다.
스택과 다르게 먼저 들어온 데이터가 먼저 나간다.
그래서 삽입과 삭제가 양방향에서 이뤄진다.

큐 용어

• rear : 큐에서 가장 끝 데이터를 가리키는 영역이다.
• front : 큐에서 가장 앞의 데이터를 가리키는 영역이다.
• add : rear 부분에 새로운 데이터를 삽입하는 연산이다.
• poll : front 부분에 있는 데이터를 삭제하고 확인하는 연산이다.
• peek : 큐의 맨 앞(front)에 있는 데이터를 확인할 때 사용하는 연산이다.

4. 스택과 큐 실전 문제

스택 수열 (백준 1874)

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

public class P1874_스택수열 {
    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<>();
        int num = 1;
        boolean result = true;
        StringBuffer sb = new StringBuffer();
        for (int i = 0; i < N; i++) {
            int su = A[i];
            if (su >= num) {
                while (su >= num) {
                    stack.push(num++);
                    sb.append("+\n");
                }
                stack.pop();
                sb.append("-\n");
            } else {
                int n = stack.pop();
                if (n > su) {
                    System.out.println("NO");
                    result = false;
                    break;
                } else {
                    sb.append("-\n");
                }
            }
        }
        if (result) System.out.println(sb.toString());
    }
}

카드2 (백준 2164)

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class P2164_카드2 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int num = 1;
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < N; i++) {
            queue.add(num++);
        }
        int size = queue.size();
        int cycle = 1;
        while (size != 1) {
            if (cycle % 2 == 1) {
                queue.poll();
                cycle++;
                size--;
            } else {
                int pollNum = queue.poll();
                queue.add(pollNum);
                cycle++;
            }
        }
        int Q = queue.peek();
        System.out.println(Q);
    }
}

절댓값 힙 (백준 11286)

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

public class P11286_절댓값힙 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        PriorityQueue<Integer> myQueue = new PriorityQueue<>((o1, o2) -> {
            int abs1 = Math.abs(o1);
            int abs2 = Math.abs(o2);

            if (abs1 == abs2) return o1 > o2 ? 1 : -1;
            return abs1 - abs2;
        });

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