우규이인우윀
Eager To Learn 🌌
우규이인우윀
전체 방문자
였늘
μ–΄μ œ

λΈ”λ‘œκ·Έ 메뉴

  • 🏑 ν™ˆ
  • πŸš€ κΉƒν—ˆλΈŒ
  • β›… νƒœκ·Έ ν΄λΌμš°λ“œ
  • λΆ„λ₯˜ 전체보기 (217)
    • πŸ‘¨πŸ»β€πŸ’» PS (170)
      • JAVA (82)
      • MYSQL (1)
      • Docker (2)
      • PYTHON (24)
      • LeetCode 150 (39)
      • Algorithm 기법 (1)
      • 바킹독 (21)
    • λΈ”λ‘œκ·Έ 이사 (0)
    • Error (1)
    • CS (15)
      • DataBase (2)
      • OS (7)
      • Network (1)
      • Spring (1)
      • 자료ꡬ쑰 (3)
      • Java (1)
    • Learned (7)
      • Spring (7)
    • κ°œλ°œμ„œμ  (15)
      • 가상 λ©΄μ ‘ μ‚¬λ‘€λ‘œ λ°°μš°λŠ” λŒ€κ·œλͺ¨ μ‹œμŠ€ν…œ 섀계 기초 (1)
      • 였브젝트 - 쑰영호 (7)
      • μΉœμ ˆν•œ SQL νŠœλ‹ (7)
    • 회고 (2)
hELLO Β· Designed By μ •μƒμš°.
우규이인우윀
πŸ‘¨πŸ»β€πŸ’» PS/LeetCode 150

[Java] 162. Find Peak Element

πŸ‘¨πŸ»β€πŸ’» PS/LeetCode 150

[Java] 162. Find Peak Element

2023. 9. 3. 17:59

문제 νŒŒμ•…

μ£Όλ³€ μ›μ†Œλ“€λ³΄λ‹€ 큰 μ›μ†Œλ₯Ό peak element라고 ν•œλ‹€.

 

κ·ΈλŸ¬ν•œ μ›μ†Œκ°€ μ—¬λŸ¬κ°œλΌλ©΄ 아무 μ›μ†Œμ˜ 인덱슀λ₯Ό λ°˜ν™˜ν•˜λ©΄ λœλ‹€.

 

μ‹œκ°„ λ³΅μž‘λ„κ°€ O(logN) 이 λ˜λ„λ‘ κ΅¬ν˜„ν•΄μ•Όν•œλ‹€.


풀이

1️⃣ 이뢄 탐색을 μ΄μš©ν•œ 풀이

πŸ’‘ λ– μ˜€λ₯Έ Idea

μ‹œκ°„λ³΅μž‘λ„λ₯Ό 톡해 이뢄 탐색을 μ΄μš©ν•΄μ•Όν•¨μ„ μ•Œ 수 μžˆμ—ˆλ‹€.

보톡 이뢄탐색은 μ •λ ¬λœ λ°°μ—΄μ—μ„œλ§Œ μ‚¬μš©ν•΄μ™€μ„œ,

이뢄 탐색을 μ–΄λ–»κ²Œ ν™œμš©ν•  수 μžˆμ„μ§€ μ˜€λž«λ™μ•ˆ μƒκ°ν•΄λ³΄μ•˜λ‹€.


mid 포인트 값이 mid + 1 포인트 값보닀 μž‘λ‹€λ©΄?

mid 포인트 값은 peak element κ°€ 될 ν™•λ₯ μ΄ μ‘΄μž¬ν•˜μ§€ μ•ŠλŠ”λ‹€.

λ”°λΌμ„œ 탐색 λ²”μœ„λ₯Ό mid+1 μ΄μƒμœΌλ‘œ μž‘μ•„μ€˜μ•Ό ν•  것이닀.


λ§Œμ•½, mid 포인트 값이 mid + 1 포인트 κ°’ 보닀 크닀면

mid 포인트 값은 peak element κ°€ 될 ν™•λ₯ μ΄ μ‘΄μž¬ν•œλ‹€.

λ”°λΌμ„œ, 탐색 λ²”μœ„λ₯Ό mid μ΄ν•˜λ‘œ μž‘μ•„μ€˜μ•Ό ν•œλ‹€.

 

μœ„ 아이디어λ₯Ό λ°”νƒ•μœΌλ‘œ μ½”λ“œλ₯Ό κ΅¬ν˜„ν•˜μ˜€λ‹€.

 

 

 

class Solution {
    public int findPeakElement(int[] nums) {
        int left = 0, right = nums.length - 1;
        while (left < right) {
            int mid = (left+right) / 2;
            if(nums[mid]<nums[mid+1]){
                left = mid+1;
            }else{
                right = mid;
            }
        }
        return left;
    }
}

 

κ²°κ³Ό


πŸ“– 회고

μ‹œκ°„ λ³΅μž‘λ„λ₯Ό λͺ…μ‹œν•΄μ€˜μ„œ, 이뢄탐색 방식을 λ– μ˜¬λ Έκ³  그에 맞게 λ‘œμ§μ„ μƒκ°ν•˜λ‹ˆ κ΅¬ν˜„ν•  수 μžˆμ—ˆλ‹€.

 

둜직이 μ§κ΄€μ μœΌλ‘œλŠ” 이해가 κ°€λŠ”λ°, μˆ˜ν•™μ μœΌλ‘œλŠ” μ–΄λ–»κ²Œ 증λͺ…ν•΄μ•Όν• μ§€ μ‰½κ²Œ λ– μ˜€λ₯΄μ§€ μ•Šμ•„μ„œ 쑰금 μ°μ°ν•˜κΈ΄ν•˜λ‹€.

 

쀑간 지점을 κΈ°μ€€μœΌλ‘œ 였λ₯Έμͺ½ μ›μ†Œκ°€ 더 크면 였λ₯Έμͺ½ μ˜μ—­μœΌλ‘œ μ΄λ™ν•˜λŠ”λ°

 

였λ₯Έμͺ½ μ˜μ—­μ—, μ–΅μ§€λ‘œ peak λ₯Ό λ§Œλ“€μ§€ μ•ŠκΈ° μœ„ν•΄μ„œ 계속 큰 μ›μ†Œλ§Œ μ£Όμ–΄μ§„λ‹€κ³  κ°€μ •ν–ˆμ„ λ•Œ, κ²°κ΅­ λ°°μ—΄μ˜ 끝 값도 peak 포인트둜 μΈμ •λ˜κΈ° λ•Œλ¬Έμ— μ‘΄μž¬ν•¨μ„ μ•Œ 수 있고

 

κ·Έλ ‡λ‹€κ³  계속 큰 μ›μ†Œλ§Œ μ£Όμ–΄μ§€μ§€ μ•Šκ³ , μž‘μ€ μ›μ†Œκ°€ λ‚˜νƒ€λ‚˜λŠ” μˆœκ°„ peak ν¬μΈνŠΈκ°€ 생기기 λ•Œλ¬Έμ— μ‘΄μž¬ν•œλ‹€κ³  생각할 수 μžˆκ² λ‹€.

  • 문제 νŒŒμ•…
  • 풀이
  • 1️⃣ 이뢄 탐색을 μ΄μš©ν•œ 풀이
  • κ²°κ³Ό
  • πŸ“– 회고
'πŸ‘¨πŸ»β€πŸ’» PS/LeetCode 150' μΉ΄ν…Œκ³ λ¦¬μ˜ λ‹€λ₯Έ κΈ€
  • [Java] 153. Find Minimum in Rotated Sorted Array
  • [Java] 33. Search in Rotated Sorted Array
  • [Java] 148. Sort List
  • [Java] 242. Valid Anagram
우규이인우윀
우규이인우윀
개발자 κΏˆλ‚˜λ¬΄

ν‹°μŠ€ν† λ¦¬νˆ΄λ°”

단좕킀

λ‚΄ λΈ”λ‘œκ·Έ

λ‚΄ λΈ”λ‘œκ·Έ - κ΄€λ¦¬μž ν™ˆ μ „ν™˜
Q
Q
μƒˆ κΈ€ μ“°κΈ°
W
W

λΈ”λ‘œκ·Έ κ²Œμ‹œκΈ€

κΈ€ μˆ˜μ • (κΆŒν•œ μžˆλŠ” 경우)
E
E
λŒ“κΈ€ μ˜μ—­μœΌλ‘œ 이동
C
C

λͺ¨λ“  μ˜μ—­

이 νŽ˜μ΄μ§€μ˜ URL 볡사
S
S
맨 μœ„λ‘œ 이동
T
T
ν‹°μŠ€ν† λ¦¬ ν™ˆ 이동
H
H
단좕킀 μ•ˆλ‚΄
Shift + /
⇧ + /

* λ‹¨μΆ•ν‚€λŠ” ν•œκΈ€/영문 λŒ€μ†Œλ¬Έμžλ‘œ 이용 κ°€λŠ₯ν•˜λ©°, ν‹°μŠ€ν† λ¦¬ κΈ°λ³Έ λ„λ©”μΈμ—μ„œλ§Œ λ™μž‘ν•©λ‹ˆλ‹€.