Skip to main content

52. [Java] 무작위로 K개의 수 뽑기

https://school.programmers.co.kr/learn/courses/30/lessons/181859

  • 무작위로 뽑은 수들이 arr 배열에 순서대로 주어짐
  • 이 수들을 앞에서부터 확인하면서 중복 없이 k개까지만 저장
  • 만약 중복을 제거한 결과가 k개보다 작으면, 남는 자리는 -1로 채움
  • 최종적으로 길이가 정확히 k인 배열을 만들어 반환
  • 1 ≤ arr의 길이 ≤ 100,000
    • 0 ≤ arr의 원소 ≤ 100,000
  • 1 ≤ k ≤ 1,000

정답코드 (List)

import java.util.*; 

class Solution {
    public int[] solution(int[] arr, int k) {
        List<Integer> result = new ArrayList<>(); // 결과를 저장할 리스트
        Set<Integer> seen = new HashSet<>();      // 중복 체크를 위한 Set

        // arr 배열을 앞에서부터 하나씩 확인
        for (int num : arr) {
            // 아직 나온 적 없는 숫자라면
            if (!seen.contains(num)) {
                seen.add(num);         // 중복 체크용 Set에 추가
                result.add(num);       // 결과 리스트에도 추가

                // k개를 모두 모았으면 더 이상 반복할 필요 없음
                if (result.size() == k) break;
            }
        }

        // 만약 결과 리스트가 k개보다 작으면
        // 부족한 부분을 -1로 채움
        while (result.size() < k) {
            result.add(-1);
        }

        // List<Integer> → int[]
        return result.stream().mapToInt(Integer::intValue).toArray();
    }
}
  • 입력: 정수 배열 arr, 정수 k
  • 출력: 중복 없이 k개의 수가 들어간 배열
    (k개가 안 되면 -1로 채운 길이 k 배열)

정답코드 (Array, 내가 푼 코드)

import java.util.*;

class Solution {
    public int[] solution(int[] arr, int k) {
        int[] answer = new int[k];           // k칸짜리 배열 생성
        Arrays.fill(answer, -1);             // 일단 전부 -1로 초기화
        Set<Integer> used = new HashSet<>(); // 중복 체크용 Set

        int idx = 0; // answer에 값을 채워넣을 인덱스

        for (int num : arr) {
            if (!used.contains(num)) {
                used.add(num);         // 중복 체크용으로 추가
                answer[idx++] = num;   // 배열에 값 넣고 인덱스 증가

                if (idx == k) break;   // k칸 모두 채웠으면 중단
            }
        }

        return answer;
    }
}
  1. k칸짜리 배열 만들​기
  2. 배열 모두 -1로 초기화
  3. arr에서 중복 없이 앞에서부터 수를 골라 채우기
    → 중복 아닌 숫자만 set에 추가
    → 배열에 값 넣고 인덱스 추가
    → k칸 모두 채웠으면 중단

idx 범위

if (idx == k) break;   // k칸 모두 채웠으면 중단

if (idx == k) break;가 왜 k - 1이 아닌지 헷갈렸다.
idx가 배열 인덱스로 쓰였기 때문에 0부터 시작에서 k-1까지라고 착각하기 쉽다.
하지만 실제로 idx는 인덱스의 역할이 아니라 "몇 개 넣었는지"를 세는 변수이다.
즉, idx == k라는 건 k개의 값을 이미 다 넣었다는 뜻이다. 

int[] answer = new int[k];      // 길이 k인 배열
int idx = 0;                    // 0개 넣은 상태로 시작

값을 넣을 때:

answer[idx++] = num;  // num을 넣고 idx는 1 증가
  • 첫 번째 값 넣고 → idx == 1
  • 두 번째 값 넣고 → idx == 2
  • 세 번째 값 넣고 → idx == 3

그리고 k == 3이면, 값을 3개 넣은 시점이 idx == k이다.
그럼 더는 넣으면 안 되니까 break한다.

  • idx == k는 "k개 넣었으니 그만 넣자"는 뜻 → ✔️ 맞는 코드
  • idx == k - 1이면 "마지막 인덱스 전까지만 넣자"는 뜻 → ❌ 틀린 기준

Stream을 사용해서 푼 코드 (최석현 님)

import java.util.Arrays;
import java.util.stream.IntStream;

class Solution {
    public int[] solution(int[] arr, int k) {
        return IntStream.concat(
        Arrays.stream(arr).distinct(),          // 1. arr 배열에서 중복 제거된 스트림 생성
        IntStream.range(0, k).map(i -> -1)     // 2. -1로 채울 k개 크기의 스트림 생성
    ).limit(k)                                 // 3. 두 스트림을 합친 후, 최대 k개까지만 자름
    .toArray();                               // 4. 최종 결과를 int[] 배열로 변환하여 반환
    }
}
  • Arrays.stream(arr).distinct()
    • arr 배열을 스트림으로 만들고, 중복되는 숫자는 한 번만 나오도록 필터링한다.
  • IntStream.range(0, k).map(i -> -1)
    • 0부터 k-1까지 숫자를 순서대로 만드는 스트림을 만들고,
    • 각 숫자를 모두 -1로 바꿔서 길이가 k인 -1 스트림을 만든다.
  • IntStream.concat(...)
    • 중복 제거된 arr 스트림과 -1로 채운 스트림을 앞뒤로 이어붙여서 하나의 스트림으로 만든다.
  • .limit(k)
    • 스트림 길이를 최대 k개로 제한해서, 만약 중복 제거된 수가 k보다 적으면 나머지를 -1로 채우고,
    • 많으면 처음 k개까지만 가져오도록 한다
  • .toArray()
    • 스트림을 다시 정수 배열로 변환해서 반환하면 끝



Back to top