[CodeKata] 프로그래머스 : 4.30(금), 2 x n 타일링 & N으로 표현

🥋 Oooth More!! (Level 3)

 

 🧮 풀이

const solution = (n) => {
  let previous = 0;
  let current = 1;

  for (let i = 0; i < n+1; i += 1) {
    const save = previous;
    previous = current
    current = (save + current) % 1000000007
  }

  return previous ;
}

1. 피보나치 수열의 규칙성을 가진 문제다. 단, 본래 피보나치보다 인덱스가 1 많아야 한다.
2. 효율성을 줄임에 있어 많은 고민을 했다. 우선, 함수를 2번 선언하는것과 solution 1개로만 연산하는 것에서 후자가 효율적이었다.
3. 또한, 본래는 save에 (previous + current) % 1000000007 을 저장했는데 이 역시 변수에 큰 값이 저장되므로 previous만 저장

---

🥋 Oooth More!! (Level 3)

 

 🧮 풀이

function solution(N, number) {
    const set = new Array(8).fill().map(() => new Set());
    
    for(let i=0; i<8; i++){
        set[i].add(Number(N.toString().repeat(i+1)));
        
        for (let j=0; j < i; j++) {
            for(const arg1 of set[j]){
                for(const arg2 of set[i-j-1]){
                    set[i].add(arg1+arg2);
                    set[i].add(arg1-arg2);
                    set[i].add(arg1*arg2);
                    set[i].add(arg1/arg2);
                }
            }
        }
        if(set[i].has(number)) {
          return i+1;
        }
    }
    return -1;
}

1. set라는 Set() 로 이루어진 배열을 만든다. 또한, 최솟값이 8보다 작은 경우 -1을 리턴하므로 배열의 길이도 8로 설정한다.
2. 우선, set 인덱스를 0부터 순회한다. 각 인덱스는 (해당값+1) 만큼 N을 사용하는 경우이다.
3. 그렇기에, 가장 먼저 N을 (i+1) 만큼 사용한 숫자를 넣어준다. (0번 인덱스엔 5, 1번 인덱스엔 55, 2번 인덱스엔 555 순서로)
4. 다음으로, 사칙연산의 경우를 구한다. 내부에서 한번 더 순회하며, 이는 숫자를 2개 이상 사용하는 경우이므로 1번 인덱스부터 할당
5. j는 set의 0번 인덱스부터 탐색하며, j번째와 i-j-1번째 set 요소값들을 조합하면 (i+1)개의 N을 이용한 사칙연산 경우가 나온다.
6. 이 set에 들어있는 각각의 값을 for - or 문으로 순회하며 사칙연산의 경우를 set[i] 에 첨가해준다.
7. 현재 set[i]가 number 를 가지고 있다면(has()) i+1(개수)를 반환, 없었다면 8개보다 많은 N이 사용되므로 -1을 반환한다.

 

🖇 리뷰

첫 번째 문제의 경우 피보나치 규칙성을 보이며, 조합(nCr) 풀이로도 풀 수 있었다.

특히, 다양한 조건변경을 통해 효율성이 어떻게 바뀌는지 경험할 수 있는 기회였다. (배열에 저장하는 것보단 변수를 활용하는게 효율적)

 

두 번째 문제는 사실 풀지를 못해 모범답안을 해석한 내용이다. 레벨3으로 올라온만큼 문제들이 알고리즘의 공식을 요구하게 된다.

(해당 문제는 동적 프로그래밍)