99클럽 코테 스터디 6일차 TIL - Climbing Stairs (리트코드 70 / JavaScript)

오늘의 문제 링크

 

⭐ intro : 문제를 생각해나간 방식

문제를 이해함에 있어서 꽤나 오랜 시간이 걸렸었다. 계단을 오르는 방식을 설명하는데, n개의 계단을 오를 때 필요한 방법의 갯수를 말해야 했다. 조건문을 정리하자면

• 총 계단 수는 1이상 45이하
• 1계단이나 2계단씩밖에 오르지 못하는 조건. 
• 2계단을 오르려면
  • (1번) 1 + 1계단을 오르거나
  • (2번) 2계단을 한꺼번에 오르기
• 3계단을 오르려면
  • (1번) 1 + 1 + 1계단을 오르거나
  • (2번) 2 + 1 계단을 오르거나
  • (3번) 1 + 2 계단을 오르기

라서, 각각 n이 2일경우 방법 2가지를 리턴, 3일 경우 3가지를 리턴하고 있었다. 그러나 막상 두가지 테스트 케이스만으로는 도통 문제를 이해할 수가 없어서, 한번 4계단 이후의 경우의 갯수도 한번 적어봤었다.

• 4계단을 오르려면 (이하 한글 생략)
  • (1번) 1 + 1 + 1 + 1
  • (2번) 1 + 1 + 2
  • (3번) 1 + 2 + 1
  • (4번) 2 + 1 + 1
  • (5번) 2 + 2
• 5계단을 오르려면
  • (1번) 1 + 1 + 1 + 1 + 1
  • (2번) 1 + 1 + 1 + 2
  • (3번) 1 + 1 + 2 + 1
  • (4번) 1 + 2 + 1 + 1
  • (5번) 2 + 1 + 1 + 1
  • (6번) 1 + 2 + 2
  • (7번) 2 + 1 + 2
  • (8번) 2 + 2 + 1 
• n(계단의 수)과 return(올라갈 수 있는 방법의 수)값과의 비교 ( n / return )
  • 1 / 1
  • 2 / 2
  • 3 / 3
  • 4 / 5
  • 5 / 8

...? 여기서 return 값을 보면서 뭔가 익숙한 숫자의 조합을 발견할 수 있었다. 그렇다면... n에 6을 넣을 경우 총 방법의 수는 5 + 8인 13이 나와야 한다. 한번 일일히 세어보기로 했다

• 6계단을 오르려면...? (편의상 + 제거)
  • 1 1 1 1 1 1
  • 1 1 1 1 2
  • 1 1 1 2 1
  • 1 1 2 1 1
  • 1 2 1 1 1
  • 2 1 1 1 1
  • 1 1 2 2
  • 1 2 1 2
  • 2 1 1 2
  • 2 1 2 1
  • 1 2 2 1
  • 2 2 1 1
  • 2 2 2

정답이다. 13이다. 이 값인 즉슨 이 문제는 피보나치 수열의 index값을 대입하면 그 값을 return하도록 하는 문제였다!! 뭔가 더 빠른 방법으로 피보나치 수열이라는 것을 알았으면 좋으련만, 수학적 지식이 부족한 내 입장에서는 이렇게 생노가다 방식으로 푸는 방법외에는 잘 떠오르지 않는다 긁적긁적...

 

⭐ 풀이과정

피보나치 수열은 대개 다음과 같이 이루어져 있다. 1 1 2 3 5 8 13 ....각각 인덱스와 대입해서 보게 되면

• 수열(return) : 1 1 2 3 5 8 13 ...
• 인덱스(n)     : 0 1 2 3 4 5 6

당연하다면 당연한 결과일것으로, 각 인덱스 값(1이상)과 수열의 값이 1:1로 잘 매칭이 된다. 그렇다면, 각 return 값이 나오기 위해서는 값의 계산이 어떻게 이루어져야 할까? 이 또한 간단히 도식화해서 생각해 보았다.

n의 값	result	더하는 숫자
1	1	0 1
2	2	1 1
3	3	1 2
4	5	2 3

 

이를 코드화 해서, 배열을 만들고 각 [0]번째 값과 [1]번째 값에 이전 값의 결과값과 현재 값을 계속 반복해서 넣도록 만들어 보았다. 그래서 간단히, 다음과 같은 값을 만들어 제출했다.

 

 

⭐ 제출답안

var climbStairs = function (n) {
  const arr = [0, 1];
  let result = 0;
  for (let i = 0; i < n; i++) {
    result = arr[0] + arr[1];
    arr[0] = arr[1];
    arr[1] = result;
  }
  return result;
};

⭐ 공부했던 개념들

• JS로 피보나치 수열 코딩하기

[JavaScript] 피보나치 수열 코딩

• 재귀