99클럽 코테 스터디 16일차 TIL + 오늘의 학습 키워드 이분 검색

- 오늘의 학습 키워드 : 이분 검색
- 공부한 내용 본인의 언어로 정리하기

①두 배열중 하나를 골라서 정렬하고 정렬된 배열에서 이분 탐색을 수행함

 

정렬+ 이분 탐색 정렬법 O(n log m) 의 시간복잡도

 

---

다른 방법으로 풀어보기

②해시셋 접근법

첫번째 배열의 모든 원소를 해시셋에 저장(중복은 안되겠다)

두번째 배열을 for문으로 순회하면서 해시셋에 있는지 확인하고 contains 있으면 결과에 추가

중복 방지를 위해 이미 결과에 추가한 원소는 해시셋에서 제거

 

수도코드

function intersection(nums1, nums2)
	set= new HashSet()
    result = new ArrayList();
    
    for( int num : nums1){
      set.add(num);
      
      for( int num: nums2) 
        if(set contains num)
        result.add(num)
        remove.set(num)
        
        return result as array

 

---

다른 풀이법 투포인터

③ 투포인터 접근법

두 배열을 정렬

투 포인터를 사용하여 두 배열을 동시에 순회하고 교집합을 찾음

 

수도코드

fuction intersection(nums1, nums2)
  sort nums1
  sort nums2
  result = new ArrayList()
  
  i=0; j=0;
  while(i<nums1.length and j<nums2.length){
    if( i >0 && nums1[i] ==nums1[i-1])
      i++;
      continue;
      
      if(nums1[i] <nums2[j])
        i++;
        else if( nums1[i] > numx2[j])
          { j++;}
          else {
             result.add(nums1[i])
             i++
             j++
          }
          
          return result as array

 

---

- 오늘의 회고
  - 어떤 문제가 있었고, 나는 어떤 시도를 했는지

결과값이 안나왔다. 예시에 나온 정답은{2} 였으나 null만 반환되었음

어디에서 null 이 나오는지 코드를 재확인했음

이분 탐색에서 원소를 찾고 resultSet에 추가해야하는데 continue를 사용해서 추가 안되고 건너뛰고 있었음
  - 어떻게 해결했는지

resultSet.add(num)을 추가하여서 원소를 찾으면 결과를 집합에 추가할수 있었음

  - 무엇을 새롭게 알았는지

이분 탐색 접근법 이외에도 해시셋 접근법, 정렬+ 투포인터 접근법으로 푸는 방법도 있다고 해서 알고리즘 풀이법이 다양하게 있다는 것을 새로이 알게 되었다.
  - 내일 학습할 것은 무엇인지