[프로그래머스/ List, HashSet] 폰켓몬 (java)

문제 보기

소요 시간

17분 소요

문제

2/N
종류에 따른 번호 부여
가장 많은 종류의 폰켓몬을 선택하는 방법을 찾아, 그때의 폰켓몬 종류 번호의 개수를 return

문제풀이

1. 배열,이중 반복문 풀이 -> 구현 중단

처음엔 이중반복문을 사용해 배열 원소 비교를 통해 구현하려 했다. 이전 원소와 같은 원소를 만날 시, 종류 수++, 다음 원소 비교
하지만, 다음 원소를 비교하는 것이 막상 떠올리지 않고, O(n^2)의 안좋은 시간복잡도로 다른 방법을 생각

정리하면서 생각해보니, 같은 원소를 만날 시, 해당 원소를 0처리 하는 방법이 있을 거 같다. 그런데 이것도 만난 원소 외에 다른 같은 종류의 원소를 0 처리해야 하므로 추가 기능 구현을 해야하니 복잡할 거 같다.

2.리스트 사용, 종류 담은 리스트 -> 구현 성공

import java.util.*;

class Solution {
    public int solution(int[] nums) {
        int count = nums.length/2;
        int answer = 0;
        List<Integer> kind = new ArrayList<>();

        for(int i = 0 ; i < nums.length ; i++) {
            if (kind.contains(nums[i])==false){
                kind.add(nums[i]);
            }
        }
        int size= kind.size();
        
        if(count<=size) answer = count;
        else answer = size;
        
        return answer;
    }
}

풀이 방식

• count : 골라야 하는 폰켓몬 수 (nums 크기 / 2)
• List kind : nums의 종류 리스트
• size : nums의 종류 수 (kind 리스트의 크기)

1. 배열을 순회하면서 kind 리스트에 없는 원소를 만날 시, kind에 추가하는 반복문을 실행한다.
2. count가 size보다 같거나 작을 시, answer는 count이고,
   count가 size보다 클 시, answer는 size이다.

성능 검사

O(N^2)

알고리즘 로직 구현은 쉬웠으나, List 문법 헷갈려서 시간 소요

• List 선언
• List.contains 함수

3. HashSet

HashSet
: Set 인터페이스에서 지원하는 구현 클래스이다.
순서대로 입력되지 않고, 일정하게 유지되지 않는다.
HashSet은 null 요소도 허용한다.
중복을 허용하지 않는다.

참고 : https://crazykim2.tistory.com/474

import java.util.*;
class Solution {
  public int solution(int[] nums) {
      int count = nums.length / 2;
      
      HashSet<Integer> kind = new HashSet<>();

      for (int num : nums) {
          kind.add(num);
      }

      return Math.min(kind.size(), count);
  }
}

풀이 방식

HashMap의 중복을 허용하지 않는 특성을 이용한다.
따라서, List 풀이와 달리, 중복 검사 순회도 필요없어, 성능 또한 개선된다.

성능 검사

O(N)