[Silver I] 절댓값 힙_P11286

[ 성능 요약 ]

메모리: 30084 KB, 시간: 728 ms

[ 분류 ]

자료 구조(data_structures), 우선순위 큐(priority_queue)

[ 문제 설명 ]

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

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

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

[ 입력 ]

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

[ 출력 ]

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

 

 

---

 

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

public class test {
    public static void main(String[] args) throws IOException {
        // 들어오는 데이터가 많을 땐 scanner 보단 bufferedreader 사용하는 것이 자바에선 시간복잡도면에서 조금 더 유리하다.
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine()); // N : 요청의 갯수(입력할 정수 x 갯수)

        /* 우선순위 큐 정렬 기준 새로 정의하기 (람다식 활용..?) */
        PriorityQueue<Integer> pQueue = new PriorityQueue<>((o1, o2) -> { // 비교할 객체 2개 o1, o2 선언 (정렬 조건을 세분화하고 문제의 조건에 맞게 하기 위해 오버라이드 하는 느낌)
            /* 비교 객체를 어떻게 비교할건지 새로 정의 */

            int first_abs = Math.abs(o1); // o1 = 1
            int second_abs = Math.abs(o2); // o2 = -1
            if (first_abs == second_abs) { // 2. 절댓값이 같은 경우 음수 우선
                return o1 > o2 ? 1 : -1;
                // o1이 o2가크면 1 리턴, 아니면 -1 리턴
                // 1, -1이 중요한게 아니라
                // 1을 리턴한다는건 첫번째 매개변수가 더 큰 값이라는 것을 의미하고,
                // -1을 리턴한다는 것은 첫번째 매개변수가 더 작은 값이라는 것을 의미하는 것
            }
            return first_abs - second_abs; // 1. 절댓값 작은 데이터 우선
            // 첫번째 데이터 o1의 절댓값 first_abs가 더 크면 양수를 리턴,
            // 두번째 데이터 o2의 절댓값 second_abs가 더 크면 음수를 리턴한다.
            // 이 말은 절댓값 작은 데이터가 우선으로 정렬되게 한다는 것을의미한다.
            // 이 compare 에서 따지는 것은 리턴값이 음수이냐 양수이냐로 비교하는 o1, o2 의 정렬 기준을 세우는 것
        });

        for (int i = 0; i < N; i++) {
            int request = Integer.parseInt(br.readLine()); // request : 입력하는 정수 x 값
            // 1) 정수 x 값이 0인 경우,
            // 큐가 비어있으면 0 출력, 비어 있지 않으면 큐의 맨 앞 front 에서 하나 뽑아서 출력
            // (이때, 그냥 큐 맨 앞에 하나 빼도 되는 이유 : 위에서 애초에 큐 생성할 때 값 저장하는
            //  정렬 기준을 우리가 원하는 대로 절댓값이 작은 애들 먼저 저장되게끔 재정의했기 때문에
            //  맨 앞에 있는 애 뽑으면 된다.)
            if (request == 0) {
                if (pQueue.isEmpty()
                    System.out.println(0);
                else
                    System.out.println(pQueue.poll());
            }
            // 2) 정수 x 값이 0이 아닌 경우,
            // 새로운 정수 x 값 큐에 더하기
            else
                pQueue.add(request);
        }
    }
}

 

 

 

---

[ 슈도코드 작성 ]

(질의 요청 개수) N 선언하기 

우선순위 큐 pQueue 선언하기

- 절댓값 기준으로 정렬되도록 우선순위 큐 설정하기

- 단, 절댓값이 같으면 음수 우선 정렬되도록 우선순위 큐 설정하기

 

for ( N만큼 반복 ) {

    요청이 0 일때 : 큐가 비어 있으면 0, 비어 있지 않으면 큐의 front값 출력하기

    요청이 1일때 : 새로운 데이터를 우선순위 큐에 더하기 ( add ( ) )

}

 

 

 

 

---

 

PriorityQueue<Integer> queue = 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;
});

이 코드는 아래의 코드를 줄인 형태이다.

 

// Comparator 부분
Comparator<Integer> comparator = new Comparator<Integer>( ) {
    @Override
    public int compare(int o1, int o2) {
        int abs1 = Math.abs(o1);
        int abs2 = Math.abs(o2);
        
        if(abs1 == abs2)
            return o1 > o2 ? 1 : -1;
    }
};

PriorityOueue<Integer> queue = new PriorityQueue<>(comparator);

 

Comparator Java 공식문서를 보면 compare 메서드의 return이 음수, 0, 양수로 Priority queue 내부값 배열에 판단한다.

compare return	설명
양수	첫번째 매개변수가 더 큰 값으로 판단
0	같은 값으로 판단
음수	첫번째 매개변수가 더 작은 값으로 판단

 

이 compare가 Priority Queue 삽입/삭제 시 내부값을 다 비교해주며 배열을 해주는 것이다.

 

 

 

[ 참조 ]

- 설명 참조 -

[Java] Priority Queue 매개변수에 람다식 쓰는 이유가 뭐야? (velog.io)

 

- 우선순위 큐 이해할 때 편한 글 -

[자료구조 2] 우선순위 큐(Priority Queue) 이해하기 · 괭이쟁이 (laboputer.github.io)

 

- 람다식 이해할 때 편한 글 -

[JAVA] 람다식(Lambda)의 개념 및 사용법 :: 히진쓰의 서버사이드 기술 블로그 (tistory.com)

 

 

 

 

 

 

---