프로그래머스-폰켓몬

목차

1.문제

2.문제 해결과정

3.타인의 코드 분석

 

1.문제

 

 

2.문제 해결과정

2-1.요구사항

• N마리 폰켓몬의 종류 번호가 담긴 배열 nums가 매개변수로 주어질 때, N/2마리의 폰켓몬을 선택하는 방법 중, 가장 많은 종류의 폰켓몬을 선택하는 방법을 찾아, 그때의 폰켓몬 종류 번호의 개수를 return 하는 것
• nums의 배열은 1차원 배열이고 1이상 10000 이하이고 항상 짝수이다.
• 선택을 할 수 있는 폰켓몬의 종류 개수의 최댓값 하나만 return 한다. 

2-2.문제의 접근 과정

• 우선은 이 문제에서 처음으로 접근을 하는 것은 전체 배열 nums에서 절반인 nums.length/2만 가져갈 수 있다는것.
• 입출력의 예를 봤을때 알 수 있는 것은 배열에 중복된 폰켓몬은 배제된다. -> 중복을 허용하지 않는다.
• 배열에 있는 중복을 배제를 하기 위해서 사용하기 위해서 Set을 사용

2-3.문제의 의사코드

• 배열의 절반길이인 count를 초기화 함(nums.length) 
• Set<Integer> set = new HashSet<>(); 을 초기화함.
• nums를 반복문으로 돌리면서 set에 넣기 -> 중복이 제거됨.
• set에 들어간 길이와 배열의 길이 절반인 count를 비교  
  • count 가 작으면 count를 반대면 set.size()를 answer로 리턴을 한다. 

import java.util.*;

class Solution {
    public int solution(int[] nums) {
        int answer = 0;
        // 문제의 요구사항에서 배열의 길이에 절반
        int count = nums.length/2;
        // 배열의 중복을 제거하기 위해서 HashSet을 선언
        Set<Integer> set = new HashSet<>();
        // 배열의 값을 set에 넣기.
        for(int r : nums) {
            set.add(r);
        }
        // 배열의 길이(절반)와 set에 저장된 길이와 비교
        if(count <= set.size()) {
            answer = count;
        } else {
            answer = set.size();
            return answer;
        }
        return answer;
    }
}

3.타인의 코드 분석

이번 문제는 Set을 활용해서 문제를 풀었는데 다른 사람들이 푼 코드를 보면 HashSet이 아닌 Map,List를 활용해서 푼 케이스와 간략하게 스트림을 해서 푼 케이스가 있었습니다. 

 

3-1. 스트림을 활용해서 푼 케이스

 

 

스트림을 활용을 해서 우선은 int타입을 Integer타입으로 박싱을 하고 배열의 타입을 Set으로 변경을 하기 위해서 toSet을 사용을 했고 set에 있는 사이즈와 배열의 길이에 절반의 길이 중에 작은것을 Integer.min으로 해서 출력을 하는 방식입니다. 

 

이 방식의 경우에는 가독성이 뛰어나지만, boxed() 메서드에서 원시타입을 객체타입으로 변현을 하는 과정에서 int 타입을 하나하나 Integer로 감싸는 과정인데, 이 과정에서 매번 새로 객체를 생성을 해야되기에 참조 비용이 추가로 발생한다는 단점이 있습니다. 

 

 

3-2. List 를 활용해서 푼 케이스

 

 

이 방법의 경우에는

 

1.List를 선언을 하고 nums만큼 반복문을 돌립니다.

2.리스트에 nums에 있는 값이 포함이 되어있지 않으면 리스트에 추가를 합니다.->중복을 제거

3.마지막으로 nums.length/2 가 리스트의 크기랑 비교를 했을때 리스트가 작으면 리스트의  크기를 아니면 배열의 절반을 리턴합니다.

 

이 방법으로 구현을 하면 직관적이지만 List의 contains()는 내부적으로 전체를 순회하므로 O(N)의 시간 복잡도를 가집니다. 이를 전체 배열(N)만큼 반복하면 O(N^2)의 성능이 나옵니다. 데이터가 작을 땐 상관없지만, 데이터가 수십만 건으로 늘어나면 치명적인 성능 저하가 발생한다는 단점이 있습니다.

 

 

3-3. Map을 활용해서 푼 케이스

 

 

이 방식의 경우에는

 

1.nums의 길이만큼 반복문을 돌려서 map에 키값을 넣습니다.

2.키값에 폰켓몬을 넣으면 중복이 되지 않기 때문에 중복을 제거를 하는 역할을 할 수 있습니다. 

3.마지막 return 부분에서 삼항연산자를 사용해서 map의 사이즈와 nums의 길이에 절반을 비교해서 map이  크면 절반 길이를 아니면 map의 길이를 리턴합니다.

 

HashMap을 사용해서 하는 방법은 단순히 문제의 요구사항에 충족을 시켜서 중복제거만 필요하면 HashSet이 훨씬 직관적입니다. 하지만 추가적으로 요구사항이 추가가 된다면 Map을 사용을 해보는것도 나쁘지 않다고 생각합니다. 

 

 

문제 출저

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

프로그래머스