TIL

---

오늘 한 일

• 휴식
• leetcode
  • Find Peak Element. (medium)

---

문제 풀이

Find Peak Element. (medium)

수가 랜덤하게 분포된 배열을 입력받고 해당 배열에서 가장 값이 큰 요소의 index를 돌려주는 문제. 요구사항으로 O(log n) 복잡도 풀이하라는 것이있다.

복잡도 요구사항으로 생각했을때 먼저 생각이 드는 방식은 반분 하면서 줄여가는 방식이다. 하지만 해당 배열은 정렬 되지 않은 배열이기에 영역을 나누는 방식에 대해 적용할 방법을 찾지 못하였다. 해서 단순하게 찾는 방식으로 풀이를 진행하였고, 다른 유저들이 풀이한 방식을 참조하여 공부 하기로 하였다.

풀이 방식에 대해 직관적인 이해가 되지 않았다. 좌우 경계를 두고 중간값을 바탕으로 영역을 구분하는 방식은 다른 곳에서 경험한 것과 유사하였으나, 정의된 중간값을 바탕으로 영역을 재구성하는 부분이 이해하기 어렵다. 방식은 다음과 같다.

1. 좌우 경계의 (index 값) 중간값(index 값) 을 구하고, 해당 중간값의 배열 값과 다음 배열값을 비교하여 현재 값이 크다면 우측 경계 값을 현재 값으로 변경한다.

2. 크지 않다면 좌측 경계 값을 1 더한다.

3. 이를 좌측 경계값이 우측 경계값보다 작을때 까지만 반복 한다.

4. 반복이 종료된후 좌측 경계값을 결과로 돌려준다.

꾸준히 고민하며 이해하도록 노력 해봐야겠다.

---

오늘은...

휴식