코테 스터디 31일차 TIL + 오늘의 학습 키워드 선형탐색

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

정렬된 겹치지 않는 간격으로 새로운 간격을 삽입하고 병합한다. 이때 사용되는 알고리즘은 선형탐색이다.

 

function insert(intervals, newInterval):
   result =[]
   i=0
   n=intervals의 길이
   
   #1. newInterval 보다 완전히 앞에있는 간격들을 결과에 추가
    while i<n 그리고 intervals[i][1]< newInterval[0]:
        result에 intervals[i] 추가
        i 증가
        
   #2. newInterval과 겹치는 간격들을 병합
     while i<n 그리고 intervals[i][0] < = newInterval[1]:
        newInterval[0] = min(newInterval[0], intervals[i][0])
        newInterval[1] =max(newInterval[1],intervals[i][1])
        i증가
        
   #3 병합된 newInterval을 결과에 추가
   result에 newInterval 추가
   
   #4 newInterval 보다 완전히 뒤에 있는 간격들을 결과에 추가
   while i<n:
      result에 intervals[i] 추가
      i 증가
      
      return result

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

interval을 (x,y) 정도의 개념으로 생각하고 문제 풀었음

범위가 겹쳐지면 merge 하는거여서 newInterval 보다 완전 작은 범위 

겹쳐지는 범위-> merge

훨씬 큰 범위로 나눠야하는데 완전 작은 범위가 왜 남는지 이해를 못했음

  - 어떻게 해결했는지

[i,j] 라도 간격이라는 사실을 문제를 다시 읽고 이해했고

overlapping 되는 부분은 삭제했다.
  - 무엇을 새롭게 알았는지
  - 내일 학습할 것은 무엇인지

필수 해시태그: #코딩테스트준비 #개발자취업  #TIL