8월 4주차 - priority queue, stack & queue

11279. 최대 힙

package bj11279;

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

// 단순히 pq 사용법 묻는 문제
// 아니면 힙 구현하던가

public class 최대힙11279 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
        int N = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();

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

 

2075. N번째 큰 수

package bj2075;

import java.io.*;
import java.util.*;

/*
모든 수는 자신의 한칸 위에 있는 수보다 크므로
한줄 + 그 다음줄(그 다음줄이 존재할 때만)
해서 max heap에 넣고 5개를 추출함
그리고 그 5개를 다시 위에 돌아가서 "한줄"에 삽입
반복

12 7 9 15 5 13 8 11 19 6
19 15 13 12 11

19 15 13 12 11 21 10 26 31 16
31 26 21 19 16

31 26 21 19 16 48 14 28 35 25
48 35 28 26 25

48 35 28 26 25 52 20 32 41 49
52 49 48 41 35
 */
public class N번째큰수2075 {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PriorityQueue<Integer> pq1 = new PriorityQueue<>(Collections.reverseOrder());

        int N = Integer.parseInt(br.readLine());
        StringTokenizer st1 = new StringTokenizer(br.readLine());
        List<Integer> l = new ArrayList<>();
        // 여기서 맨 처음 줄 넣어줌
        for(int i = 0; i<N; i++){
            l.add(Integer.parseInt(st1.nextToken()));
        }
        
        // 이제 두번째 줄 부터 
        // 처음 5개 + 그 아래 5개 = 총 10개 숫자 PQ에 넣고
        // 5개만 poll해서 윗 단계의 처음 5개로 설정함
        // N될때까지 반복
        for(int j = 1; j<N; j++) {
            st1 = new StringTokenizer(br.readLine());
            for(int i = 0; i<N; i++){
                l.add(Integer.parseInt(st1.nextToken()));
            }
            pq1.addAll(l);
            l.clear();
            for(int i=0; i<N; i++){
                l.add(pq1.poll());
            }
        }
        // N번째 뽑는 거니까 최소힙 PQ에 넣어서 처음꺼 poll
        PriorityQueue<Integer> pq3 = new PriorityQueue<>();
        pq3.addAll(l);
        System.out.println(pq3.poll());
    }
}

 

15825. Router

LinkedList보다는 사이즈를 미리 지정해줄 수 있는 LinkedBlockingQueue를 쓰자.

package bj15828;

import java.util.*;
import java.io.*;
import java.util.concurrent.LinkedBlockingQueue;

public class Router15828 {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        // BlockingQueue를 쓰면 사이즈 체크 안해도 됨
        // 가득 차면 스레드를 Block 해서 offer하려 하면 false가 반환되기 때문에
        Queue<Integer> q = new LinkedBlockingQueue<>(N);

        while(true){
            int temp = Integer.parseInt(br.readLine());
            if(temp < 0){
                break;
            }
            else if(temp == 0){
                q.remove();
            }
            else{
                q.offer(temp);
            }
        }
        if(q.isEmpty()) {
            System.out.println("empty");
            return;
        }
        while(!q.isEmpty()){
            System.out.print(q.remove() + " ");
        }
    }
}

 

5430: AC

출력에서 ,를 마지막에 무조건 빼버리는 것 때문에 

빈 배열에서 삭제하면 이상하게 나와서 그거 찾느라 40분 고민함

package bj5430;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Deque;
import java.util.LinkedList;

// deque 써서 뒤집을때마다 poll 해줄 방향 바꿔주기 true
public class AC5430 {
    public static String ac(Deque<Integer> dq, char[] cmds){
        //type R 명령마다 바꿔주기
        boolean type = true;
        for(char cmd : cmds){
            if(cmd == 'R'){
                type = !type;
            }
            else{
                if(dq.isEmpty())
                    return "error";

                if (type)
                    dq.pollFirst();
                else
                    dq.pollLast();
            }

        }
        StringBuilder sb = new StringBuilder("[");
        while(!dq.isEmpty()){
            if(type)
                sb.append(dq.pollFirst());
            else
                sb.append(dq.pollLast());
            if(!dq.isEmpty())
                sb.append(",");
        }
        // 맨 마지막 , 콤마 삭제 => 이거 때문에 안되던거였음!!!!!!!!!
        // sb.delete(sb.length()-1, sb.length());
        sb.append("]");
        return sb.toString();
    }

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

        // T가 0이 될때까지라는 뜻
        while(T-->0){
            Deque<Integer> dq = new LinkedList<>();
            char[] cmds = br.readLine().toCharArray();
            int n = Integer.parseInt(br.readLine());

            // 빈 배열 들어오면 error
            String cmdStr = br.readLine();
            // [ ] 떼고
            String cmdString = cmdStr.substring(1,cmdStr.length()-1);
            // ,기준으로 숫자 배열 스플릿해서 데크에 넣어줌
            for(String s : cmdString.split(",")){
                if(!s.equals(""))
                    dq.add(Integer.parseInt(s));
            }

            System.out.println(ac(dq, cmds));
        }
    }
}

 

10866. 덱

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

// Arrays.copyOf(원본 배열, 새 배열 길이)
// Arrays.copyOfRange(원본 배열, 시작 idx(포함), 끝 idx(포함x, 이 값 -1 한거까지만 포함)
// 예를 들어 {1,2,3,4}가 있는데 {2,3,4}를 추출하고 싶다고 하면
// arr = {1,2,3,4}
// newArr = Arrays.copyOfRange(arr, 1, 4);

public class 덱10866 {
    private static int[] push_front(int[] arr, int X){
        int[] temp = new int[arr.length+1];
        int idx = 0;
        temp[idx++] = X;
        for(int i : arr){
            temp[idx++] = i;
        }
        return temp;
    }

    private static int[] push_back(int[] arr, int X){
        int[] temp = Arrays.copyOf(arr, arr.length+1);
        temp[arr.length] = X;
        return temp;
    }

    private static int[] pop_front(int[] arr){
        if(empty(arr) == 0)
            return Arrays.copyOfRange(arr,1, arr.length);
        else
            return arr;
    }

    private static int[] pop_back(int[] arr){
        if(empty(arr) == 0)
            return Arrays.copyOfRange(arr, 0, arr.length-1);
        else
            return arr;
    }

    private static int size(int[] arr){
        return arr.length;
    }

    /**
     * 현재 배열이 비었는지 알려주는 메서드
     * @param arr
     * @return 비었으면 1, 아니면 0
     */
    private static int empty(int[] arr){
        if(size(arr) == 0)
            return 1;
        return 0;
    }

    private static int front(int[] arr){
        if(empty(arr)==0)
            return arr[0];
        else
            return -1;
    }

    private static int back(int[] arr){
        if(empty(arr)==0)
            return arr[arr.length-1];
        else
            return -1;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[] arr = new int[0];

        StringBuilder sb = new StringBuilder();
        while(N-->0){
            String[] cmds = br.readLine().split(" ");
            String cmd = cmds[0];
            if(cmds.length == 1){
                if(cmd.equals("front")){
                    sb.append(front(arr));
                }
                else if(cmd.equals("back")){
                    sb.append(back(arr));
                }
                else if(cmd.equals("size")){
                    sb.append(size(arr));
                }
                else if(cmd.equals("empty")){
                    sb.append(empty(arr));
                }
                else if(cmd.equals("pop_front")){
                    if(empty(arr) != 1)
                        sb.append(arr[0]);
                    else
                        sb.append(-1);
                    arr = pop_front(arr);
                }
                else if(cmd.equals("pop_back")){
                    if(empty(arr) != 1)
                        sb.append(arr[size(arr)-1]);
                    else
                        sb.append(-1);
                    arr = pop_back(arr);
                }
                sb.append("\n");
            }
            // push_back, push_front
            else{
                int num = Integer.parseInt(cmds[1]);
                if(cmd.equals("push_back")){
                    arr = push_back(arr, num);
                }
                else{
                    arr = push_front(arr, num);
                }
            }
        }
        System.out.println(sb);
    }
}

 

 

4949. 균형잡힌 세상

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

/*
문자열 스택으로 ( ) [ ] . 일때만 push
현재 push 할게 ]면, peek 해서 [ 면 pop하고 계속 진행 아니면 push 하고 break;
현재 push 할게 )면, peek 해서 ( 면 pop하고 계속 진행 아니면 push
( [ . 은 push
마지막에 스택에 . 하나 들어있으면 yes, 아니면 no

 */
public class 균형잡힌세상4949 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        while(true){
            String cmd = br.readLine();
            // 입력 종료조건
            if(cmd.equals("."))
                break;

            boolean error = false;
            Stack<Character> st = new Stack<>();
            for(char s : cmd.toCharArray()){
                if(s == ']'){
                    if(!st.isEmpty() && st.peek() == '[') {
                        st.pop();
                    }
                    else{
                        error = true;
                        break;
                    }
                }
                else if(s == ')'){
                    if(!st.isEmpty() && st.peek() == '(') {
                        st.pop();
                    }
                    else{
                        error = true;
                        break;
                    }
                }
                else if(s == '(' || s == '[')
                    st.push(s);

            }

            if(st.isEmpty() && !error) {
                sb.append("yes\n");
            } else {
                sb.append("no\n");
            }

        }
        System.out.println(sb.toString());
    }
}

 

1874. 스택수열

/*
    4 3 6 8 7 5 2 1 <- 이걸 만드려고 함
    stack 에는 12345678 순서로 push 됨
    1 2 3 4
    1 2 / 4,3
    1 2 5 6 / 4,3
    1 2 5 / 4,3,6
    1 2 5 7 8 / 4,3,6
    / 4,3,6,8,7,5,2,1

    입력 배열에 쭉 넣고
    1~n 순서대로 삽입되니까 start라는 변수에 1넣고 시작
    while(idx<N)[
        input[idx]마다 살펴보면서
        input[idx] + 1보다 작으면 'start' push
        st이 비지 않았을 때 peek했는데 idx의 value랑 같으면 pop
        idx++;
    ]

    1,2,5,3,4

    1
    /1
    2/1
    /1,2
    3,4,5/1,2
    3,4/1,2,5 => 저장하는 스택에서 pop 해도 수열 못만듬 (NO)

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

public class 스택수열1874 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        Stack<Integer> stack = new Stack<>();
        StringBuilder sb = new StringBuilder();

        int start = 1; // 스택에 1부터 순서대로 넣기 위해 시작 숫자 설정

        for(int i = 0; i < n; i++){
            int target = Integer.parseInt(br.readLine());

            // 목표 값이 start보다 크거나 같으면 start부터 목표 값(target)까지 스택에 푸시
            if(target >= start){
                while(start <= target){
                    stack.push(start++);
                    sb.append("+\n");
                }
            }

            // 스택 맨 위의 값이 현재 값과 같으면 pop
            if(stack.peek() == target){
                stack.pop();
                sb.append("-\n");
            }
            else {
                System.out.println("NO");
                return;
            }
        }

        System.out.println(sb.toString());
    }
}

 

5397. 키로거

package bj5397;
/*
toCharArray 쓰기
stack으로 하면
answer, input
<는 answer에서 pop해서 input에 add
>는 input에서 pop해서 answer에 add
문자는 answer에 add
-는 answer에 pop
 */
import java.util.*;
import java.io.*;

public class 키로거5397 {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();

        while(T-->0){
            char[] cmds = br.readLine().toCharArray();
            Stack<Character> answer = new Stack<>();
            Stack<Character> input = new Stack<>();

            for(char c : cmds){
                if(c == '<'){
                    if(!answer.isEmpty()){
                        input.push(answer.pop());
                    }
                }
                else if(c == '>'){
                    if(!input.isEmpty()){
                        answer.push(input.pop());
                    }
                }
                // 백스페이스
                else if(c == '-'){
                    if(!answer.isEmpty())
                        answer.pop();
                }
                else{
                    // 문자 붙여주기
                    answer.push(c);
                }
            }
            
            // 엣지케이스 -> input에 아직 넣어줘야할 값이 남아있으면 다 넣어줘야됨
            while(!input.isEmpty()){
                answer.push(input.pop());
            }

            StringBuilder sb2 = new StringBuilder();
            while(!answer.isEmpty()){
                sb2.append(answer.pop());
            }
            sb.append(sb2.reverse()+"\n");
        }
        System.out.print(sb);
    }
}

 

1655. 가운데를 말해요

import java.io.*;
import java.util.*;

/*
pq 두개 나눠서 max랑 min힙을 두는데
왼쪽은 max 오른쪽은 min
근데 max를 항상 1개 많게 해주면 그게 항상 중간값이 됨.
그리고 항상 max의 peek보다 min의 peek값이 커야함.

->최소 힙과 최대 힙의 크기가 같으면 max에 저장하기(1개 많게하는거 유지하는 로직)
아니면 min에 저장하기
max.peek이 min.peek보다 크면 위치 바꿔서 삽입

답은 max를 peek 해주면 됨
 */
public class 가운데를말해요1655 {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        PriorityQueue<Integer> min = new PriorityQueue<>();
        PriorityQueue<Integer> max = new PriorityQueue<>(Collections.reverseOrder());
        StringBuilder sb = new StringBuilder();

        for(int i = 0; i<N; i++){
            int num = Integer.parseInt(br.readLine());
            if(min.size() == max.size())
                max.add(num);
            else
                min.add(num);

            if(!max.isEmpty() && !min.isEmpty()) {
                if (max.peek() > min.peek()) {
                    int temp = min.poll();
                    int temp2 = max.poll();
                    max.add(temp);
                    min.add(temp2);
                }
            }
            sb.append(max.peek()+"\n");
        }
        System.out.print(sb);
    }
}