오늘의 학습 키워드
- 폰켓몬
공부한 내용 본인의 언어로 정리하기
import java.util.*;
class Solution {
public int solution(int[] nums) {
Arrays.sort(nums);
List<Integer> overlapRemoval = new ArrayList<>();
int halfsize = nums.length / 2;
overlapRemoval.add(nums[0]);
for(int i=1; i < nums.length; i++){
if(nums[i] != nums[i-1]){
overlapRemoval.add(nums[i]);
}
}
if(overlapRemoval.size() > halfsize){
return halfsize;
} else {
return overlapRemoval.size();
}
}
}
오늘의 회고
오늘은 문제가 길어서 한번에 이해하기 힘들었다. 하지만 결국의 요구하는 값은 N마리의 포켓몬 중 최대한 서로 다른 종류의 폰켓몬을 포함해서 N/2마리를 선택하여 반환하라는 소리였다.
만약 서로 다른 종류의 폰켓몬이 N/2마리를 넘어선다면 N/2마리만 가져갈 수 있고, 만약의 N/2 마릿수보다 작다면 중복되지 않은 폰켓몬의 수만큼만 가져간다고 생각하면 되겠다.
그래서 오늘도 어제와 마찬가지로 중복된 개체를 제거해야 했으므로 비교를 하기 편하게 오름차순으로 정렬해준 후, 비교 후 추가해줄 중복제거 리스트를 새로 만들어주었다.
Arrays.sort(nums); //배열 오름차순 정렬 [1,2,3,3,4]
List<Integer> overlapRemoval = new ArrayList<>(); //중복제거 리스트가져갈 수 있는 최대 수량인 N/2마리도 만들어주었다.
int halfsize = nums.length / 2; //가져갈수있는 최대 포켓몬의 수그리고 반복문에서 int i = 0이 되면 마지막 항목은 비교를 할 수 없으므로 int i = 1로 시작하고 비교가 필요없는 index 0번의 개체는 시작부터 중복 제거 리스트에 추가해주었고 배열의 이전 항목과 비교해 같지 않다면 리스트에 추가해 주었다.
overlapRemoval.add(nums[0]); //중복제거된 리스트에 첫번째 요소 추가
for(int i=1; i < nums.length; i++){ //배열 중복 제거
if(nums[i] != nums[i-1]){
overlapRemoval.add(nums[i]);
}
}중복제거된 리스트도 나왔고 가져갈 수 있는 최대의 갯수도 구해져있으므로 비교해서 중복제거리스트의 크키가 가져갈 수 있는 최대의 갯수보다 큰 경우 최대값을 반환하고 아니라면 중복제거리스트의 크기를 반환해주면 된다.
//비교 후 알맞은 값 반환
if(overlapRemoval.size() > halfsize){
return halfsize;
} else {
return overlapRemoval.size();
}제한사항에 N의 길이가 항상 짝수로 주어진다는 항목이 있어서 최대 갯수의 값을 구하기 매우 쉬웠던 것 같다.
AI 코드리뷰
코드 구조와 로직:
전체적인 알고리즘이 잘 구현되어 있습니다.
배열 정렬, 중복 제거, 최대 선택 가능 개수 계산 등의 단계가 명확합니다.
변수명:
halfsize는 halfSize로 변경하면 가독성이 더 좋아집니다 (camelCase 규칙).
overlapRemoval은 uniquePokemon이나 distinctPokemon으로 변경하면 목적이 더 명확해집니다.
주석:
주석이 코드의 각 부분을 잘 설명하고 있습니다.
효율성:
현재 구현은 O(n log n) 시간 복잡도를 가집니다 (정렬 때문에).
만약 입력 배열의 크기가 매우 크다면, HashSet을 사용하여 O(n) 시간 복잡도로 개선할 수 있습니다.
시간 복잡도 개선 코드
import java.util.*;
class Solution {
public int solution(int[] nums) {
int maxSelection = nums.length / 2; // 선택 가능한 최대 포켓몬 수
Set<Integer> uniquePokemon = new HashSet<>();
for (int num : nums) {
uniquePokemon.add(num);
if (uniquePokemon.size() == maxSelection) {
break; // 최대 선택 가능 수에 도달하면 중단
}
}
return Math.min(uniquePokemon.size(), maxSelection);
}
}이 개선된 버전의 장점:
HashSet을 사용하여 중복 제거와 동시에 고유한 포켓몬 수를 계산합니다.
정렬이 필요 없어 시간 복잡도가 O(n)으로 개선됩니다.
최대 선택 가능 수에 도달하면 루프를 중단하여 불필요한 반복을 피합니다.
Math.min()을 사용하여 조건문을 간소화했습니다.
이 개선된 버전은 원래 코드의 로직을 유지하면서도 더 효율적이고 간결합니다. 하지만 원래 코드도 충분히 잘 작동하며, 특히 입력 크기가 작을 때는 큰 차이가 없을 것입니다.
내일 공부할 것 :
오늘도 개선된 코드에 Hash가 등장을 했다. Hash 자료구조 비교관련 코드를 굉장히 유용하고 잘 사용하는 것으로 보인다.
Hash 자료구조비교에는 다양한 것들이 있다.
HashMap:
1. 가장 많이 사용되는 Map 구현체입니다.
2. 키-값 쌍을 저장하며, 키를 통해 빠르게 값을 검색할 수 있습니다.
3. 동기화되지 않아 멀티스레드 환경에서는 주의가 필요합니다.
HashSet
1. 중복을 허용하지 않는 집합을 구현합니다.
2. 내부적으로 HashMap을 사용하여 구현됩니다.
LinkedHashMap
1. HashMap과 유사하지만 삽입 순서를 유지합니다.
2. 순서가 중요한 경우에 사용됩니다.
LinkedHashSet
1. HashSet과 유사하지만 삽입 순서를 유지합니다.
TreeMap
1. 키를 기준으로 정렬된 Map입니다.
2. 레드-블랙 트리로 구현되어 있습니다.
TreeSet
1. 정렬된 Set입니다.
2. 내부적으로 TreeMap을 사용하여 구현됩니다.
Hashtable
1. HashMap의 이전 버전으로, 동기화를 지원합니다.
2. 현재는 ConcurrentHashMap을 사용하는 것이 권장됩니다.
ConcurrentHashMap
1. 동시성을 지원하는 HashMap입니다.
2. 멀티스레드 환경에서 안전하게 사용할 수 있습니다.
최근에 많이 보였던 HashMap과 HashSet에 대해서 공부를 해야할 것 같다.
오늘 문제는 권장시간인 30분을 넘긴것에 대해 많은 아쉬움을 느꼈다. 더욱 분발하여 시간을 단축하도록 노력하여야 한다.
문제
https://school.programmers.co.kr/learn/courses/30/lessons/1845
