리트코드 153 풀이 노트

미들을 구할 필요가 있는가? 해야함. 왜냐면 미들 하나 구해서 이걸 왼쪽, 오른쪽과의 크기 비교 한 뒤에 l, r 인덱스 값 조정에 이걸 써야 하기 때문임

최소값은, 배열 값들이 계속 증가하다가 확 바뀌는 지점이다. 음..

맨 처음 if를 통과하지 못한 이상 이미 앞쪽 애들이 뒤쪽보다 큰 건 확실하잖아? 그래서 미들을 구해보는거지

얘가 증가구간에 있는 앤지 감소 구간에 있는 앤지 봐야 하잖아

 

난 미들을 계속 ..l, r 그 자체가 아니고 오른쪽 혹은 왼쪽 값에 대해 얼마를 더했거나 뺀.... 값으로 설정해보기로 했다 일단.

이 아이디어가 이상하다 생각이 들기도 하지만,..

 

궁극적 최소값이 어떻게 구해지는가? 에 대한 아이디어가... 흠...

글고  m-nums[m] 이런 비슷한 것들 하는 과정에서 +1, -1 더 필요할 수도 있음. 인덱스의 정확성 때문에

 

1. 미들&왼쪽 비교

l < m: l=최소값일수도 있고, m+1 부터 최소값 있을 수 있음. 왜냐면 l,m 다 증가 구간에 있단 뜻인데, 최소값은 감소구간 맨왼쪽끝에 있기 떄문이고, at least m+1 부터 최소값 가능성 있기 때문에 l=m+1, r=m+?? 인데, 이 '??'는 최대값을 모르는 이상 구할 수 없는 부분이라서 r은 그대로 두는. 즉 l만 바꿔 준다.

l > m: l~m 사이에 최소값 있을 수 있음. m부터 시작해 왼쪽 방향으로 내려가는 쪽에 말이다. l = m-nums[m],   r=m-1. 이것도 m = 최소값 가능성 있으니 업뎃

 

2. 미들 & 오른쪽:

m < r: m=최소값일수도 있고, 더 작은 값이 m-1부터 있을 수 있고 1-2의 경우와 동일하다!

m > r: r=최소값일수도 있고, r부터 왼쪽 방향으로 내려가는 구간에 최소값 있을 수 있다.  l = r-nums[r],   (r=r-1 은 할 필요가 있는지 모르겠음).

 

 

근데 이 1-1, 2-2번을 병행..하는거야 두 가지 가능성을 갖고? 아님 둘중 하나만 택하는 거야..?

 

그리고 l<=0, r>=len-1 되는 경우에 대한 에지 케이스 처리 필요

대체 최소값 검사를 언제언제 해야하지? m+1, m-1 인덱스 처리하면 얘네가 최소값 그 자체일 수도 있는 건데... 이에 대한 검사는 없잖아 그럼 어떻게 해야 함? 그래서 그냥 l,r이 m으로 돼야 하는 건 아냐? 그럼 굳이 매번 최소값 가능성이 있다면서 업데이트할 필요가 없어지는 건 아닐까?

 

 

 

자 아이디어 작성은 끝났음. 나머지는 힌트를 보거나, 영상 풀이 보면서 아이디어 한 번 확인한 다음에 구현해보는 걸로 하자.

---

역시나 더 좋은 아이디어가 있었다. ㅠㅠ

미들을 먼저 찾아(구해) 본다. 그 값을 l, r값과 비교했을 때, m 이 l(혹은 r)보다 큰, 작은 경우 m+1 즉 오른쪽 사이드 어딘가로 l 옮기고 다시 m을 구한다. 이쪽에 최소값이 있을 것이므로. 그 반대의 경우는 그 반대로 진행한다.