[프로그래머스] 95. 무작위로 K개의 수 뽑기

Oct 11, 2025

💡

문제 설명

랜덤으로 서로 다른 k개의 수를 저장한 배열을 만드려고 합니다. 적절한 방법이 떠오르지 않기 때문에 일정한 범위 내에서 무작위로 수를 뽑은 후, 지금까지 나온적이 없는 수이면 배열 맨 뒤에 추가하는 방식으로 만들기로 합니다.

이미 어떤 수가 무작위로 주어질지 알고 있다고 가정하고, 실제 만들어질 길이 k의 배열을 예상해봅시다.

정수 배열 arr가 주어집니다. 문제에서의 무작위의 수는 arr에 저장된 순서대로 주어질 예정이라고 했을 때, 완성될 배열을 return 하는 solution 함수를 완성해 주세요.

단, 완성될 배열의 길이가 k보다 작으면 나머지 값을 전부 -1로 채워서 return 합니다.

💡

제한사항

1 ≤ arr의 길이 ≤ 100,000

0 ≤ arr의 원소 ≤ 100,000

1 ≤ k ≤ 1,000

입출력 예

arr	k	result
[0, 1, 1, 2, 2, 3]	3	[0, 1, 2]
[0, 1, 1, 1, 1]	4	[0, 1, -1, -1]

입출력 예 설명

입출력 예 #1

앞에서부터 서로 다른 k개의 수를 골라내면 [0, 1, 2]가 됩니다. 따라서 [0, 1, 2]를 return 합니다.

입출력 예 #2

서로 다른 수의 개수가 2개 뿐이므로 서로 다른 수들을 앞에서부터 차례대로 저장한 [0, 1]에서 이후 2개의 인덱스를 -1로 채워넣은 [0, 1, -1, -1]을 return 합니다.

코드


import java.util.*;

class Solution {
    public int[] solution(int[] arr, int k) {
        List<Integer> result = new ArrayList<>();
        
        for (int i : arr) {
            
            if (!result.contains(i)) {
                result.add(i);
                
                if (result.size() == k) {
                    break;
                }
            }
        }
        
        if (result.size() != k) {
            int countToAdd = k - result.size();
            for (int i = 0; i < countToAdd; i++) {
                result.add(-1);
            }
        }
        
        return result.stream()
                     .mapToInt(i -> i)
                     .toArray();
    }
}

코드 - set 사용


import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

class Solution {
    /**
     * arr에서 중복을 제거하며 순서대로 k개의 원소를 추출하고,
     * 부족한 경우 -1로 채워 길이가 k인 배열을 반환합니다.
     * * @param arr 무작위로 주어진 수의 배열 (중복 포함 가능)
     * @param k 완성될 배열의 목표 길이
     * @return 길이가 k인 완성된 배열
     */
    public int[] solution(int[] arr, int k) {
        // 최종 결과를 순서대로 담을 List
        List<Integer> result = new ArrayList<>();
        // 중복 여부를 O(1)의 속도로 빠르게 확인하기 위한 Set (핵심 개선)
        Set<Integer> seen = new HashSet<>(); 

        // 1. arr을 순회하며 중복 없이 k개 채우기
        for (int element : arr) {
            // Set.add()는 해당 요소가 Set에 없어서 추가에 성공했을 때만 true를 반환합니다.
            // O(1) 시간 복잡도로 중복 확인과 저장을 동시에 처리합니다.
            if (seen.add(element)) { 
                result.add(element);
            }
            
            // k개를 모두 채웠다면, 더 이상 arr을 순회할 필요 없이 즉시 종료합니다.
            if (result.size() == k) {
                break;
            }
        }

        // 2. k개보다 부족한 경우 나머지 값을 -1로 채우기
        // while 루프를 사용하여 조건이 만족될 때까지 반복적으로 -1을 추가합니다.
        while (result.size() < k) {
            result.add(-1);
        }
        
        // 3. List<Integer>를 기본 타입 int[] 배열로 변환
        // 스트림 API의 mapToInt와 toArray를 사용하여 간결하게 변환합니다.
        return result.stream()
                     .mapToInt(i -> i) // Integer -> int (오토 언박싱)
                     .toArray();
    }
}