프로그래머스 포켓몬(lvl 1) 풀어보기

문제링크

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

프로그래머스

---

문제 접근법

-설명은 길지만 결국 전체 배열중 절반만 뽑을 수 있을때 가장 많이 종류의 뽑을 수있는 수는 몇인가?

---

문제 풀이법

종류이니 배열전체중 중복거르기

어차피 배열 전체중 최대 절반만 뽑을수 있으니

그냥 중복제외 배열사이즈가지고 판결하기로 결정

절반 보다 중복제외배열사이즈가 크거나같으면 절반 응답

작으면 그냥 중복제외배열 사이즈 리턴하기로 결정

---

코드

 public static int solution(int[] nums) {

        int answer = 0;

        int cn=nums.length/2;

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

        for(int n:nums){

            if(!have.contains(n)){

                have.add(n);

            }

        }

        int hs=have.size();

        if(hs>=cn){

            answer=cn;

        }else{

            answer=hs;

        }

        return answer;

    }

---

결과

---

gpt 피드백

다만 한 가지 개선할 부분이 있어. 지금 ArrayList.contains()는 리스트를 처음부터 찾아보기 때문에 O(N)이야. 그걸 for문 안에서 계속 하니까 전체적으로 최악의 경우 O(N²)이 될 수 있어.

이 문제에서는 중복 없는 값만 모으려는 거니까 Set이 딱 맞아.

---

배운점

list/set/hashmap 차이 좀더 명확하게 알게됨

나름 여러가지 만들기도 하고 했지만 기초를 모르니 부끄러움.

---