백준 17299번 오등큰수

문제

나의 풀이

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

public class Main {
    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[n];
        int freq[] = new int[n];
        int answer[] = new int[n];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
            freq[arr[i]] += 1;
        }

        Stack<Integer> stack = new Stack<>();
        stack.push(0);
        for(int i = 1; i < n; i++) {
            while(!stack.isEmpty() && freq[arr[stack.peek()]] < freq[arr[i]]) {
                answer[stack.pop()] = arr[i];
            }
            stack.push(i);
        }
        while(!stack.isEmpty()) {
            answer[stack.pop()] = -1;
        }

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

오큰수 풀이에서 해당 수가 얼마나 등장했는지 횟수를 세는 freq 정수 배열을 선언해줘서 입력 받은 수 마다 등장 횟수를 1 증가시켜주고 while문에서 비교할 때 등장횟수가 현재 값의 등장 횟수 보다 작은 경우 정답 배열에 오등큰수로 저장해주는 방식으로 구현하였다.

결과

백준 2164번 카드2

문제

나의 풀이

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        
        Queue<Integer> queue = new LinkedList<>();
        for(int i = 1; i <= n; i++) {
            queue.offer(i);
        }
        
        while(queue.size() > 1) {
            queue.poll();
            queue.offer(queue.poll());
        }
        
        System.out.println(queue.poll());
    }
}

큐를 이용해서 1부터 입력 바은 정수 n까지 큐에 넣는다. 그런 다음 큐의 사이즈가 1 보다 클 때 까지 while문을 돌려서 처음에는 가장 위에 있는 요소는 poll 메소드로 제거하고 두번째로 위에 있는 요소는 poll로 뽑아내고 그 값을 다시 offer 메소드로 가장 뒤로 집어넣게 한다. 그리고 마지막에 queue.poll() 메소드로 마지막에 남은 요소를 출력 시키면 된다.

결과

백준 11286번 절댓값 힙

문제

나의 풀이

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PriorityQueue<Integer> pq = new PriorityQueue<>((o1, o2) -> {
            int first = Math.abs(o1);
            int second = Math.abs(o2);
            if(first == second) { // 절댓값이 같은 경우
                return o1 > o2 ? 1 : -1; // 음수 우선 정렬하기
            } else {
                return first - second; // 절댓값을 기준으로 오름차순 정렬
            }
        });
        
        int n = Integer.parseInt(br.readLine());
        for(int i = 0; i < n; i++) {
            int req = Integer.parseInt(br.readLine());
            if(req == 0) {
                if(pq.isEmpty()) {
                    System.out.println("0");
                } else {
                    System.out.println(pq.poll());
                }
            } else {
                pq.add(req);
            }
        }
    }
}

우선순위큐를 이용해서 절댓값이 같은 경우는 음수를 우선으로 오름차순 정렬 시키고, 아닌 경우는 절댓값을 기준으로 오름차순 정렬하도록 설정해준다.
그런 다음 명령어가 0일 때 큐가 비어있으면 0을 출력하고 그렇지 않다면 큐의 요소를 빼낸 값을 출력한다. 명렁어가 0이 아닐 때는 그 값을 큐에 넣게 구현하면 된다.

결과