Algorithm/코딩테스트

[리트코드][JAVA] 2195. append-k-integers-with-minimal-sum (최소 합으로 K 정수 추가하기)

ioh'sDeveloper 2024. 6. 23. 18:48
💡 문제
append-k-integers-with-minimal-sum (https://leetcode.com/problems/append-k-integers-with-minimal-sum/description/)
자세한 문제 설명과 입출력 예는 링크를 참고해주세요.

 

📝 선행 개념

HashSet은 Java에서 제공하는 자료구조 중 하나로, 집합(Set)을 구현한 클래스입니다. 여기서 집합은 중복을 허용하지 않고 순서가 없는 요소들의 모임을 의미합니다. HashSet은 해시 테이블을 이용하여 구현되어 있어, 데이터의 추가, 삭제, 검색 등의 연산이 평균적으로 O(1)의 시간 복잡도를 가집니다. 이는 데이터의 크기에 상관없이 일정한 성능을 보장합니다.

HashSet의 주요 특징:

  1. 중복을 허용하지 않음: 동일한 요소를 여러 번 추가해도 한 번만 유지됩니다.
  2. 순서가 없음: 데이터의 저장 순서가 유지되지 않습니다.
  3. 빠른 검색, 삽입, 삭제: 해시 함수를 이용하여 요소의 추가, 삭제, 검색이 빠르게 수행됩니다.
  4. 동기화 지원 안 함: HashSet은 동기화를 지원하지 않으므로, 여러 스레드에서 안전하게 사용하려면 Collections.synchronizedSet() 메서드를 이용해야 합니다.

HashSet의 자바 예시 코드:

다음은 HashSet을 사용하여 데이터를 추가하고 검색하는 간단한 예시 코드입니다.

import java.util.HashSet;

public class HashSetExample {
    public static void main(String[] args) {
        // HashSet 객체 생성
        HashSet<String> hashSet = new HashSet<>();

        // 데이터 추가
        hashSet.add("apple");
        hashSet.add("banana");
        hashSet.add("orange");

        // 중복된 데이터 추가 시도 (중복된 데이터는 추가되지 않음)
        hashSet.add("apple");

        // 데이터 출력
        System.out.println("HashSet: " + hashSet); // 출력 순서는 예측할 수 없음

        // 데이터 검색
        String searchItem = "banana";
        if (hashSet.contains(searchItem)) {
            System.out.println(searchItem + " found in the HashSet.");
        } else {
            System.out.println(searchItem + " not found in the HashSet.");
        }

        // 데이터 삭제
        hashSet.remove("orange");

        // 삭제된 데이터 확인
        System.out.println("After removing 'orange', HashSet: " + hashSet);
    }
}
  • HashSet<String> hashSet = new HashSet<>();: HashSet 객체를 생성합니다. 이 HashSet은 문자열을 요소로 갖습니다.
  • hashSet.add("apple");, hashSet.add("banana");, hashSet.add("orange");: HashSet에 데이터를 추가합니다. 중복된 데이터는 한 번만 추가됩니다.
  • System.out.println("HashSet: " + hashSet);: HashSet의 모든 요소를 출력합니다. 순서는 저장 순서와 다를 수 있습니다.
  • hashSet.contains(searchItem): HashSet에서 특정 요소를 검색합니다. contains() 메서드는 해당 요소가 HashSet에 있는지 여부를 확인합니다.
  • hashSet.remove("orange");: HashSet에서 특정 요소를 제거합니다.
  • System.out.println("After removing 'orange', HashSet: " + hashSet);: 'orange' 요소를 제거한 후의 HashSet의 내용을 출력합니다.

HashSet은 자료구조의 특성상 순서가 유지되지 않고, 중복된 요소를 허용하지 않는다는 점에서 유용하게 사용될 수 있습니다.

🤓 문제 풀이

🔨 문제 설명

주어진 정수 배열 nums와 정수 k가 있습니다. nums에 없는 k개의 고유한 양의 정수를 nums에 추가하여 추가된 정수들의 합을 최소화해야 합니다.

🔨 접근 방법

  1. 누락된 정수 식별:
    1. 먼저, nums에 없는 양의 정수들을 식별합니다. 이를 위해 nums의 모든 값을 HashSet에 저장하고, 연속된 숫자들을 검사하여 없는 숫자들을 찾습니다.
  2. 누락된 정수들의 합 계산:
    1. 누락된 정수들의 합을 계산합니다. 이 합이 최소화해야 할 결과값입니다.

🔨 문제 풀이 과정

  • 단계 1: HashSet을 사용한 존재 여부 확인
    • nums를 순회하며 각 숫자를 HashSet에 저장하여 빠르게 존재 여부를 확인합니다 (O(1) 평균 시간 복잡도).
    • HashSet을 사용하여 주어진 배열 nums에 있는 모든 숫자를 저장합니다. HashSet은 평균적으로 O(1)의 시간 복잡도로 요소에 접근할 수 있어 존재 여부를 빠르게 확인할 수 있습니다.
  • 단계 2: 누락된 정수 찾기
    • 1부터 시작하여 각 숫자가 HashSet에 존재하지 않는지 확인하고, 누락된 숫자들의 합을 구합니다. 이 과정을 k개의 누락된 숫자를 찾을 때까지 반복합니다.
    • 1부터 시작하여 숫자를 하나씩 증가시키면서 해당 숫자가 HashSet에 존재하지 않는지 확인합니다. 존재하지 않는 숫자들을 차례로 누락된 숫자로 처리하며, 그 숫자들의 합을 계산합니다.
  • 단계 3: 결과 계산 및 반환
    • k개의 누락된 숫자들의 합을 구한 후, 이 값을 반환합니다.

🔨 HashSet 선택 이유

선택한 알고리즘은 "누락된 숫자들을 찾아서 그 합을 최소화하는" 문제를 해결하기 위한 방법으로, 다음과 같은 접근을 사용했습니다:

HashSet을 활용한 접근 방법

  1. 문제 요구 사항:
    • 주어진 배열 nums에 없는 k개의 고유한 양의 정수를 추가하여 추가된 정수들의 합을 최소화해야 합니다.
  2. HashSet의 역할:
    • HashSet은 중복을 허용하지 않고 빠르게 검색할 수 있는 자료구조입니다.
    • 주어진 배열 nums의 모든 요소를 HashSet에 저장하여, 어떤 숫자가 존재하는지 여부를 빠르게 확인할 수 있습니다.
  3. 누락된 숫자 찾기:
    • 1부터 시작하여 숫자를 하나씩 증가시키면서 HashSet에 존재하지 않는 숫자를 찾습니다.
    • 이러한 접근 방식은 주어진 배열 nums에 포함되지 않은 양의 정수들을 순서대로 찾아서 그 합을 계산하는 방법입니다.
  4. 알고리즘 설명:
    • HashSet 초기화: 주어진 배열 nums의 모든 요소를 HashSet에 추가합니다. 이 과정은 O(n) 시간이 걸립니다 (n은 nums 배열의 길이).
    • 누락된 숫자 찾기: 1부터 시작하여 각 숫자가 HashSet에 존재하는지를 확인하고, 존재하지 않는 숫자들을 찾아 그 합을 계산합니다. 이 과정은 O(k) 시간이 걸립니다 (k는 누락된 숫자의 개수).
    • 따라서 총 시간 복잡도는 O(n + k)입니다.
  5. 장점:
    • 빠른 검색: HashSet을 사용하면 숫자의 존재 여부를 O(1)의 시간 복잡도로 확인할 수 있어, 누락된 숫자를 효율적으로 찾을 수 있습니다.
    • 간단한 구현: HashSet을 이용한 이 접근 방식은 구현하기 쉽고, 시간 복잡도 역시 입력 크기에 비해 효율적입니다.

이러한 방법을 선택함으로써 주어진 문제를 해결하는 데 있어서 효율성과 간결함을 동시에 고려한 접근을 할 수 있습니다.

🔨 구현코드

import java.util.HashSet;

class Solution {
    public long minimalKSum(int[] nums, int k) {
        // 모든 숫자를 빠르게 조회하기 위해 HashSet을 사용합니다
        HashSet<Integer> set = new HashSet<>();
        for (int num : nums) {
            set.add(num);
        }
        
        long sum = 0; // k개의 누락된 정수들의 합을 저장하기 위한 변수입니다
        int missingCount = 0; // 찾은 누락된 정수들의 개수를 세기 위한 변수입니다
        int num = 1; // 1부터 시작해서 확인할 숫자입니다
        
        // k개의 누락된 정수를 찾을 때까지 반복합니다
        while (missingCount < k) {
            // 현재 숫자가 HashSet에 없다면, 그 숫자는 누락된 것입니다
            if (!set.contains(num)) {
                sum += num; // 누락된 숫자를 합에 추가합니다
                missingCount++; // 찾은 누락된 숫자의 개수를 증가시킵니다
            }
            num++; // 다음 숫자로 넘어갑니다
        }
        
        return sum; // k개의 누락된 정수들의 합을 반환합니다
    }
}
import java.util.Arrays;

class Solution {
    public long minimalKSum(int[] nums, int k) {
        // 배열을 정렬합니다
        Arrays.sort(nums);
        
        long sum = 0; // k개의 누락된 정수들의 합을 저장하기 위한 변수입니다
        int missingCount = 0; // 찾은 누락된 정수들의 개수를 세기 위한 변수입니다
        int num = 1; // 1부터 시작해서 확인할 숫자입니다
        
        // 정렬된 배열에서 누락된 숫자를 찾습니다
        for (int i = 0; i < nums.length && missingCount < k; i++) {
            // nums[i]가 num보다 크면 num부터 nums[i]-1 사이의 숫자들이 누락된 것입니다
            while (num < nums[i] && missingCount < k) {
                sum += num; // 누락된 숫자를 합에 추가합니다
                missingCount++; // 찾은 누락된 숫자의 개수를 증가시킵니다
                num++; // 다음 숫자로 넘어갑니다
            }
            num = nums[i] + 1; // 다음 확인할 숫자를 설정합니다
        }
        
        // 배열의 끝까지 순회한 후에도 k개의 누락된 숫자를 찾지 못한 경우 처리
        while (missingCount < k) {
            sum += num; // 누락된 숫자를 합에 추가합니다
            missingCount++; // 찾은 누락된 숫자의 개수를 증가시킵니다
            num++; // 다음 숫자로 넘어갑니다
        }
        
        return sum; // k개의 누락된 정수들의 합을 반환합니다
    }
}

📚 풀이 보완

코드 설명

  • HashSet 초기화: 먼저, HashSet을 사용하여 nums 배열에 있는 모든 요소를 저장합니다. 이는 O(n) 시간복잡도로 수행됩니다 (n은 nums 배열의 길이).
  • 누락된 숫자 확인: num 변수를 1부터 시작하여 증가시키면서 각 숫자가 HashSet에 포함되어 있는지를 확인합니다. 만약 포함되어 있지 않다면, 그 숫자는 nums 배열에 없는 누락된 숫자입니다.
  • 누락된 숫자의 합 계산: 누락된 숫자를 발견할 때마다 해당 숫자를 sum 변수에 추가하고, missingCount를 증가시킵니다. 이를 k개의 누락된 숫자를 찾을 때까지 반복합니다.
  • 결과 반환: sum 변수에는 k개의 누락된 숫자의 합이 저장되어 있으며, 이 값을 반환하여 최종 결과로 제출합니다.

코드 설명

  1. 배열 정렬: Arrays.sort(nums)를 사용하여 주어진 배열 nums를 오름차순으로 정렬합니다. 이 과정은 O(n log n)의 시간 복잡도를 가집니다.
  2. 누락된 숫자 찾기: 정렬된 배열을 순회하면서 각 요소 nums[i]와 num 사이의 누락된 숫자들을 확인합니다.
    • nums[i]가 num보다 크면, num부터 nums[i]-1까지의 숫자가 누락된 것입니다. 이 범위의 숫자들을 sum에 추가하고 missingCount를 증가시킵니다.
    • num을 nums[i] + 1로 업데이트하여 다음 확인할 숫자를 설정합니다.
  3. 나머지 누락된 숫자 처리: 배열의 끝까지 순회한 후에도 k개의 누락된 숫자를 찾지 못한 경우, while 루프를 통해 나머지 누락된 숫자들을 처리합니다.
  4. 결과 반환: sum에 저장된 k개의 누락된 정수들의 합을 반환합니다.

📍 Plus+

시간 복잡도

  1. HashSet 초기화:
    • HashSet에 nums 배열의 모든 요소를 추가하는 과정은 O(n) 시간이 소요됩니다. 여기서 n은 nums 배열의 길이입니다.
  2. 누락된 숫자 찾기:
    • while 루프를 통해 1부터 시작하여 누락된 숫자를 찾습니다. 각 숫자가 HashSet에 존재하는지 확인하는 작업은 평균적으로 O(1)입니다.
    • 따라서 k개의 누락된 숫자를 찾기 위해 최대 k번의 반복이 필요하므로, 이 과정은 O(k) 시간이 걸립니다.

총 시간 복잡도는 O(n + k)입니다. 주어진 제약 조건에서 n과 k는 각각 최대 10^5와 10^8까지 가능하므로, 효율적인 알고리즘이 필요합니다.

공간 복잡도

  • HashSet 사용:
    • HashSet에는 nums 배열의 모든 요소가 저장됩니다. HashSet의 공간 복잡도는 일반적으로 O(n)이지만, 최악의 경우 모든 숫자가 충돌이 일어날 수 있어 공간 복잡도가 O(n)이 될 수 있습니다.

따라서 이 코드의 공간 복잡도는 O(n)입니다.

요약

  • 시간 복잡도: O(n + k) (HashSet 초기화에 O(n), 누락된 숫자 찾기에 O(k))
  • 공간 복잡도: O(n) (HashSet에 nums 배열의 모든 요소를 저장)

 

 

 

 

 

'Algorithm > 코딩테스트' 카테고리의 다른 글

[리트코드][JAVA] 2762. continuous-subarrays (연속 하위 배열)  (0) 2024.06.23
[리트코드][JAVA] 2944. minimum-number-of-coins-for-fruits (과일에 대한 최소 동전 수)  (0) 2024.06.23
[리트코드][JAVA] 2280. minimum-lines-to-represent-a-line-chart (라인 차트를 표현하기 위한 최소 라인)  (0) 2024.06.23
[리트코드][JAVA] 402. remove-k-digits (K 자리 제거)  (0) 2024.06.23
[리트코드][JAVA] 5. longest-palindromic-substring(가장 긴 팰린드롬 부분 문자열)  (1) 2024.06.19

'Algorithm/코딩테스트'의 다른글

  • 현재글[리트코드][JAVA] 2195. append-k-integers-with-minimal-sum (최소 합으로 K 정수 추가하기)

관련글

티스토리툴바