티스토리 뷰

728x90
반응형

소스 코드는 여기 있습니다.
문제는 여기 있습니다.

Problem

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, and
  • If 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.

Example 2:

Input: stones = [1]
Output: 1

Constraints:

  • 1 <= stones.length <= 30
  • 1 <= stones[i] <= 1000

Solution

돌의 무게를 나타내는 정수 배열이 주어집니다.

각 턴마다 가장 무거운 두 개의 돌을 집어 두 개를 부술 수 있습니다.

두 돌의 무게가 같으면 둘 다 부서지고 무게가 다른 경우 더 가벼운 돌은 부서지고 더 무거운 돌은 원래 무게에서 가벼운 돌의 무게를 뺀만큼만 남습니다.

하나의 돌이 남을 때까지 반복해서 위의 작업을 거쳤을 때 남는 돌의 무게를 구하는 문제입니다.

우선순위 큐를 이용해 매 번 돌의 무게가 내림차순으로 정렬되게하면 간단하게 해결할 수 있습니다.

package io.lcalmsky.leetcode.last_stone_weight;

import java.util.PriorityQueue;

public class Solution {

  public int lastStoneWeight(int[] stones) {
    PriorityQueue<Integer> queue = new PriorityQueue<>((o1, o2) -> Integer.compare(o2, o1)); // (1)
    for (int stone : stones) { // (2)
      queue.offer(stone);
    }
    while (queue.size() >= 2) { // (3)
      Integer first = queue.poll();
      Integer second = queue.poll();
      if (first == second) { // (4)
        continue;
      }
      queue.offer(first - second); // (5)
    }
    return queue.isEmpty() ? 0 : queue.poll(); // (6)
  }
}
  1. 내림 차순으로 정렬하는 우선순위 큐를 생성합니다.
  2. 모든 돌을 큐 안에 넣습니다.
  3. 큐에 두 개 이상의 원소가 남아있을 동안 반복합니다.
  4. 두 개의 돌을 꺼내 둘 다 부서진 경우 다음 돌을 선택합니다.
  5. 두 크기가 달라 부서진 경우 부서지고 남은 돌을 다시 큐에 넣습니다.
  6. 큐가 비어있으면 0을, 남아있으면 해당 돌을 반환합니다.

Test

package io.lcalmsky.leetcode.last_stone_weight;

import static org.junit.jupiter.api.Assertions.assertAll;
import static org.junit.jupiter.api.Assertions.assertEquals;

import org.junit.jupiter.api.Test;

class SolutionTest {

  @Test
  void testAll() {
    assertAll(
        () -> test(new int[]{2, 7, 4, 1, 8, 1}, 1),
        () -> test(new int[]{1}, 1),
        () -> test(new int[]{1, 3}, 2)
    );
  }

  private void test(int[] given, int expected) {
    // when
    Solution solution = new Solution();
    int actual = solution.lastStoneWeight(given);
    // then
    assertEquals(expected, actual);
  }
}
728x90
반응형

'Algorithm > LeetCode Daily Challenge' 카테고리의 다른 글

31. Next Permutation  (0) 2022.04.23
344. Reverse String  (0) 2022.04.22
1046. Last Stone Weight  (0) 2022.04.19
923. 3Sum With Multiplicity  (0) 2022.04.18
11. Container With Most Water  (0) 2022.04.16
1721. Swapping Nodes in a Linked List  (0) 2022.04.15
댓글
댓글쓰기 폼