[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);
        }
    }*/
}