코딩 테스트/프로그래머스

프로그래머스 - 폰켓몬 문제 (자바)

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

 

코딩테스트 연습 - 폰켓몬

당신은 폰켓몬을 잡기 위한 오랜 여행 끝에, 홍 박사님의 연구실에 도착했습니다. 홍 박사님은 당신에게 자신의 연구실에 있는 총 N 마리의 폰켓몬 중에서 N/2마리를 가져가도 좋다고 했습니다.

programmers.co.kr

간단한 문제로 포켄몬 종류 번호크기만큼의 배열을 만들어서 해결하거나 set을 이용할 수 있습니다.

둘다 nums의 길이만큼만 돌면되지만

배열은 고정길이로 일정 수준의 메모리를 사용해야합니다.

Set은 내부 로직에서 중복여부를 체크하고 추가하는 연산이 진행됩니다.

1. 배열

문제 중

폰켓몬의 종류 번호는 1 이상 200,000 이하의 자연수로 나타냅니다.

을 따라서 200001 길의 의 배열을 만들어서 nums를 순회하면서

1마리도 없는 경우 카운트를 진행하게 하고 

마지막에 answer가 N/2 보타 크면 N/2로 초기화하였습니다.  

class Solution {
    public int solution(int[] nums) {
        int[] counts = new int[200001];
        int answer = 0;
        for(int i = 0; i < nums.length; i++) {
            if(counts[nums[i]] == 0) {
                answer++;
            }
            counts[nums[i]]++;
        }
        if(answer > nums.length / 2) {
            answer = nums.length / 2;
        }
        return answer;
    }
}

 

2. Set

Set을 만들고 nums을 순회하면서 포켓몬의 번호를 추가한 뒤 set의 길이로 값을 구하는 방법

import java.util.*;
class Solution {
    public int solution(int[] nums) {
        HashSet<Integer> set = new HashSet<>();
        for(int i = 0; i < nums.length; i++) {
            set.add(nums[i]);
        }
        
        int answer = set.size();
        if(answer > nums.length / 2) {
            answer = nums.length / 2;
        }
        
        return answer;
    }
}