[코딩문제풀기 1일차] Peak Index in a Mountain Array

Introduction

꾸준히 코딩문제를 풀기 위해서 스팀잇에 매일매일 푼 문제의 해설을 적어보려합니다.
leetcode와 codewars 사이트를 주로 사용할 것입니다.

Talk is cheap. Show me the code. - 리누스 토발즈

Problem

난이도: Easy

다음 속성을 따르는 A라는 산 배열이 있다:

A.length >= 3
A[0] < A[1] < ... A[i-1] < A[i] > A[i+1] > ... > A[A.length - 1]를 만족하는 0 < i < A.length - 1가 존재한다.

산 배열이 주어지면, A[0] < A[1] < ... A[i-1] < A[i] > A[i+1] > ... > A[A.length - 1]를 만족하는 i를 반환해야 한다.

예제 1:

Input: [0,1,0]
Output: 1

예제 2:

Input: [0,2,1,0]
Output: 1

유의사항:

3 <= A.length <= 10000
0 <= A[i] <= 10^6
A는 위에서 말했듯이 산이다.

문제 출처: leetcode 852. Peak Index in a Mountain Array

Solution

Javascript를 사용해서 두 방법으로 풀었습니다.
해설로 나온 나머지 두 방법도 설명드리겠습니다.
Github solution 코드 보기

Solution 1 : `forEach`를 사용한 기본적인 방법

let peakIndexInMountainArray = A => {
    let peak = -1, index = -1;
    A.forEach((v, i) => {
        if (v > peak) {
            peak = v;
            index = i;
        }
    });
    return index;
};

A 배열에서 forEach를 돌려서 최대값(peak)을 찾은 후, index에 그 최대값의 인덱스를 저장하고 있습니다.
시간복잡도는 O(N) 으로 N은 A 배열의 길이입니다.

Solution 2 : `Array.indexOf()`와 `Math.max()`를 사용한 방법 (Very Simple!)

let peakIndexInMountainArray = A => A.indexOf(Math.max(...A));

A 배열에서 최대값을 구한 후, Javascript에 내장된 indexOf 함수를 사용해서 최대값의 인덱스를 가져오고 있습니다.
시간복잡도는 마찬가지로 O(N) 입니다.

// 여기서부터는 사이트에 나와있는 해설입니다.

Solution 3 : Linear Scan

let peakIndexInMountainArray = A => {
    let i = 0;
    while(A[i] < A[i + 1]) i++;
    return i;
}

i를 증가시키면서 증가하는 구간에서 감소하는 구간으로 바뀌는 순간에 반복문을 탈출하여 i를 반환합니다.
시간복잡도는 마찬가지로 O(N) 입니다.

Solution 4 : Binary Search (Very Important!!!)

let peakIndexInMountainArray = A => {
    let lo = 0, hi = A.length - 1
    while (lo < hi) {
        let mi = Math.floor((lo + hi) / 2)
        if (A[mi] < A[mi + 1]) lo = mi + 1
        else hi = mi
    }
    return lo
}

A 배열은 A[i] < A[i+1]이므로 [true, true, true, ..., true, false, false, ..., false]와 같이 나타낼 수 있습니다. (true가 1개 이상이고, false가 1개 이상입니다.)
위 성질을 이용해서 false인 부분을 이진검색으로 찾을 수 있습니다.
따라서 시간복잡도는 O(logN) 으로 위 3개의 solution보다 시간복잡도가 짧습니다.

2018/06/19 Written by Jon Jee

자바스크립트도 이런코드를 쓸 수 있네요!
생각보다(?) 깊은 언어같기도...
클러이언트단에서 내려받아서 동작하는 언어라
웹해킹 취약포인트가 발생되는 부분이 참 많았던거 같아요.
스크립트 난독화 이런거만보다가 공부하는 글도 새롭네요 +.+
아! 그리고 저도 뉴비지만...?
전체적으로 게시글들이 태그활용이 잘 안되는거같아요.
먹거리는 muksteem kr-food tasteem 태그가 있고 kr-newbie jjangjjangman 태그도 있답니다.
ourselves도 있고.. 찾아보면 많다능! kr-dev 도 있을텐뎅.
현재 지갑에 스달이 $5.943 있으신거 같은데 이것도 놀지말고 보팅봇 부르시길 추천드려요!
보상이 있어야 글쓰는 재미도 있으니까요 @_@! 또 올려주세요~

Sort:

Trending

[-]

virus707 (76) 7 years ago

(jjangjjangman 태그 사용시 댓글을 남깁니다.)
호출에 감사드립니다! 즐거운 스티밋하세요!