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

문제

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

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

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

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

 

 

제한사항

• 1 ≤ arr 의 길이 ≤ 100,000
  • 0 ≤ arr 의 원소 ≤ 100,000
• 1 ≤ k ≤ 1,000

 

import java.util.Set;
import java.util.LinkedHashSet;
import java.util.Iterator;

class Solution {
    public int[] solution(int[] arr, int k) {
        int[] answer = new int[k];

        Set<Integer> arrSet = new LinkedHashSet<Integer>();
        for(int num : arr) {
            arrSet.add(num);
        }

        Iterator<Integer> arrIterSet = arrSet.iterator();
        for(int i = 0; i < answer.length; i++) {
            answer[i] = (arrIterSet.hasNext()) ? arrIterSet.next() : -1;
        }
        return answer;
    }
}

처음에는 위 코드와 같이 LinkedHashSet 에 arr 의 값을 추가했다. (순서가 그대로 들어가야 하고 중복된 값은 배제하기 때문)

그리고 그 값을 순회하며 answer 배열에 넣는 방식으로 해결했다.

 

결과는 아래와 같이 나왔다.

 

 

그러면 ArrayList로 해결하면 어떨지 확인해 보자.

import java.util.ArrayList;

class Solution {
    public int[] solution(int[] arr, int k) {
        int[] answer = new int[k];
        
        ArrayList<Integer> arrList = new ArrayList<Integer>();
        for(int num : arr) {
            if(!arrList.contains(num)) {
                arrList.add(num);
            }
        }
        
        for(int i = 0; i < k; i++) {
            answer[i] = (i < arrList.size()) ? arrList.get(i) : -1;
        }
        
        return answer;
    } // arr의 길이가 길면 HashSet의 방법이 더 이득이고 짧으면 위 방법이 훨씬 빠른듯.
}

 

그 결과

아래 테스트 케이스로 갈수록 시간이 더 걸리는 듯했다.

테스트 케이스 앞 몇 부분은 오히려 ArrayList로 푸는 것이 시간이 더 짧게 걸린다.

추측건대, 아마 테스트케이스가 짧다면 ArrayList가 더 빠르고 테스트케이스가 길어질수록 HashSet이 더 이득인 것 같다.

 

출처

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