알고리즘/문제풀이

프로그래머스[폰켓몬] 정답 - Java

정헤이 2024. 2. 21. 13:45

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

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

 

 

개인적으로 인프런 자바 알고리즘 강의를 통해 문제를 풀어보고 있는데, 프로그래머스 문제들도 병행해서 같이 풀면 좋을것 같다는 생각에

고득점 Kit 문제들을 순서대로 풀어본다.

 

문제 :

당신은 폰켓몬을 잡기 위한 오랜 여행 끝에, 박사님의 연구실에 도착했습니다. 박사님은 당신에게 자신의 연구실에 있는 N 마리의 폰켓몬 중에서 N/2마리를 가져가도 좋다고 했습니다. 박사님 연구실의 폰켓몬은 종류에 따라 번호를 붙여 구분합니다. 따라서 같은 종류의 폰켓몬은 같은 번호를 가지고 있습니다. 예를 들어 연구실에 4마리의 폰켓몬이 있고, 폰켓몬의 종류 번호가 [3, 1, 2, 3]이라면 이는 3 폰켓몬 마리, 1 폰켓몬 마리, 2 폰켓몬 마리가 있음을 나타냅니다. 이때, 4마리의 폰켓몬 2마리를 고르는 방법은 다음과 같이 6가지가 있습니다.  번째(3), 번째(1) 폰켓몬을 선택 번째(3), 번째(2) 폰켓몬을 선택 번째(3), 번째(3) 폰켓몬을 선택 번째(1), 번째(2) 폰켓몬을 선택 번째(1), 번째(3) 폰켓몬을 선택 번째(2), 번째(3) 폰켓몬을 선택 이때, 번째(3) 폰켓몬과 번째(3) 폰켓몬을 선택하는 방법은 종류(3 폰켓몬 마리) 폰켓몬만 가질 있지만, 다른 방법들은 모두 종류의 폰켓몬을 가질 있습니다. 따라서 예시에서 가질 있는 폰켓몬 종류 수의 최댓값은 2 됩니다. 당신은 최대한 다양한 종류의 폰켓몬을 가지길 원하기 때문에, 최대한 많은 종류의 폰켓몬을 포함해서 N/2마리를 선택하려 합니다. N마리 폰켓몬의 종류 번호가 담긴 배열 nums 매개변수로 주어질 , N/2마리의 폰켓몬을 선택하는 방법 , 가장 많은 종류의 폰켓몬을 선택하는 방법을 찾아, 그때의 폰켓몬 종류 번호의 개수를 return 하도록 solution 함수를 완성해주세요.

문제 요약:

1. nums[] 라는 폰켓몬 종류들이 담긴 정수형 배열이 주어진다.
2. 가져갈 수 있는 폰켓몬의 최대수는 nums.length / 2
3. 가져갈 수 있는 최대 폰켓몬의 수를 구해라.

 

코드 + 풀이 :

* 해를 구하기 위한 자료형으로 중복된 값을 담아두지 않는 TreeSet으로 결정했다.

  1. int len = 골라야하는 폰켓몬의 수 , int size = 중복제거된 폰켓몬 종류의 수 변수세팅

  2. 만약 골라야하는 수는 3 인데 중복제거된 폰켓몬 종류의 수는2 일때. 이때는 고를 수 있는 수가 3인데

중복되지 않게 고를 수 있는 최선이 결국 2이기 때문에 size를 리턴.

  3. 2번 경우가 아니라면 고를 수 있는 폰켓몬의 수만큼 중복제거된 폰켓몬을 가질 수 있기에 len을 리턴.

import java.util.*;
class Solution {
    public int solution(int[] nums) {
        int answer = 0;
        int len = nums.length / 2;
        TreeSet <Integer> set = new TreeSet<>();
        for(int i: nums)set.add(i);
        int size = set.size();
        if(len > size) return size;
        else return len;
    }
}

정답처리 된 코드이다. 그런데

다른 사람들은 어떻게 풀었나 구경하는데 나랑 같은 방식으로 푼 사람이 있었다.

 

 

 

그런데!!!!!

나는 TreeSet으로 선언했는데 다른 분은 HashSet으로 푼 것이다.

아.. 나는 알고리즘 강의를 듣다 이와 비슷한 문제를 강사님께서 TreeSet으로 푸셔서 TreeSet을 선택한 것이었다.

set이 중복된 값을 저장하지 않는다는건 알지만 그래도 구체적으로 알면 좋지 않은가. 

TreeSet VS HashSet 의 차이점 정리까지 하려고 한다.

1. TreeSet은 내부적으로 TreeMap을 사용하고 기본적으로 오름차순 정렬 시킨다
2. HashSet은 내부적으로 해시 알고리즘 사용하여 속도가 일반적으로 TreeSet보다 빠르다.

 

결론 :

Set자료형을 쓰면서 정렬된 순서를 유지해야 하거나 큰 값 or 작은 값을 많이 사용해야 한다면 TreeSet을 쓰고

그게 아니라면 HashSet을 쓰면되겠다! 만약 정렬이 아닌 저장순서를 기억해야 한다면 LinkedHashSet을 이용하자