[JAVA] 프로그래머스 폰켓몬

HashSet을 이용해 중복제거하는 문제이다.

 

처음 문제를 봤을때 dfs combination 문제인줄 알고 dfs로 모두 구했더니 시간초과가 발생했다.

 

다시 생각해보니 nums.length/2 미만인경우 아니라면 최대한 많이뽑아도 nums.length/2개이니 해당 값을 return해주면 되는 간단한 문제였다.

 

if문을 할때 종이로 쓰는 습관을 들여야겠다.

 

import java.util.HashSet;
import java.util.Set;

class Solution {
​​​​static int[] result;
​​​​static int max=0;
​​​​public int solution(int[] nums) {
​​​​​​​​int answer = 0;
​​​​​​​​result = new int[nums.length/2];
​​​​​​​​Set<Integer> s = new HashSet<>();
​​​​​​​​for(int n : nums) s.add(n);
​​​​​​​​//Integer[] newArr = s.toArray(new Integer[0]);
​​​​​​​​//System.out.println(Arrays.toString(newArr));

​​​​​​​​if(s.size()<nums.length/2) return s.size();
​​​​​​​​else return nums.length/2;

​​​​​​​​//comb(nums, nums.length, nums.length/2);

​​​​​​​​//return max;
​​​​}

​​/*  public static void comb(int[] newArr, int n, int r){
        if(r==0){
            Set<Integer> set = new HashSet<>();
            for(int rst : result) set.add(rst);
            max = Math.max(max,set.size());
        }else if(n<r){
            return;
        }else{
            result[r-1] = newArr[n-1];
            comb(newArr, n-1, r-1);
            comb(newArr, n-1, r);
        }
    }*/
}