[CodingTest] i를 제외한 배열 요소들의 곱

문제

정수 배열이 주어지면 인덱스 i에 해당하는 값 이외의 모든 값들의 곱인 배열을 구하여라.
보너스 : 나눗셈을 안쓰고 풀기

예시

[1,2,3] => [6,3,2]
[1,2,3,4,5 ] => [120, 60, 40, 30, 24]

나눗셈이 있는 풀이법

// 2n => O(n)
function solution(arr) {
  const max = arr.reduce((a,b)=>a*b); // n
  let answer = [];
  for(let el of arr) { // n + n
    answer.push(max/el)
  }
  return answer
}

나눗셈 없는 풀이법

// n^2 = N(n^2)
function solution(arr) {
  return arr.map(el => // n
    arr.reduce((a,b) => { // n
      return el == b ? a : a*b
    },1)
  )
}

느낀점

O(N²) 이외의 풀이법은 생각이 나지 않음.

답변 및 해설

function solution(arr) {
    // Generate prefix solution
    let prefix_products = []
    for(el of arr) {
      if (prefix_products.length > 0) prefix_products.push(prefix_products[prefix_products.length-1] * el)
      else prefix_products.push(el)
    }
    console.log("prefix_products : ", prefix_products)

    // Generate suffix solution
    let suffix_products = []
    for(el of [...arr].reverse()) {
      if(suffix_products.length > 0) suffix_products.push(suffix_products[suffix_products.length-1] * el)
      else suffix_products.push(el)
    }
    suffix_products = [...suffix_products].reverse();
    console.log("suffix_products : ", suffix_products)

    // Generate result
    let result = []
    for (let i=0; i<arr.length; i++) {
      if(i == 0) result.push(suffix_products[i + 1]) // 첫 엘리먼트
      else if (i == arr.length - 1) result.push(prefix_products[i - 1]) // 마지막 엘리먼트
      else result.push(prefix_products[i - 1] * suffix_products[i + 1])
    }
    console.log("result : ", result)
    return result
}

해결방법 : 루프를 돌면서 해당 인덱스(i)의 prefix(앞부분들)와 suffix(뒷부분들)의 값들을 구해서 곱하는 방법.

prefix는 i번째의 앞부분들의 수의 곱
suffix는 i번째의 뒷부분들의 수의 곱

result는 루프를 돌면서 i번째 앞부분들의 곱과 뒷부분들의 곱에 해당하는 element 값들 간의 곱

아이디어

n²이외의 방법을 위해 여러가지 n을 만들어 풀기.
i번째의 앞부분들의 곱과 뒷부분들의 곱에 해당하는 array추출.

2023 1
2022 2
2019 45
2018 1

2023

Flutter 맛보기 1

3 분 소요

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

2022

D3.js 차트 개발 Hands on lab

5 분 소요

직방 기술지원팀 기술공유 세미나 중 D3.js를 소개한 내용입니다

직방이 사용자 행동 로그를 관리하는 방법. ZAMS

최대 1 분 소요

직방에서 작성했던 블로그 글을 공유합니다.

2019

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

1 분 소요

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

[Scaffold] Scaffold Module 개발

최대 1 분 소요

도입 이유

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

2 분 소요

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

[Git] Git Command 정리

3 분 소요

Git 시스템 이해하기

[Design Pattern] Monorepo 공부

2 분 소요

결론

[Methodology] CDD(Component Driven Development) - 테스트(2/2)

1 분 소요

Intro

[Methodology] CDD(Component Driven Development) - 계획(1/2)

1 분 소요

CDD(Component Driven Development)란?

GraphQL, Prisma, Apollo 공부

2 분 소요

GraphQL? RESTful?

[CodingTest] Combination(조합) 문제풀이 2

최대 1 분 소요

문제

[CodingTest] Combination(조합) 문제풀이 1

최대 1 분 소요

문제

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

1 분 소요

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