[프로그래머스-Java] 해시 1, 2번

RedPanda·2022년 8월 3일

[알고리즘] Java

목록 보기

14/16

📌 폰켓몬

📢 문제 설명

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

🔑 풀이

차근차근히 생각을 해보자.

종류는 숫자로 구분하여 배열에 들어간다.

폰켓몬이 들어있는 배열에서 N/2마리만큼 뽑는다.

가장 많은 종류를 뽑아야 한다.

가장 많은 종류를 뽑는다면 배열의 요소가 달라야 한다. 따라서 중복을 제거한 배열의 길이만 반환하면 쉽게 해결할 수 있다.
그러나 조건1의 경우에 [3,1,2,3]이면 종류는 3개이지만 뽑는 마릿수는 n/2이므로 최대 2개이다. 그러므로 결과값이 n/2가 넘으면 n/2값을 반환해야 한다.

나는 임의로 벡터에 처음값을 넣어 배열의 길이만큼 반복하였다. 반복하는 동안 벡터와 배열의 인덱스를 비교하여 같으면 다음으로 넘어가도록 코드를 짰다.

import java.util.Vector;

class Solution {
    public int solution(int[] nums) {
        int answer = 0;
        Vector<Integer> vec = new Vector<Integer>();
        int half_num = nums.length / 2;
        vec.add(nums[0]);
        
        for(int i = 1; i < nums.length; i++){
            boolean is_data = false;
            for(int j = 0; j < vec.size(); j++){
                if(nums[i] == vec.get(j)){
                    is_data = true;
                    break;
                }
            }
            if(!is_data) vec.add(nums[i]);
        }
        answer = vec.size();
        if(answer > half_num) answer = half_num; 
        
        return answer;
    }
}

중복을 제거하는 부분에서 이중 반복문을 사용하였는데, HashSet이라는 컬렉션을 사용하여 중복제거를 미리 해놓는 방법도 있었다.

이중으로 반복을 하는 것보다 바로 중복을 제거할 수 있어 실행시간이 훨씬 줄어든다.

>>HashSet으로 해결한 풀이

📌 완주하지 못한 선수

📢 문제 설명

수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다.
마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요.

🔑 풀이

위의 문제보다 이해하는 데에는 많은 시간이 걸리지 않았다.
간단히 말하자면 이렇다.

participant는 참가자 전원의 배열, completion은 완주한 인원의 배열이다.

participant 배열에서 completion 배열을 빼고 남은 한사람을 찾아라.

이번에도 이중반복문으로 해결하면 될 것 같았다.

participant의 새로운 벡터에서 completion의 요소들을 pop해주면 될 것 같았다.
그러나 100,000번이 최대이므로 이중 반복문으로는 너무 많은 반복이 계속 되었고, 결과적으로 실행시간이 초과되었다.

그래서 효과적인 방법을 찾아보았고, 미리 오름차순으로 정렬하는 Arrays.sort 메소드를 발견했다.

participant 정렬, completion 정렬

completion의 길이만큼 participant의 각 요소들과 비교

다른 요소가 있으면 종료 후 반환, 끝까지 간다면 participant의 마지막 요소를 반환

이 방법으로 검색한다면 배열의 길이만큼만 반복하면 해결된다.

import java.util.Arrays;

class Solution {
    public String solution(String[] participant, String[] completion) {
        String answer = "";
        Arrays.sort(participant);
        Arrays.sort(completion);
        boolean find = false;
        
        for(int i = 0; i < completion.length; i++){
            if(!participant[i].equals(completion[i])){
                answer = participant[i];
                find = true;
                break;
            }
            find = false;
        }
        if(!find) answer = participant[completion.length];
        
        return answer;
    }
}