[프로그래머스] 폰켓몬(JAVA) 풀이

폰켓몬

---

🔗 문제 링크

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

프로그래머스

 

---

 

🚨맨 처음에 문제 푸는 방향성을 잘못 잡아서 먼 산을 돌아왔다 (..)

조합(Combination)을 통해서 풀었는데 브루트포스(완전탐색) 방식으로 nums.length가 커질수록 시간복잡도가 O(N!)에 가까워진다. 가장 비효율적이고 타임아웃이 나므로 수학적 사고 + 자료구조(Set)를 사용해서 풀어줘야 한다.

✅ 효율적으로 풀기

[문제 탐색]

• 선택할 수 있는 최대 수 : nums/2
• 폰켓몬 종류의 수 : Set.size() (중복제거)
• answer : 총 포켓몬 종류 수, nums/2 중 작은 

[코드 설계]

1. 자료구조 Set을 사용하여 중복 값을 제거하고 종류의 수 구하기
2. 선택할 수 있는 최대 수 구하기
3. 구한 두 수 중 작은 값이 정답

[가능한 시간복잡도]

Set의 add의 시간복잡도는 O(1) 이기 때문에 for문에서 N만큼 반복 : 시간 복잡도 O(N)

나머지 연산들은 O(1)로 상수 시간 연산

=> 전체 시간 복잡도 O(N)

✅풀이 코드

import java.util.*;

class Solution {
    public int solution(int[] nums) {
        int answer = 0;
        
        HashSet<Integer> set = new HashSet<>();
        for(int n : nums){
            set.add(n);
        }

        answer = Math.min(set.size(), nums.length/2);
        
        return answer;
    }
    
}