프로그래머스 폰켓몬

-10월 첫째주 공부 내용을 옮겨 씀-

 

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

프로그래머스

-문제

nums배열에 가질수 있는 폰켓몬들이 나옴

nums요소수/2 의 폰켓몬만 가지는것이 가능

최대한 많은 종류의 폰켓몬을 가지고싶다. 그 종류 수를 return

---

-아이디어

nums배열의 절반이 몇인지 구한다.

nums안의 폰켓몬 종류 수를 구한다.

만약 가질수있는수>폰켓몬 종류 수 라면 지금 있는 폰켓몬 종류 수가 최대 가질수 있는 종류의 수

가질수있는수≤폰켓몬 종류 수 라면 가질수있는수가 최대 종류 수

---

-첫번째 코드

import java.util.*;
class Solution {
    public int solution(int[] nums) {
        int answer = 0;//가질수 있는 종류의 최댓값
        int num_len_half=nums.length/2;//가질수 있는 폰켓몬 수
        int type_number=0;//nums안의 폰켓몬 종류의 수
        HashMap<Integer,Integer> ponketmons=new HashMap<Integer,Integer>();
        //어떤 폰켓몬이 몇마리 있는지 해시맵으로 관리한다.
        for(int i=0;i<nums.length;i++){
            if(ponketmons.containsKey(nums[i])){//만약 해시맵에 있는 폰켓몬이라면
                int ponketmon_num=ponketmons.get(nums[i]);
                ponketmons.put(nums[i],ponketmon_num+1);//val값을 1증가
            }else{//해시맵에 없는 폰켓몬이면
                ponketmons.put(nums[i],1);//폰켓몬 추가
                type_number++;//폰켓몬 종류수 증가
            }
            
        }
        if(type_number>=num_len_half){//만약 종류 수가 가질수있는 수보다 크거나 같으면
            answer=num_len_half;//가질수있는 최대 종류 수는 가질수있는 수만큼임
        }else{//만약 종류 수가 가질수있는 수보다 작으면
            answer=type_number;//가질수있는 최대 종류 수는 종류의 수
        }
        return answer;
    }
}

---

-두번째 풀이: 다른사람 풀이를 참고

결론적으로 필요한것은 nums에 폰켓몬 종류의 수

그 종류의 폰켓몬이 몇마리 있는지는 알필요 없음

어차피 해당 종류의 폰켓몬이 있는지 여부만 알면되니 HashMap을 쓸 필요없음

import java.util.*;
class Solution {
    public int solution(int[] nums) {
        int answer = 0;
        int num_len_half=nums.length/2;
        int type_number=0;
        ArrayList<Integer> ponketmons=new ArrayList<Integer>();
        
        for(int i=0;i<nums.length;i++){
            if(!ponketmons.contains(nums[i])){
                ponketmons.add(nums[i]);
                type_number++;
            }
        }
        if(type_number>=num_len_half){
            answer=num_len_half;
        }else{
            answer=type_number;
        }
        return answer;
    }
}

→ArrayList의 사용으로 소모 시간 증가함

hashmap, arraylist차이: https://naivedevelop.tistory.com/29

ArrayList와 HashMap의 차이점 (Java Collection)

-Map 계열

---AbstractMap, Attributes, HashMap, identiyHashMap, RenderingHints, TreeMap, WeakHashMap

---key vlaue쌍으로 저장

---수집의 순서없음, 동일한 key존재 불가

---특정 데이터에 접근이 빨라 검색시 유리

---HashMap은 데이터 입출력이 동기화되지 않고(?) 처리속도 빠름

---HashTable은 모든 입출력이 동기화, 처리속도 다소 떨어짐

 

-List계열

---AbstractMap, ArrayList, LinkedList, Vector

---수집 순서 존재, 동일 데이터 중복 가능

---순차적으로 대량의 데이터를 엑세스하거나 입력할때 유리

---데이터 검색을 위해(그 데이터가 있는지확인 등)리스트의 처음부터 끝까지 살펴보거나 해당 데이터의 인덱스를 알고있어야 된다, 만약 인덱스를 알고있다면 HashMap보다 빠르다

 

-Set계열

---AbstractSet, HashSet, LinkedHashSet, TreeSet

---중복불가

---

-세번째 코드: HashMap 쓰되 단순히 종류만

import java.util.*;
class Solution {
    public int solution(int[] nums) {
        int answer = 0;
        int num_len_half=nums.length/2;
        int type_number=0;
        HashMap<Integer,Integer> ponketmons=new HashMap<Integer,Integer>();
        
        for(int i=0;i<nums.length;i++){
            if(!ponketmons.containsKey(nums[i])){
                ponketmons.put(nums[i],1);
                type_number++;
            }
        }
        if(type_number>=num_len_half){
            answer=num_len_half;
        }else{
            answer=type_number;
        }
        return answer;
    }
}

---

-네번째 코드: 다른사람 코드 참고, HashSet을 사용

HashSet은 중복을 허용하지 않음

-참고: https://hbase.tistory.com/129

[Java] HashSet 사용법 및 예제

HashSet은 add로 값이 추가되며 이미 있는값을 add하면 추가되지 않고 false를 반환

없는값을 새롭게 추가하면 추가가 되고 true반환

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

→속도는 HashMap이 더 빠름,, 용량도 그렇게 차이나는것 같진 않다 뭐가 더 좋을진.. 모르겠음