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

06 Feb 2025 in Study / Coding Test

• ☑️ 문제
• ☑️ 풀이
  • 첫 번째 풀이 (실패)
  • 두 번째 풀이 (성공)
  • 세 번째 풀이 (성공)

☑️ 문제

프로그래머스 181858

☑️ 풀이

첫 번째 풀이 (실패)

import java.util.*;

class Solution {
    public int[] solution(int[] arr, int k) {
        int[] answer = new int[k];
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < arr.length; i++) {
            if (set.size() < k) {
                set.add(arr[i]);
            } else if (set.size() == k) {
                break;
            }
        }
        
        if (set.size() < k) {
            for (int i = 0; i < k - set.size(); i++) {
                answer[answer.length - i - 1] = -1;
            }
        }
        
        Iterator<Integer> iter = set.iterator();
        int idx = 0;
        while(iter.hasNext()) {
            answer[idx++] = iter.next();
        }
        
        
        return answer;
    }
}

• Set 을 사용해서 풀었고, 테케는 통과했는데 채점에서 모두 틀렸다.
• Set 은 순서를 보장하지 않는다는 특징을 가지고 있는데, 이 문제에서는 arr 에 저장된 순서대로 담아야 하기 때문에 순서를 지켜야 한다.

두 번째 풀이 (성공)

//시간: 55.19ms
//메모리: 97.5MB

import java.util.*;

class Solution {
    public int[] solution(int[] arr, int k) {
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < arr.length; i++) {
            int num = arr[i];
            boolean exists = false;

            if (list.size() == k) {
                break;
            }

            for (int j = 0; j < list.size(); j++) {
                if (list.get(j) == num) {
                    exists = true;
                }
            }

            if (!exists) {
                list.add(num);
            }
        }

        int[] answer = new int[k];
        Arrays.fill(answer, -1);

        for (int i = 0; i < list.size(); i++) {
            answer[i] = list.get(i);
        }

        return answer;
    }
}

• List 를 사용해서 arr 의 순서를 유지하면서 중복을 제거했다.
• 하지만 for문 을 사용하여 중복검사를 하였기 때문에 시간이 너무 오래 걸렸다.

세 번째 풀이 (성공)

//시간: 15.05ms
//메모리: 82.5MB

import java.util.*;

class Solution {
    public int[] solution(int[] arr, int k) {
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < arr.length; i++) {
            int num = arr[i];

            if (list.size() == k) {
                break;
            }

            if (!list.contains(num)) {
                list.add(num);
            }
        }

        int[] answer = new int[k];
        Arrays.fill(answer, -1);

        for (int i = 0; i < list.size(); i++) {
            answer[i] = list.get(i);
        }

        return answer;
    }
}

• for문 대신 contains() 메서드를 사용하여 중복 체크를 하니, 코드도 간결해지고 시간도 줄어들었다.