[leetcode] Last Stone Weight

https://leetcode.com/problems/last-stone-weight/

 

 

 

array 가 주어진다.

가장 큰 숫자 둘을 꺼낸다.

두 숫자가 같으면 둘 다 파괴하고,

다르면 그 차이를 다시 array에 넣는다.

위의 작업을 array의 크기가 1 이하로 떨어질 때 까지 반복한다.

array가 1이면 남은 숫자 하나를 반환하고,

0이면 0을 반환하는 문제이다.

 

이 문제는 PriorityQueue를 사용하면 간단하게 해결된다.

가장 큰 숫자를 꺼내기 위해서 내림차순 PriorityQueue 를 만든 후,

poll 로 두 개를 꺼내어 비교한 뒤 그 차이만큼을 다시 PriorityQueue 에 넣으면 된다.

위의 작업을 PriorityQueue의 size가 1 이하로 떨어질 때 꺼정 반복하면 된다.

코드를 보면 더 이해가 쉬울 것이다.

 

class Solution {
    public int lastStoneWeight(int[] stones) {
        int size = stones.length;
		PriorityQueue<Integer> qu = new PriorityQueue<>(size, Collections.reverseOrder());
		for(int stone : stones) {
			qu.offer(stone);
		}
		
		while(qu.size()>1) {
			int a = qu.poll();
			int b = qu.poll();
			if(a>b) qu.offer(a-b); //a와 b가 같은 경우는 파괴되므로 다시 offer 하지 않는다.
		}
        if(qu.size()==1) return qu.peek();
        else return 0;
    }
}

 

 

이것보다 더 빠르게 푼 알고리즘의 경우,

반복할 때마다 Arrays.sort 를 계속 적용하는데

문제의 최대 array length 가 30이라서 더 빠른 속도를 낼 수 있었던 듯.

만약 array가 일파만파 컸더라면 위의 PriorityQueue 를 사용하는 것이 더 현명한 선택일 것이다.