[프로그래머스][Java][Lv.1] 포켓몬

 

 

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

프로그래머스

 

내가 푼 풀이 - HashMap 사용

문제가 최대 nums/2만큼 가져갈 수 있는데, 최대한 다양한 종류를 골라야 한다.

일단 다 map에 집어넣고, map사이즈가 max보다 작거나 같으면 map.size로 출력하고 아닐 경우 max로 출력했다.

import java.util.*;
class Solution {
    public int solution(int[] nums) {
        int answer = 0;
        HashMap<Integer,Integer> map = new HashMap<>();
        for(int i = 0; i < nums.length; i ++) {
            map.put(nums[i], map.getOrDefault(nums[i],0)+1);
        }
        int max = nums.length/2;
        if (max >= map.size()) answer = map.size();
        else answer = max;
        return  answer;
    }
}

테스트 1 〉	통과 (0.03ms, 77.5MB)
테스트 2 〉	통과 (0.05ms, 77.6MB)
테스트 3 〉	통과 (0.05ms, 76.8MB)
테스트 4 〉	통과 (0.03ms, 72.1MB)
테스트 5 〉	통과 (0.07ms, 77.8MB)
테스트 6 〉	통과 (0.03ms, 86.9MB)
테스트 7 〉	통과 (0.22ms, 74.7MB)
테스트 8 〉	통과 (0.26ms, 77.9MB)
테스트 9 〉	통과 (0.38ms, 79.9MB)
테스트 10 〉	통과 (0.25ms, 78.1MB)
테스트 11 〉	통과 (0.20ms, 79.9MB)
테스트 12 〉	통과 (0.53ms, 75.4MB)
테스트 13 〉	통과 (0.77ms, 76MB)
테스트 14 〉	통과 (0.85ms, 73.2MB)
테스트 15 〉	통과 (1.26ms, 79.7MB)
테스트 16 〉	통과 (5.21ms, 81.6MB)
테스트 17 〉	통과 (5.15ms, 87.8MB)
테스트 18 〉	통과 (4.70ms, 88.7MB)
테스트 19 〉	통과 (4.77ms, 78MB)
테스트 20 〉	통과 (4.16ms, 81.3MB)

 

다른 사람 풀이 - 리스트  사용

import java.util.ArrayList;
import java.util.List;
// 리스트
public class Other1 {
    public int solution(int[] nums) {
        //1. 기존 length를 구한다.
        //2. 중복값을 제거한 length를 구한다.
        //3. 두 값중 최소값이 정답.
        List<Integer> list = new ArrayList<Integer>();
        for(int i = 0 ; i < nums.length; i++){
            if(!list.contains(nums[i])){
                list.add(nums[i]);
            }
        }

        return nums.length/2 > list.size()?list.size():nums.length/2;
    }
}

테스트 1 〉	통과 (0.04ms, 73.3MB)
테스트 2 〉	통과 (0.03ms, 74.7MB)
테스트 3 〉	통과 (0.12ms, 75.1MB)
테스트 4 〉	통과 (0.03ms, 77MB)
테스트 5 〉	통과 (0.06ms, 72.5MB)
테스트 6 〉	통과 (0.05ms, 78.9MB)
테스트 7 〉	통과 (0.60ms, 71.6MB)
테스트 8 〉	통과 (0.36ms, 74.3MB)
테스트 9 〉	통과 (0.39ms, 82.8MB)
테스트 10 〉	통과 (0.46ms, 72.3MB)
테스트 11 〉	통과 (0.26ms, 74.7MB)
테스트 12 〉	통과 (8.05ms, 73.6MB)
테스트 13 〉	통과 (3.12ms, 70.9MB)
테스트 14 〉	통과 (4.08ms, 73.8MB)
테스트 15 〉	통과 (1.45ms, 80.4MB)
테스트 16 〉	통과 (34.25ms, 86.8MB)
테스트 17 〉	통과 (39.69ms, 78.6MB)
테스트 18 〉	통과 (32.61ms, 83.5MB)
테스트 19 〉	통과 (12.08ms, 78.7MB)
테스트 20 〉	통과 (1.98ms, 78.4MB)

내가 푼 풀이랑 비교

두 코드 간의 성능 차이는 주로 데이터 구조와 알고리즘 선택 때문입니다.

1. 데이터 구조 선택: 

 

   - 첫 번째 코드(`Solution`)는 `HashMap`을 사용하여 중복된 숫자의 개수를 효율적으로 추적합니다. `HashMap`은 해시 맵을 사용하기 때문에 중복 확인 및 카운트를 더 효율적으로 수행할 수 있습니다.

   - 두 번째 코드(`Other1`)는 `ArrayList`를 사용하여 중복을 제거하고 유일한 숫자를 추적합니다. `ArrayList`는 중복을 제거하기 위해 순차적으로 원소를 확인해야 하며, `contains` 메서드를 사용하여 중복을 확인하기 때문에 성능상 더 많은 시간이 소요될 수 있습니다.

2. 알고리즘 선택:

   - 두 코드 모두 최대로 선택할 수 있는 고유한 숫자의 개수를 계산하는 목적으로 `nums.length/2`를 사용하고 있습니다. 그러나 첫 번째 코드에서는 중복된 숫자의 개수를 `HashMap`을 통해 미리 카운트하고 있기 때문에 중복된 숫자의 수와 `nums.length/2`를 비교하여 결과를 계산하는 것이 효율적입니다.

종합적으로, 첫 번째 코드(`Solution`)가 더 효율적인 데이터 구조와 알고리즘을 사용하여 성능이 더 좋을 것으로 예상됩니다. 

 

 

다른 사람 풀이 - HashSet 사용

내 코드랑 성능차이 별로 없긴하지만 중복을 제거하는 HashSet이 조금 더 빠른듯하다

import java.util.*;
// 해쉬셋
public class Solution {
    public int solution(int[] nums) {
        HashSet<Integer> a = new HashSet<>();
        for (int i = 0; i < nums.length; i++) {
            a.add(nums[i]);
        }
        return (nums.length / 2 > a.size()) ? a.size() : nums.length / 2;
    }
}

테스트 1 〉	통과 (0.07ms, 78.2MB)
테스트 2 〉	통과 (0.12ms, 78MB)
테스트 3 〉	통과 (0.06ms, 73.1MB)
테스트 4 〉	통과 (0.12ms, 74.9MB)
테스트 5 〉	통과 (0.05ms, 71.9MB)
테스트 6 〉	통과 (0.08ms, 77.6MB)
테스트 7 〉	통과 (0.31ms, 78.5MB)
테스트 8 〉	통과 (0.21ms, 76.5MB)
테스트 9 〉	통과 (0.24ms, 76.9MB)
테스트 10 〉	통과 (0.25ms, 72.2MB)
테스트 11 〉	통과 (0.22ms, 75.9MB)
테스트 12 〉	통과 (0.29ms, 75.2MB)
테스트 13 〉	통과 (0.47ms, 76.4MB)
테스트 14 〉	통과 (0.83ms, 73.3MB)
테스트 15 〉	통과 (0.81ms, 72.6MB)
테스트 16 〉	통과 (6.60ms, 76.3MB)
테스트 17 〉	통과 (3.84ms, 80MB)
테스트 18 〉	통과 (2.85ms, 67.9MB)
테스트 19 〉	통과 (2.25ms, 77.7MB)
테스트 20 〉	통과 (2.14ms, 75.7MB)