[PS] 폰켓몬

문제

프로그래머스

 

N마리의 폰켓몬이 있다

이 중 N/2 마리를 선택 가능하다

이 때, 선택 가능한 폰켓몬 종류 수의 최댓값을 구하라

풀이 1

우선, [3, 1, 2, 3] 과 같은 예시가 있을 때,

어떤 경우에 종류의 수가 결정되는지 확인해보았다

1. N/2보다 종류의 수가 크거나 같다면, N/2개 선택 가능하다 (즉 선택 가능한 포켓몬 마리 수 안에서 최대로 선택 가능하다)
2. N/2보다 종류의 수가 작다면, 종류의 수 만큼 선택 가능하다

이와 같은 결론을 내리게 되었다

종류의 수를 구하는 방법에 대해서 생각해보았다

즉, nums 배열에서 중복을 제외한 숫자들의 개수를 세야 한다

1. nums 배열을 정렬한다
2. 정렬된 배열을 for문으로 돌면서, 이전 종류와 다른 종류가 있다면 종류의 수를 카운트 +1 한다

사실 배열이 최대 10,000 길이이므로 정렬하고 또 for문 돌리는 거라 스스로도 비효율적이라고 생각했지만 일단 이렇게 구현해봤다

#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;

int solution(vector<int> nums)
{
    int answer = 0;
    int numOfType = 0;
    int numsHalf = nums.size() / 2;

    sort(nums.begin(), nums.end());

    for (int i = 1; i <= nums.size(); i++){
        if (nums[i] != nums[i-1]){
            numOfType++;
        }
    }

    if (numsHalf <= numOfType){
        answer = numsHalf;
    } else if (numsHalf > numOfType){
        answer= numOfType;
    }

    return answer;
}

내가 쓴 풀이 방법은, 불필요한 정렬을 쓰는 바람에 O(N logN)이 되어버렸다

풀고 나서 정답 체크가 되었으니, 성능 개선을 위한 방법을 찾아봤다

해시 문제인 만큼, unordered_set을 사용하는 것이 정석 풀이 방법이었다

풀이 2

내 풀이에서 두 가지 코드 개선점이 있었다.

1. unordered_set 사용하기
   • 중복 제거와 종류 수 세기를 동시에 해결
   • unordered\_set<int> types(nums.begin(), nums.end());
2. if, else문 빼고 min() 사용하기
   • if/else 대신 한 줄로 간결하게 최대값 결정
   • int limit = nums.size() / 2; return min((int)types.size(), limit);

생각해보면 크기 비교하고 값을 return하는 것은 min()이라는 간단한 내장 함수로 가능한데, 이걸 생각 못한 게 너무 바보같았다..

실제 프론트엔드 코드 구현 시에는 이런 수식 계산을 잘 안 하다보니 이런 부분에서는 부족함이 느껴졌다

이래서 알고리즘 문제를 많이 푸는게 중요한가 보다

CODE 2

#include <vector>
#include <unordered_set>
#include <algorithm>
using namespace std;

int solution(vector<int> nums) {
    unordered_set<int> types(nums.begin(), nums.end());
    int limit = nums.size() / 2;
    return min((int)types.size(), limit);
}

unordered_set을 사용하면 O(N)시간 안에 종류 수 카운트가 가능하다

또, 정렬 없이 빠르고 간단하게 사용 가능하다

회고

unordered_set이나, min()처럼 STL의 적절한 사용이 시간 복잡도와 가독성 모두를 개선해줄 수 있다는 걸 체감했다..

로직 구조 중심으로만 코드를 작성해봐서 이런 역량이 부족했던 것 같다

좀 더 열심히 풀어서 실력을 길러야 겠다