[엘카데미 챌린지] 10일차 Java 레벨 테스트 (5)

1. 서론

오늘도 자바 알고리즘 풀이를 진행하였다.

우선순위 큐를 이용하여 문제를 풀이하였다.

알고리즘에 재미를 붙이게 되는 것 같다.

---

2. 문제

엘리스와 이상한 상자

엘리스는 최댓값을 구할 수 있는 이상한 기계상자를 가지고있습니다. 이 최댓값 기계는 숫자를 여러개 담을 수 있으며, 담겨있는 숫자들 중에서 최댓값을 반환할 수 있습니다.

class를 이용하여 엘리스를 도와 최댓값 기계를 구현해봅시다.

 

엘리스의 이상한 기계상자는 다음의 기능을 지원 해야합니다.
machine.addNumber(x) : 숫자 x를 최댓값 기계 machine에 추가합니다.
machine.removeNumber(x) : 숫자 x를 최댓값 기계 machine으로부터 제거합니다. 만약 숫자 x가 최댓값 기계 내에 없다면 아무 일도 일어나지 않습니다.
machine.getMax() : 최댓값 기계 machine이 갖고있는 숫자들 중 최댓값을 반환합니다.

예를 들어, 기계상자의 이름이 myMachine이고 숫자 2, 5, 3, 4 를 각각 추가하기 위해서는 다음의 명령어를 사용합니다.

myMachine.addNumber(2)
myMachine.addNumber(5)
myMachine.addNumber(3)
myMachine.addNumber(4)

이후 myMachine.getMax() 를 호출하면, 이는 5를 반환하게 됩니다.

---

문제 풀이

우선순위 큐를 이용하여 문제를 해결하였다. 큐는 선입선출인 FIFO 형식의 자료구조인데, 우선순위 큐는 먼저 들어온 데이터가 아닌 우선순위가 높은 데이터가 먼저 나가는 자료구조이다.

maxMachine 메소드로 numbers라는 우선순위 큐를 초기화하고, Collections.reverseOrder()를 사용하여 우선순위 큐가 최댓값부터 내림차순으로 정렬되도록 하였다. addNumber 메소드로 우선순위 큐에 수를 추가하고, removeNumber 메소드로 제거하고, getMax 메소드로 최댓값을 반환하였다.

 

package elice;

import java.util.*;

class maxMachine {
    private PriorityQueue<Integer> numbers;
    public maxMachine() {
        numbers = new PriorityQueue<>(Collections.reverseOrder());
    }
    
    public void addNumber(int n) {
        numbers.add(n);
    }
    
    public void removeNumber(int n) {
        numbers.remove(n);
    }
    
    public int getMax() {
        return numbers.peek();
    }
}

public class Main {
	public static void main(String args[]) {
        int n, i;
        Scanner scan = new Scanner(System.in);
        maxMachine machine = new maxMachine();
    
        n = scan.nextInt();
    
        for(i = 0; i < n; i++)
        {
            int t;
            t = scan.nextInt();
            switch(t)
            {
            case 0: machine.addNumber(scan.nextInt()); break;
            case 1: machine.removeNumber(scan.nextInt()); break;
            case 2: System.out.println(machine.getMax()); break;
            }
        }
	}
}

실행 결과는 명령어 개수를 입력하고, case문의 번호와 수를 입력하여 출력할 수 있다.

예시)

3
0 10
0 5
2
10