[프로그래머스] 폰켓몬 ( by using JavaScript )

문제

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

코딩테스트 연습 - 폰켓몬

 

접근법

 

1) Hash map

 

문제에서 해결 해야 할 중요한 문제점은 아래의 2개이다.

 

1) ( 총 폰켓몬 수 / 2 ) 을 데려간다.

2) 이 때, 최대한 많은 종류의 "폰켓몬" 을 데려간다.

 

1번째는 받은 Array의 길이를 2로 나눠주는거라 문제는 없지만, 어떻게 하면 최대한 많은 수의 폰켓몬을 데려 갈 수 있을지가 조금 더 어렵게 다가왔다.

 

고민을 하던 끝에 결과적으로는 종류 별로 폰켓몬을 정리하여, 정리된 폰켓몬의 종류가 데려갈 수 있는 폰켓몬의 수보다 적으면 아무리 많은 수의 폰켓몬을 데려가도 종류의 수는 증가 하지 않는다는 사실을 알게 되어 이를 바탕으로 문제를 해결 하였다.

 

// 해시를 이용한 문제 풀이
function solution(nums) {
  let map = {};
  let maxCount = parseInt(nums.length / 2);

  for (let i = 0; i < nums.length; i++) {
    map[nums[i]] = (map[nums[i]] || 0) + 1;
  }

  let objectLength = Object.keys(map).length;

  return objectLength <= maxCount ? objectLength : maxCount;
}

테스트 1 〉	통과 (0.09ms, 30.2MB)
테스트 2 〉	통과 (0.08ms, 30.1MB)
테스트 3 〉	통과 (0.06ms, 30MB)
테스트 4 〉	통과 (0.07ms, 29.9MB)
테스트 5 〉	통과 (0.07ms, 30.1MB)
테스트 6 〉	통과 (0.07ms, 29.9MB)
테스트 7 〉	통과 (0.33ms, 30.1MB)
테스트 8 〉	통과 (0.28ms, 30.1MB)
테스트 9 〉	통과 (0.33ms, 30.2MB)
테스트 10 〉	통과 (0.32ms, 30.3MB)
테스트 11 〉	통과 (0.21ms, 30.2MB)
테스트 12 〉	통과 (0.90ms, 30.4MB)
테스트 13 〉	통과 (0.79ms, 30.3MB)
테스트 14 〉	통과 (0.74ms, 30.1MB)
테스트 15 〉	통과 (0.59ms, 30.1MB)
테스트 16 〉	통과 (3.58ms, 30.7MB)
테스트 17 〉	통과 (3.36ms, 30.6MB)
테스트 18 〉	통과 (3.01ms, 30.5MB)
테스트 19 〉	통과 (2.21ms, 30.2MB)
테스트 20 〉	통과 (1.83ms, 30MB)

2) Set

 

문제를 풀고나니, 실질적으로 Map 안에 있는 값들을 쓰지 않는데 굳이 Hash를 할 필요가 있었을까? 라는 의문이 들었다.

 

일단 해시를 통해, 정리하면 O(n) 만큼의 시간이 들기 때문이다. 그리하여, 어떻게 하면 더 최적화 할 수 있을까?에 대한 고민 끝에 중복 없이 폰켓몬을 정리하면 그것이 폰켓몬의 종류가 된다는 사실을 깨닫게 되어 Set 함수를 이용해서 이를 정리하였고 더 빠른 속도로 처리 할 수 있게 되었다.

 

// set 함수를 이용한 문제풀이
function solution(nums) {
  let maxCount = parseInt(nums.length / 2);
  const variety = [...new Set(nums)];

  return variety.length <= maxCount ? variety.length : maxCount;
}

테스트 1 〉	통과 (0.05ms, 30MB)
테스트 2 〉	통과 (0.05ms, 30MB)
테스트 3 〉	통과 (0.04ms, 29.9MB)
테스트 4 〉	통과 (0.05ms, 30MB)
테스트 5 〉	통과 (0.05ms, 29.8MB)
테스트 6 〉	통과 (0.06ms, 30MB)
테스트 7 〉	통과 (0.05ms, 30.1MB)
테스트 8 〉	통과 (0.05ms, 29.9MB)
테스트 9 〉	통과 (0.05ms, 30.1MB)
테스트 10 〉	통과 (0.06ms, 30.2MB)
테스트 11 〉	통과 (0.06ms, 30MB)
테스트 12 〉	통과 (0.11ms, 30.1MB)
테스트 13 〉	통과 (0.11ms, 29.9MB)
테스트 14 〉	통과 (0.10ms, 29.9MB)
테스트 15 〉	통과 (0.08ms, 29.8MB)
테스트 16 〉	통과 (0.67ms, 30.1MB)
테스트 17 〉	통과 (0.71ms, 30.2MB)
테스트 18 〉	통과 (0.34ms, 30MB)
테스트 19 〉	통과 (0.45ms, 30.1MB)
테스트 20 〉	통과 (0.25ms, 29.9MB)