[프로그래머스 Lv.1 / Java] 폰켓몬

[문제]

programmers.co.kr/learn/courses/30/lessons/1845

프로그래머스

 

[문제 분석]

1. 박사님의 폰켓몬이 N마리라면, 내가 가져갈 수 있는 폰켓몬의 수는 N/2마리이다.

2. N마리중에는 같은 종류의 폰켓몬이 존재할 수 있다.

3. 나는 최대한 다양한 종류의 폰켓몬을 가져가고 싶다.

4. 이 때, 나는 최대 몇 종류의 폰켓몬을 가져갈 수 있을까?

---

[풀이]

배열, map, set 세 가지 방법으로 풀이를 해봤다. 코드는 조금씩 다르지만 원리는 비슷비슷하다.

 

● 배열을 이용한 풀이

import java.util.Arrays;

class Solution {
    public int solution(int[] nums) {
        int count = 1; //몇 종류의 폰켓몬이 있는지 넣을 변수
        int half = nums.length / 2; //내가 가져갈 수 있는 폰켓몬의 마리수

        //배열 정렬하기
        Arrays.sort(nums);

        //중복을 제거해서 서로 다른 수가 몇개인지 세기
        for (int i = 1; i < nums.length; i++) {
            if (nums[i-1] != nums[i]) { //만약 현재 숫자가 직전의 숫자와 같지 않으면
                count++; //카운트를 하나씩 늘려준다. 즉, 같은 숫자가 나오면 세지 않음!
            }
        }

        return Math.min(count, half);
    }
}

1. count변수와 half변수를 선언해준다.

    - count : 몇 종류의 폰켓몬이 있는지 넣어줄 변수. 1로 초기화한 이유는 3번에서 설명.

    - half : 박사님의 폰켓몬 N마리를 2로 나눠, 내가 가져갈 수 있는 폰켓몬의 마릿수를 넣어준 변수이다.

2. 박사님의 폰켓몬을 담은 배열 nums를 정렬해 준다.

    - why? for문을 돌리면서 인접한 인덱스의 값끼리 비교를 해서 폰켓몬의 종류를 세기 위함이다.

3. i의 범위는 1부터 nums배열의 길이만큼 잡아주고 for문을 돌려준다.

4. 현재 인덱스와 이전 인덱스의 숫자가 다르다면 다른 종류의 폰켓몬이라는 뜻이기 때문에 count++을 해준다.

    - nums[0]는 처음 나온 값이기 때문에 무조건 1종류의 폰켓몬이 있다고 생각해야 한다. 그렇기에 처음에 count 변수

     를 1로 초기화 해준 것이고, for문을 돌면서 nums[0]과 nums[1], nums[1]와 nums[2] ... ... 을 비교하여 다른 숫자

     라면 종류가 다르다는 뜻이기 때문에 count++, 같은 숫자라면 종류가 같은 폰켓몬이기 때문에 아무런 액션도 취해주

     지 않는 것이다.

5. 마지막으로 count와 half 중 더 작은 숫자를 찾아 return 한다. 사실 여기서 살짝 헷갈릴 수 있다. 왜 최솟값을 리턴시

    켜야 할까? 이번 문제의 내 풀이는 마지막이 전부 최솟값 리턴이기 때문에, 다른 풀이도 다 설명한 후에 제일 마지막에

    설명하도록 하겠다. 설명을 보기 전에 스스로 생각해 보는 것도 좋은 방법일 것 같다!

 

 

● map을 이용한 풀이

import java.util.HashMap;

class Solution {
    public int solution(int[] nums) {
        int answer = 0;
        int half = nums.length / 2; //내가 가져갈 수 있는 폰켓몬의 마리수

        //map에 넣기
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            map.put(nums[i], 1);
        }

        if (map.size() <= half) {
            answer = map.size();
        } else {
            answer = half;
        }
        
        return answer;
    }
}

1. answer변수와 half변수를 선언해준다.

    - answer : 최종 답을 return 할 변수

    - half : 박사님의 폰켓몬 N마리를 2로 나눠, 내가 가져갈 수 있는 폰켓몬의 마릿수를 넣어준 변수이다.

2. map을 선언한 후 map에 폰켓몬의 종류를 key로, 아무 숫자(나는 1)를 value로 넣어준다.

    - 폰켓몬의 종류가 몇종류인지를 세기 위함이다.

    - map은 key의 중복이 안되기 때문에 최종 map의 size가 폰켓몬의 종류수가 된다.

    - 따라서 value값은 뭐가 들어가던지 상관이 없다. (내가 필요한 건 map의 사이즈니까!)

3. map의 size와 half값을 비교하여 더 작은 값을 answer에 넣어준 후 리턴해주면 끝!

4. 3번 과정을 삼항 연산자를 이용해 더 짧게 쓸 수도 있다. 해당 코드는 아래 set에서 써보겠다!

 

 

● set을 이용한 풀이

import java.util.HashSet;

class Solution {
    public int solution(int[] nums) {
        int half = nums.length / 2;
        HashSet<Integer> set = new HashSet<>();
        
        //set에 넣기
        for (int i : nums) {
            set.add(i);
        }

        return set.size() <= half ? set.size() : half;
    }
}

1. half변수를 선언해준다.

    - half : 박사님의 폰켓몬 N마리를 2로 나눠, 내가 가져갈 수 있는 폰켓몬의 마릿수를 넣어준 변수이다.

2. set을 선언한 후 nums배열을 set에 넣어준다.

    - 폰켓몬의 종류가 몇종류인지를 세기 위함이다.

    - set은 중복이 안되기 때문에 최종 set의 size가 폰켓몬의 종류수가 된다.

3. 삼항 연산자를 사용해 set의 size와 half 중 더 작은 수를 return 한다.

    - 위 map을 사용해 푼 풀이와 거의 일치하는 풀이이다. 다른 점은 중복 제거를 위해 map대신 set을 사용했다는 점과,

      굳이 answer변수를 return하지 않고 삼항 연산자를 사용해 최솟값을 바로 return 시켰다는 점이다.

 

 

자, 그렇다면! 왜 마지막에 최솟값을 return 하는 것일까??

최솟값을 리턴한다는 것은 폰켓몬의 종류와 N/2 중 더 작은 수를 리턴한다는 것을 의미한다.

예시를 들어 설명을 해보겠다.

 

• 가정 1 : 폰켓몬 종류 > half
   만약 10마리의 폰켓몬이 있고, 폰켓몬의 종류가 모두 다르다고 가정하면 배열 풀이에서의 count나 map(set)의 size는 10이된다. 그러나 내가 가져갈 수 있는 폰켓몬은 5마리(N/2)이기 때문에 count 10과 half 5중에 더 작은 값인 5를 리턴해야한다. (내가 가져갈 수 있는 폰켓몬도 5마리, 최대 폰켓몬 종류도 5마리)

 

• 가정 2 : 폰켓몬 종류 < half
  만약 폰켓몬 10마리의 종류가 네 가지라면 배열 풀이에서의 count나 map(set)의 size는 4가 된다.
  내가 가져갈 수 있는 폰켓몬은 10/2마리로 half는 5지만 문제는 최대 몇 종류의 폰켓을 가져갈 수 있느냐? 이기 때문에 내가 가져갈 수 있는 폰켓몬 개수인 5가 아니라, 최대 종류 개수인 4를 리턴해야 한다.
  즉, 여기서도 더 작은 값을 리턴해야 한다!

 

[느낀점]

사실 이 문제는 작년 국비 학원을 다니고 두 달 후에? 처음 봤던 문제이다.

그때는 정말 어떻게 풀어야 할지 감도 잡지 못했고, 문제 이해하는 데도 엄청 오래 걸렸던 걸로 기억한다.

그 후 코딩 테스트는 거의 준비하지 못한 채 시간만 흘렀고, 취업을 한 지금 오히려 더 코딩테스트 공부를 열심히 하면서 간단(?)하게 풀 수 있게 되었다.

내 기준 프로그래머스 문제는 너무 어렵다고 느껴져서 한 두달?정도 백준을 통해 아주 쉬운 문제부터 차근차근 풀어왔고, 내가 어느정도 성장했는지 확인하기 위해 프로그래머스로 다시 코딩테스트 문제를 풀어봤다.

leval1 문제를 풀지 못한다면 엄청난 현타가 왔을 거 같은데 그래도 세 문제 정도 풀었을 때 모두 통과할 수 있었다.

엄청난 성장을 한 것은 아니지만 그래도 내 스스로에게는 칭찬을 해주고 싶다. 안 그러면 아무도 안 해주거든... 흑흑......

 

하지만 이젠 문제를 푸는 것 만이 아닌, 어떤 코드가 더 효율적인 코드인지 고민해보고 공부해봐야 할 것 같다.

누군가 '위 세 개의 풀이 중 어떤 것이 메모리를 제일 적게 사용하고, 또 제일 빠른 풀이인가요?' 하고 물어보면... 난 꿀 먹은 벙어리가 될 것 같다. 공부하자 공부!!!!