99클럽 코테 스터디 17일차 TIL + 오늘의 학습 키워드 이진 탐색

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

 

접근 방법

arr1의 각 요소를 한바퀴 돈다

arr[i]에 대해서 arr2의 모든 요소랑 비교한다

arr2의 어떤 요소와도 차이가 d이하가 아닌경우, 카운터를 증가시킨다.

 

수도코드

function findDistanceValue(arr1, arr2, d):
    count = 0
    
    for each element x in arr1:
        flag = true
        
        for each element y in arr2:
            if |x - y| <= d:
                flag = false
                break
        
        if flag is true:
            count++
    
    return count

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

예제에 나와있는 arr1[i]- arr2[j] >d 보다 큰 경우는 어떻게 처리해야할지 갈팡질팡함

처리를 제대로 못했음 단하나의 요소라도 d이하면 카운트 하지 않는다는 말을 정반대로 해석해서

반대로 풀고 있었음
  - 어떻게 해결했는지

arr1의 각 요소를 순회하되

boolean valid= true로 처리하고

절대값차이를 arr1[i]- arr2[j]<=d로 비교하여

값이 d 이하가 나오면 valid =false로 취급하여 카운트에서 제외했음 

  - 무엇을 새롭게 알았는지

현재 코드는 for문이 중첩되어있어서 시간 복잡도가 O(n*m)이나 작은 수를 가정하고 있어서 그냥 

이대로 만들었다. 만약에 숫자 범위가 큰경우에는 for문을 뜯어내서 각각으로 만들어야한다.
  - 내일 학습할 것은 무엇인지