https://school.programmers.co.kr/learn/courses/30/lessons/1845
처음에는 해시 문제라고 생각해서 해시맵을 사용해서 풀려고 했다.
직접 코드를 짜보기보다는, 그림과 글로 문제 해결 방식을 생각해보고 감이 잡히면 코드를 만들어보려고 했다.
이것 조차도 안돼서 일단 해시맵을 구현부터 해봤지만 1시간 이상이 지나도 문제 해결에 대한 실마리조차 얻지 못했고 검색을 통해 해시셋이라는 것이 있다는 것을 알게 됐다.
옛날에 New Years test였나 거기에서 문제를 해결할 때 다른 사람들이 셋이라는 개념을 사용해 중복된 값을 제거해 문제를 돌리는 시간을 획기적으로 줄였다! 하는 답변을 많이 봤었는데 이 문제는 셋을 쓰는 개념인가보다
기존에 생각한 접근 방식
해시를 사용해야 한다고 하길래 해시를 저장하고 빈도수를 세는 데 사용하려고 했다
1. 숫자 n/2개를 배열에서 뽑는다
2. n/2개의 숫자 중 중복되지 않는 숫자의 개수를 구한다
3. 2에서 구한 중복되지 않는 숫자의 개수를 저장하는데 해시를 사용한다.
4. 저장해놓은 값에서 가장 큰 수를 구한다.
다만 이 방식의 치명적인 단점은, 3번의 개수의 저장은 아무리 생각해도 배열에 저장하는거지, 해시를 사용하는 방식은 아니었다.
그래서 다시 해시가 뭔지 찾아봤다.
해시란?
- 키와 값이 1대 1 구조로 저장된 자료구조로 키를 통해 값을 도출할 수 있다.
- 해시함수를 이용해 키 값을 해시코드로 변환-> 해시 코드를 인덱스로 값을 저장.
- 자바에서는 이 해시 코드를 힙 영역 인스턴스의 참조값이라고 볼 수 있다.
- 키 값은 중복될 수 없다
https://llshl.tistory.com/17
https://velog.io/@kkw9312/javaHash
다시 얘기 하다 해시 맵과 맵과 차이점, 해시함수를 사용한다는 얘기 말고 구체적으로 또 어떤 점이 있을까 가설을 세워봤다.
- 해시맵은 해시함수를 쓰는데 위에서 말했듯 해시함수를 거쳐 구한 해시코드에 값을 저장한다. 따라서 키값이 그대로 인덱스이기 때문에 원하는 키에 맵핑된 값을 찾기 위해 for 문을 돌며 값을 찾아야 하는 맵보다 빠른 속도로 찾을 수 있다.
- 애초에 해시는 메모리를 관리하기 위해 나온 개념으로 해시코드가 가리키는 주소에서 충돌이 일어나면 다른 곳에 데이터를 저장할 수 있다.
다시 생각해봤다.
[2 2 4 5 6 3]이라는 포켓몬이 있다고 가정한다.
1. for문을 돌며 숫자 세 개를 뽑아서 배열에 담아둔다(여기서 3중 중첩 for문이 생성될 수 밖에 없음) [[224], [225], [226], [223], [245], [246]]
2. 외부 배열의 인덱스를 키로, 내부 배열의 포켓몬의 개수를 해시값으로 설정한다.
3. 해시값을 for문을 돌며 가장 큰 값을 확인한다(해시 값이 n/2에 해당하는 경우 함수 종료)
for 문을 돌며 포켓몬을 n/2만큼 뽑는 과정이 너무 비효율적이라 포기
해시셋이란?
- 객체 저장 전 저장할 객체의 해시 코드를 해시 함수를 통해 구한다.
- 이미 존재하는 해시코드라면 equals를 통해 객체를 비교해 true이면 중복값임으로 저장을 하지 않고, false인 경우 저장을 한다.
https://crazykim2.tistory.com/474
해답 검색
- 주어진 포켓몬 번호가 담긴 숫자 배열을 set을 통해 중복을 걸러 저장한다
- 해시셋의 사이즈가 골라야 하는 숫자의 개수(n/2)보다 작으면 해시셋의 사이즈가 주어진 배열에서 고를 수 있는 최대 포켓몬 수로 답이 된다.
- 해시셋의 사이즈가 골라야 하는 숫자의 개수(n/2)보다 크면 최대로 고를 수 있는 포켓몬 수는 골라야 하는 숫자 그대로이다.
https://devhan.tistory.com/205
class Solution {
public int solution(int[] nums) {
int answer = 0;
int choosingNum = nums.length / 2;
HashSet<Integer> hashSet = new HashSet<Integer>();
for (int i: nums){
hashSet.add(i);
}
if(hashSet.size() >= choosingNum)
answer = choosingNum;
else
answer = hashSet.size();
return answer;
}
}내 힘으로 해결하지 못해 슬프다.. 흑흑
문제의 핵심은 중복되지 않는 값을 구해서 그 숫자를 세는 것!
