NeetCode - Arrays & Hashing

https://neetcode.io/roadmap

NeetCode

---

□ Duplicate Integer

https://neetcode.io/problems/duplicate-integer

NeetCode

 

---

□ Is Anagram

https://neetcode.io/problems/is-anagram

NeetCode

 

---

□ Two Sum

https://neetcode.io/problems/two-integer-sum

NeetCode

 

 

- HashMap 사용

1. HashMap 초기화

HashMap<Integer, Integer> prevMap = new HashMap<>();
→ prevMap은 배열의 값과 해당 인덱스를 저장하는 HashMap입니다.

2. 배열 순회

for (int i = 0; i < nums.length; i++) {
    int num = nums[i];
    int diff = target - num;
    
    if (prevMap.containsKey(diff)) {
        return new int[] { prevMap.get(diff), i };
    }
    prevMap.put(num, i);
}

• 배열의 각 요소를 순회하면서 현재 요소 num과 target의 차이 diff를 계산합니다.
• diff가 prevMap에 있는지 확인합니다. 만약 있다면, prevMap.get(diff)는 diff의 인덱스를 반환하고, 현재 인덱스 i와 함께 반환합니다.
• prevMap에 현재 요소 num과 그 인덱스 i를 저장합니다.

※ 해당 HashMap은 배열 nums의 요소를 key값으로, index를 value로하여 저장하는 방식이다.

---

□ Anagram Groups

https://neetcode.io/problems/anagram-groups

NeetCode

 

- 코드 리뷰

1. HashMap 생성, key=정렬된 문자열, value=원래 문자열들의 리스트
   

   

2. 반복문을 통해 key값이 될 정렬된 문자열 만들기
   

   

3. 해당 key 값이 이미 존재하는 확인 후 key,value 저장
   

   

---

□ Top K Element in List(실패)

https://neetcode.io/problems/top-k-elements-in-list

NeetCode

 

- 코드 리뷰

1. 빈도 계산을 위한 HashMap 생성
   

   

2. 우선순위 큐 생성 및 빈도에 따라 정렬
   

   

3. HashMap의 엔트리를 우선순위 큐에 삽입
   

   

4. 결과 배열 생성 및 우선순위 큐에서 요소 추출
   

   

※ PriortyQueue

•  PriorityQueue<Map.Entry<Integer, Integer>> pq = new PriorityQueue<>(); → 선언
• Map.Entry<Integer, Integer> entry : map.entrySet(); → map의 각 엔트리를 반복
• offer : 요소를 추가 이때 pq선언 시 정해둔 기준으로 비교하여 삽입됨
• poll : 맨 앞 요소를 제거하고 반환

---

□ Products of Array Discluding Self

 

https://neetcode.io/problems/products-of-array-discluding-self

NeetCode

- 코드 리뷰

1. input배열에 0의 갯수 세기
2. 0을 제외한 나머지들의 곱을 변수 k에 담기
3. 0의 갯수에 따라 answer배열에 대입

※ 해당 요소를 제외한 곱을 구하는 코드

 

- 코드 리뷰(nums.length = 3로 가정)

1. arr[0]에 초기값 left = 1을 대입
2. left 값에 nums[0]값을 곱해주고 반복문 진행
3. arr[1]에 left*nums[0]의 값을 대입하고 다시 left값에 nums[1]을 곱해줌
4. arr[2]에 left* nums[0]* nums[1] 값을 대입하고 ....
5. 왼쪽의 모든 요소가 곱해진 배열 arr을 생성
6. arr[2](left* nums[0]* nums[1])에 rigth값을 곱함
7. right 값에 nums[2] 값을 곱하여 갱신
8. arr[1]( left* nums[0])에 갱신된 right를 곱해줌

이런식으로 자신을 제외한 좌우의 곱을 구하는 코드가 완성됨

---

□ Vaild Sudoku

https://neetcode.io/problems/valid-sudoku

NeetCode

---

□ Longest Consecutive Sequence

https://neetcode.io/problems/longest-consecutive-sequence

 

- 코드 리뷰

1. 입력값이 빈 배열인 경우 0을 ruturn
2. 중복값을 제거한 Set 생성
3. 순서를 위해 Set의 값을 List 대입
4. Collectios.sort를 이용해 정렬
5. 반복문을 통해 연속된 수의 최대 길이 반환

※ 해설 풀이

1. HashSet 정의 nums 요소 추가
2. 길이 변수 longest 선언
3. numSet의 요소 n-1이 numSet의 요소에 포함되는지 확인하고 포함되면
4. length를 선언하고
5. numSet이 n+1을 보유하고있는 동안 계속 length++를 반복한다.