Moon Seung Hyun

[CodingTest] 벽안에 고인 빗물의 양


문제

주어지는 행렬 arr(ex - [3,0,1,3,0,5])값의 인자들을 벽이라고 했을때 비가와서 물이 고이는 부분의 양을 구하여라.

답 : 8

내가 생각한 풀이

  • 풀어본 시간 : 1시간
  • 중간까지 밖에 못함. 접근방법이 복잡해져서 방향을 잘못잡음.
    • 위로 꺾은 선들을 찾아서 각 구간마다 물이 고일수있는 max값을 찾고
    • 해당 구간에서 max - arr[i] 값들의 합을 구하려고 했음
function solution(arr) {
    let upperPoints = {0: arr[0]} // {index: value, ...}
    for(let i=0;i>arr.length;i++) {
        if(arr[i-1] < arr[i]) if(arr[i+1] == undefined) upperPoints[i] = arr[i]
        else if(arr[i] > arr[i+1]) upperPoints[i] = arr[i]
    }

    let filteredPoints = {0: arr[0]}, // {index: value, ...}
        startPoint = [0, arr[0]]
    for((p,i) of upperPoints) {
        if(&& startPoint >= upperPoints[i] && i != 0 ) {
            filteredPoints[i] = upperPoints[i];
        }
    }

    // 중단함.
}

정답풀이법

  • 아이디어
    • 왼쪽과 오른쪽을 각각 돌며 각 index마다의 물이 고일 수 있는 max값 찾음.
    • 왼쪽 / 오른쪽에서 찾은 max값들 중 min 값으로 [min - 해당 index] 값을 구해서 total로 더함.
// 시간복잡도 O(n) 공간복잡도 O(n)
function solution(arr) {
    let left_maxes = [], 
        right_maxes = [],
        current_left_max = 0, 
        current_right_max = 0, 
        total = 0;

    for(let i=0; arr.length > i; i++) {
        current_left_max = Math.max(current_left_max, arr[i]);
        left_maxes[i] = current_left_max;
    }
    
    for(let i=arr.length-1; 0 <= i; i--) {
        current_right_max = Math.max(current_right_max, arr[i]);
        right_maxes[i] = current_right_max;
    }

    for(let i=0; arr.length > i; i++) {
        total += Math.min(left_maxes[i], right_maxes[i]) - arr[i];
    }
    return total;
}

업그레이드된 정답풀이법

  • 목적
    • 공간 복잡도를 O(1)로 만들기위해 left_maxes, right_maxes를 없앰.
  • 아이디어
    • 가장 큰 수를 기점으로 오른쪽 / 왼쪽 나눔.
  • 단점
    • 울퉁불퉁한 모양이면 답이 제대로 나오지만 계단형태의 그래프일 경우 답이 이상하게 나옴.
    • arr = [1,2,3,4,5] 또는 [5,4,3,2,1]의 경우 답이 -3 나옴.
    • arr = [5,2,6,1,8,9,9,7] 에 해당하는 답안이 이상함.
    • arr = [3,0,1,3,0,5] 에만 잘 되는 답임.
// 시간복잡도 O(n) 공간복잡도 O(1)
function solution(arr) {
    if (arr.length == 0) return 0

    let total = 0,
        max_i = arr.indexOf(Math.max(...arr)),
        left_max = arr[0],
        right_max = arr[arr.length-1];

    for (let i=1; max_i > i; i++) {
        total += left_max - arr[i];
        left_max = Math.max(left_max, arr[i]);
    }

    for (let i=arr.length-2; max_i<i; i--) {
        total += right_max - arr[i];
        right_max = Math.max(right_max, arr[i]);
    }

    return total;
}




2023

Flutter 맛보기 1

3 분 소요

직방 기술지원팀 기술공유 세미나 중 플러터를 소개한 내용입니다

Back to Top ↑

2022

Back to Top ↑

2019

[Tutorial] Storybook과 Bit을 활용한 UI 컴포넌트 관리(Workflow)

1 분 소요

회사에서 프론트엔드 개발원칙을 SFC(Single File Component)에서 UI 컴포넌트를 기준으로 CDD(Component Driven Development)를 진행하려고 한다. 그래서 체계적으로 관리하기위해 Storybook과 Bit을 도입해보고자 한다. 각각의 역할은 ...

[Workflow] 프론트엔드 개발조직을 위한 워크플로 설계

2 분 소요

작성 배경 회사의 작업구조를 페이지 중심 개발에서 UI 컴포넌트 중심 개발로 변경하면서 Workflow를 개선할만한 환경을 구성해야했다. 폐쇄망 기반에서 개발자간 UI 명세서 역할을 할 수 있는 Storybook과 그것을 공유할 Verdaccio라는 구축형 NPM Pri...

[ESlint & Prettier] 개발 관습 설정 in Visual Studio

1 분 소요

회사 프로젝트를 작업하기 전 프론트엔드 개발자들 간의 코드 규칙을 Eslint와 Prettier 설정을 맞춰 관리해가는 방향을 정했다. 아직 협업을 할 경우는 없지만 미래에 인수인계 받거나 협업을 진행할 경우 코드관습이 달라 고생할 경우를 대비하기로 했다. 설정은 작업을 진행하며 ...

[CodingTest] 2019-10-26 SQL문제

최대 1 분 소요

공부겸 코딩테스트 사이트에서 토요일 오전 10시에 백엔드 포지션 테스트를 해준다기에 참여해봤다. SQL문제가 나왔는데 더 좋은 답이 있는것 같아 나중에 기록해두고 수정해보기로 한다.

[CodingTest] 피보나치 수열

1 분 소요

문제 : 피보나치 수열 제 1항부터 입력한 자연수(N)까지의 피보나치 수열 항들의 합을 구하여라.

[Syntax] 새로 알게된 파이썬 문법 정리

최대 1 분 소요

chaning comparison 파이썬은 chaning comparison이라는 신기한 문법이 있다. 참고 if a < b and b < c : (...) 라는 구문이 if a < b < c : (...) 으로 연산된다. 직관적인 문법이 인상적. ...

[DataType] Map & Set

최대 1 분 소요

Set vs Array - 관련기사 Set 유일값들의 배열이 필요할때(distinct) 집합의 개념이 필요할때(차집합, 교집합 등등 자체 메서드들이 많음.) index가 필요 없을때 Array에서 중복값을 없앨때 => ...

Back to Top ↑

2018

SGIS-shpToGeojson

1 분 소요

SGIS에서 받은 지도데이터(.shp)를 geojson으로 변경하는 작업 내용

Back to Top ↑