leetcode : 1046. Last Stone Weight

요즘 코딩 테스트를 많이 하지 않는것 같아서 문제를 하나 풀어보았다. 

 

문제는 다음 사이트에서 풀 수 있다.

 

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

Last Stone Weight - LeetCode

 

Description

You are given an array of integers stones where stones[i] is the weight of the ith stone.

We are playing a game with the stones. On each turn, we choose the heaviest two stones and smash them together. Suppose the heaviest two stones have weights x and y with x <= y. The result of this smash is:
If x == y, both stones are destroyed, andIf x != y, the stone of weight x is destroyed, and the stone of weight y has new weight y - x.

At the end of the game, there is at most one stone left.
Return the smallest possible weight of the left stone. If there are no stones left, return 0.

 

Example 1:

Input: stones = [2,7,4,1,8,1]
Output: 1
Explanation: 
We combine 7 and 8 to get 1 so the array converts to [2,4,1,1,1] then,
we combine 2 and 4 to get 2 so the array converts to [2,1,1,1] then,
we combine 2 and 1 to get 1 so the array converts to [1,1,1] then,
we combine 1 and 1 to get 0 so the array converts to [1] then that's the value of the last stone.

 

처음에 입력값을 받을 때 주어진 Array를 잘 활용하면 될 것 같다는 생각이 들었다.

 

그런데 도저히 새로운 Array를 만드는 것 외에는 생각이 나질 않았다.

 

그런데 최근에 LinkedList와 ArrayList의 차이점에 대해서 읽었는데

 

LinkedList의 경우에는 중간 값이 추가, 삭제가 일어날 때 ArrayList보다 빠르다는 기억이 났다

 

그래서 이 배열을 LinkedList로 변환해 로직을 구성했다.

 

class Solution {
    public int lastStoneWeight(int[] stones) {
        
        List<Integer> stoneList =(LinkedList)Arrays.stream(stones).sorted().boxed().collect(Collectors.toCollection(LinkedList::new));
        while(stoneList.size() != 1){
            int max = Collections.max(stoneList);
            stoneList.remove(stoneList.indexOf(max));
            int nextMax = Collections.max(stoneList);

            if(nextMax == max){
                stoneList.remove(stoneList.indexOf(nextMax));
            }else {
                stoneList.remove(stoneList.indexOf(nextMax));
                stoneList.add(max - nextMax);
            }
            if(stoneList.size() == 0)
                return 0;
        }
        return stoneList.get(0);
        
    }
}

 

뭔가 길어보인다...

 

그래서 submission을 해보니 성능이 그렇게 좋지는 않다.

 

속도가 안나길래 내부에 Collections의 max method가 어떻게 구성되어 있는지 확인해본 결과

 

다음과 같았다. 

public static <T extends Object & Comparable<? super T>> T max(Collection<? extends T> coll) {
    Iterator<? extends T> i = coll.iterator();
    T candidate = i.next();

    while (i.hasNext()) {
        T next = i.next();
        if (next.compareTo(candidate) > 0)
            candidate = next;
    }
    return candidate;
}

전부 직접 돌려서 가장 큰 것을 찾아서 그냥 반환해주는 것이었다....

 

결국 전부 돌게 되는것인데 

 

그러니까 속도가 느리지...

 

결국 가장 큰 값, 그 다음값을 서로 비교해서 같으면 삭제, 다르면 큰값에서 작은 값을 뺀 값을 넣어주면 된다. 

 

그렇게 하면 굳이 Collections.max를 이용해서 찾고, 삭제하고, 찾고 하는 일이 필요가 없다!

 

그러면 하나의 이 배열을 어떻게 잘 정렬해서 사용해야 할까 해서 다른 사람들의 풀이를 보았다.

 

다른 사람 풀이 1 - 배열 사용하기

class Solution {
    public int lastStoneWeight(int[] stones) {
        //가장 먼저 정렬을 한다.
        //stones = [2,7,4,1,8,1]
        Arrays.sort(stones);
        //stones = [1,1,2,4,7,8]
        for(int i=stones.length-2;i>-1;i--){
        	//문제에서 중요한 점은 
            //가장 큰 두 수를 서로 조합하기에 가장 뒤에 있는 수에 먼저 접근을 한다.
            Arrays.sort(stones);
            stones[i]=Math.abs(stones[i+1]-stones[i]);
			/*
            	i = 4일 때
            	stones[4] = Math.abs(stones[5] - stones[4]); 
                => 8-7 = 1이고 이 값을 stones[4]에 넣음.
                stones = [1,1,2,4,1,8] 정렬 후 => stones = [1,1,1,2,4,8] 
                
                i = 3일 때
                stones[3] = Math.abs(stones[4] - stones[3]);
                => 4 - 2 = 2이고 이 값을 stones[3]에 넣음
                stones = [1,1,1,2,4,8]
                
                i = 2일 때
                stones[2] = Math.abs(stones[3] - stones[2]);
                => 2 - 1 = 1이고 이 값을 stones[2]에 넣음
                stones = [1,1,1,2,4,8]
                
                i = 1일 때
                stones[1] = Math.abs(stones[2] - stones[1]);
                => 1 - 1 = 0이고 이 값을 stones[1]에 넣음
                stones = [1,0,1,2,4,8]
                
                i = 0일 때
                stones[0] = Math.abs(stones[1] - stones[0]);
                => 1 - 0 = 1이고 이 값을 stones[0]에 넣음
                stones = [1,0,1,2,4,8]
                
            */            
        }
        return stones[0]; // stones[0]은 1임
    }
}

 

오름차순으로 정렬이 되고 가장 높은 값에서부터 차근 차근 빼고 그것을 밑으로 내려가며 체크한다. 

 

어짜피 가장 큰 값은 사라지는게 확실하니 그 나머지값만 조합해서 넣어주면 되기에 이렇게 한 것 같다. 

 

그런데 다른 풀이에서는 PriorityQueue를 이용했다.

 

사실 이것에 대해 잘 몰라서 공부를 했다. 참고할 분은 참고하면 좋을것이다. (허졉해도 욕 안하기) 여기

 

두번째 풀이 - PriorityQueue 활용

public int lastStoneWeight(int[] stones) {
	PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
	for(int st: stones)
    		pq.offer(st);

	while(pq.size() > 1) {
		int f = pq.poll();
		int s = pq.poll();
		if(f != s) 
			pq.offer(f-s);
	}

	return pq.isEmpty() ? 0 : pq.peek();
}

 

결국 가장 큰 돌과 그것보다 한단계 작은 돌을 뽑아서 깨뜨리는 작업을 하게 된다. 

 

그러면 PriortyQueue의 경우 Heap을 토대로 구현한 자료구조로 내림차순으로 정렬할 경우 두개를 깨뜨려서 같은 경우에는 PriorityQueue에 넣지 않고, 다를 경우에만 제공한다. 

 

그렇게 하게되면 언젠가는 하나 혹은 0개만 남게 되는데 

 

이것을 반환해주면 된다.

 

아니... 이렇게 쉬운 방법이 있다니 ...

---

사실 문제는 금방 풀고 풀이도 금방 볼 수 있었지만 위와 관련된 자료구조에 대해 제대로 이해하고자 좀 오래 걸렸다.

 

거기에 더해 주말에 고향에 다녀올 일이 있었는데 덕분에 공부를 하나도 못했다...

(ㄹㅇ 가슴아픔... 하...진짜 너무해... 끄아ㅡ아앙)

 

재미있는 사실은 무언가 이해를 하려고 한다면 근본적인 정보를 찾기 위해 시간을 부쩍 많이 할애한다는 것이다. 

 

진즉에 알았어야 할 많은 기본 지식이 부족하다는 방증이다. ㅠㅠ...

 

하여간 이 문제 덕분에 많은 정보를 얻은 것 같다.