프로그래머스(JAVA) - Hash (폰켓몬)

문제정리

N마리의 폰켓몬 중 N/2마리를 가져가도 좋다
최대한 많은 종류의 폰켓몬을 포함해서 N/2마리를 선택, N 마리 폰켓몬의 종류 번호가 담긴 배열 nums가 매개변수로 주어질 때, N/2마리의 폰켓몬을 선택하는 방법 중, 가장 많은 종류의 폰켓몬을 선택하는 방법을 찾아 종류의 개수의 최댓값 하나만 return
nums 길이는 항상 짝수

 

처음 작성한 코드

import java.util.ArrayList;
import java.util.List;

class Solution {
    public int solution(int[] nums) {
        int answer = 0;

        List <Integer> list = new ArrayList<Integer>();

        for(int i = 0; i < nums.length; i++) {
            if(list.contains(nums[i])) {
                continue;
            }
            list.add(nums[i]);
            if(list.size() == nums.length / 2 ) {
                break;
            }
        }
        answer = list.size();
        return answer;
    }
}

 

기존에 자주 사용했던 ArrayList를 활용해서 문제 해결 list.contains(num[i])를 사용해서 이미 리스트에 있는 폰켓몬이면 continue 하고 아니면 add 리스트 최대 길이가 실제 가져갈 수 있는 최대 개수를 넘어가게 되면 반복문을 멈추고, 그 값을 return해서 값을 얻어낸다.

결과적으로는 성공으로 떴지만, 다른 사람들 코드를 찾아보니 보통 HashSet을 사용해서 해결

 

최종 코드

class Solution {
    public int solution(int[] nums) {
        int answer = 0;
        HashSet<Integer> set = new HashSet<>();

        for(int i = 0; i < nums.length; i++){
            set.add(nums[i]);
        }

        int get = nums.length / 2 ;

        if(set.size() > get){
           answer = get;
        }else {
            answer = set.size();
        }

        return answer;
    }
}

 

ArrayList.contains()는 시간 복잡도가 O(N)으로 list.contains(num[i])는 리스트의 크기가 커질수록 느려진다고 한다. HashSet을 사용해서 O(1)로 중복 검사를 수행한다.
(set.add(num)을 사용하면 중복이 자동으로 제거됨 -> O(1) 연산)

시간은..

 

코드 개선

// for(int i = 0; i < nums.length; i++){
//            set.add(nums[i]);
//        }
        

for (int num : nums) { // 모든 폰켓몬을 순회하며 중복 제거
	set.add(num);
}


//        int get = nums.length / 2 ;

//        if(set.size() > get){
//           answer = get;
//        }else {
//            answer = set.size();
//        }

//        return answer;


// 최대로 가질 수 있는 폰켓몬 종류 수
return Math.min(set.size(), num.length / 2);
 

내가 작성한 최종 코드도 기능적으로는 문제가 없지만 Math.min()을 사용하니 확실히 간결해짐..