[백준] 11286번 절댓값 힙 - 우선순위 큐 / 오름차순 정렬 / 반환 값 변화 / 절댓값

문제

 

 

로직 

연산 개수 입력받기

큐 선언(우선순위 큐를 아예 구현하려고 큐로 선언함ㅜ)

 

1. 반복문

- 숫자 입력 받기

- 숫자가 0이 아닐 때 -> 큐에 삽입

- 숫자가 0일 때 -> 큐가 비었을 때 -> 0출력

                         -> 큐가 안 비었을 때 -> 출력할 값을 변수에 저장 후 출력

 

sign함수

- 결과값 변수 선언 및 초기화

- 결과를 저장할 배열 선언 및 크기 설정

- 음수값 저장할 배열 선언 및 크기 설정

- 양수값 저장할 배열 선언 및 크기 설정

1. 반복문

- 큐 안의 값이 음수일 때 -> minus배열에 값 불러와 저장 -> 배열 오름차순 정렬

- 큐 안의 값이 양수일 때 -> plus배열에 값 불러와 저장 -> 배열 오름차순 정렬

2. 반복문

절댓값 크기를 비교하며 배열 값을 큐에 삽입 

-> 이 로직을 세우는 것이 어려워서 마무리 못함

결과값 반환

 

 

My Code

import java.io.*;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

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

        int x;
        for (int i = 0; i<N; i++) {
            x = Integer.parseInt(bf.readLine());
            if (x != 0){
                cardQueue.add((x));
            }
            else{
                if (cardQueue.isEmpty())
                    System.out.println(0);
                else {
                    int num = sign(cardQueue);
                    System.out.println(num);
                }
            }

        }
    }


    private static int sign(Queue<Integer> cQueue) {
        int result = 0;
        int[] numArray = new int[cQueue.size()];
        int[] minus = new int[cQueue.size()];
        int[] plus = new int[cQueue.size()];

        for (int i = 0; i < cQueue.size(); i++) {
            if(cQueue.peek() < 0){
                minus[i] = cQueue.poll();
                Arrays.sort(minus);
            }
            else{
                plus[i] = cQueue.poll();
                Arrays.sort(plus);
            }
        }
        for (int i = 0; i < cQueue.size(); i++) {
            if(Math.abs(minus[i]) <= Math.abs(plus[0]))
                cQueue.add(minus[i]);
            else {
                cQueue.add(plus[0]);

                while(Math.abs(minus[i]) <= Math.abs(plus[0]))

            }
        }
        return result;
    }
}

 

 

문제의 핵심 & 알게된 점

우선순위 큐로 선언한 후 

절댓값에 따라 오름차순 정렬시키고 절댓값이 같은 경우 음수, 양수 판별 후 정렬시켜야한다.

우선순위 큐의 우선순위 정하는 기준을 위와 같이 구현하는 것이 문제의 핵심이었다.

그런 논리는 알고 있었지만 구현하기 어려웠다...

거의 8시간 동안 이틀에 걸쳐 이 문제만 생각했는데 쉽지 않았다...

return할 때 반환 값에 따라 오름차순, 내림차순 정렬이 가능하다는 것을 알게 되어 구현할 수 있었다.

return o1 - o2;일 때

o1 > o2 => 1

o1 == 02 => 0

o1 < o2 => -1

위와 같은 규칙으로 오름차순 정렬로 정의가 가능하다.

(내림차순은 반대로)

큐를 선언할 때 비교할 값 2개 변수(o1, o2)를 선언해서 비교하며 구현하는 방식도 처음 알게 됐다.

 

 

참고 Code

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

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());
        PriorityQueue<Integer> cardQueue = 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;
            }
            return first_abs - second_abs;
        });

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

        }
    }
}

 

 

참고 강의_인프런의 Do it! 알고리즘 코딩테스트 with JAVA