Row of the odd triangle<6 kyu>

jjanmo·2020년 2월 4일

문제

문제 간단 설명!

             1
          3     5
       7     9    11
   13    15    17    19
21    23    25    27    29
...

이러한 연속된 홀수로 구성된 숫자 삼각형이 주어졌을때,, 각각에 행에 해당하는 숫자의 집합을 배열로 리턴하시오.

odd_row(1)  ==  [1] 		//1행에 해당하는 숫자 집합
odd_row(2)  ==  [3, 5]		//2행에 해당하는 숫자 집합
odd_row(3)  ==  [7, 9, 11]	//3행에 해당하는 숫자 집합

문제접근

이 문제는 이전에 풀었던 문제인 Sum of odd numbers의 시리즈물이다. 문제를 접근하는 방법은 비슷하였다. 우선 1️⃣ 삼각형 안의 연속된 숫자를 배열이라고 생각하고 2️⃣ 해당 열이 배열의 몇번째 인덱스부터 몇번째 인덱스인지 찾는다. 3️⃣ 그 부분만을 값으로 갖는 배열을 만들어서 리턴한다. 이전 문제는 주어진 열의 총 합을 구하는 것이였는데, 이 부분만 다르다.

1	function oddRow(n) {
2	  const arr = [];
3	  const start = Array.from({length : n},(v,i)=> i).reduce((a,c)=> a+c,0);
4	  for(let i = start; i <start+n; i++){
5	    arr.push(2*i+1);
6	  }
7	  return arr;
8	}

3번라인 : 해당 열이 배열의 몇번째부터 시작하는지를 배열로서 접근해서 구한 코드

사실 이 부분은 문제를 풀다보니 배열의 시작 인덱스를 구하는데 다시 배열을 생성해서 구해야만 하는건가라는 생각이 들었다. 하지만 딱히 다른 방법을 떠오르지 않아서 이렇게 풀이하였다.(코드만 다르지 다 같은 인덱스로 접근하는 방법만 떠오를뿐...😒) 예상대로 효율성이 떨어지는 풀이라 시간이 꽤 많이 걸렸지만 다행히 시간초과는 면하였다.

4~6번라인 : 홀수 삼각형이고 해당 열의 시작 인덱스를 알기 때문에 직접 값을 구해서 배열을 만드는 코드

Best Solution

  function oddRow(n) {
    const m = n * (n - 1) + 1;
    return [...Array(n)].map((_, i) => m + 2 * i);
  }

코드의 테스트 수행에 걸린 시간을 비교해봤다.

Best Solution : Time: 3696ms Passed: 3 Failed: 0
My Solution : Time: 5159ms Passed: 3 Failed: 0

딱봐도...1500ms정도 차이난다. 역시나 구하고자하는 행(n)이 커질수록 걸리는 시간이 많이 걸렸다.

위 코드는 직접 각 행의 시작 값을 직접 구했다. 그 값부터 공차가 2인 등차수열에 개수는 n개인 값들을 배열로 만들면 된다. 위 코드는 배열 순회를 map() 메소드에 의해서 1번만 진행한다. 그러나 나의 코드는 start를 구할 때, 2번 순회를 하고(배열 맵핑 + reduce()) 리턴값의 배열을 만들때 1회 순회한다고 볼 수 있다.(물론 순회하는 배열이 다 다르지만, n이 엄청 큰 값이라고 하면 뭐가 됐든 시간 소요가 심하다.)

const m = n * (n - 1) + 1 이 어떻게 나왔는지 살펴보자.