본문 바로가기
  • 삽질하는 자의 블로그
CS와 언어, 라이브러리 이론/알고리즘-이론과 실전

7. [실전] - 우박수열

by 이게뭐당가 2023. 1. 18.

문제

1-1. 입력된 수가 짝수라면 2로 나눕니다.
1-2. 입력된 수가 홀수라면 3을 곱하고 1을 더합니다.
2.결과로 나온 수가 1보다 크다면 1번 작업을 반복합니다.

        5168421

        우박수열을 좌표 평면 위에 꺾은선 그래프로 나타내보려고 합니다. 
        초항이 K인 우박수열이 있다면, x = 0일때 y = K이고 다음 우박수는 x = 1에 표시합니다. 
        이런 식으로 우박수가 1이 될 때까지 점들을 찍고 인접한 점들끼리 직선으로 연결하면 
        다음과 같이 꺾은선 그래프를 만들 수 있습니다.

        이렇게 만든 꺾은선 그래프를 정적분 해보고 싶어졌습니다.
        x에 대한 어떤 범위 [a, b]가 주어진다면 
        이 범위에 대한 정적분 결과는 꺾은선 그래프와 x = a, x = b, y = 0 으로 둘러 쌓인 공간의 면적

        우박수열 그래프의 가로축 길이를 미리 알 수 없기 때문에 구간의 시작은 음이 아닌 정수, 
        구간의 끝은 양이 아닌 정수로 표현합니다. 

            => (앞은 앞에서부터 짜르고, 뒤는 뒤에서부터 짜른다는 말)

        이는 각각 꺾은선 그래프가 시작하는 점과 끝나는 점의 x좌표에 대한 상대적인 오프셋을 의미합니다.

        예를 들어, 5를 초항으로 하는 우박수열은 5168421 입니다. 
        이를 좌표 평면으로 옮기면 (0, 5), (1, 16), (2, 8), (3, 4), (4, 2), (5, 1) 에 점이 찍히고 
        점들을 연결하면 꺾은선 그래프가 나옵니다. 
        이를 [0,0] 구간에 대해 정적분 한다면 전체 구간에 대한 정적분이며,
        [1,-2] 구간에 대해 정적분 한다면 1 ≤ x ≤ 3인 구간에 대한 정적분입니다.

        우박수의 초항 k와, 정적분을 구하는 구간들의 목록 ranges가 주어졌을 때 
        정적분의 결과 목록을 return 하도록 solution을 완성해주세요. 
        단, 주어진 구간의 시작점이 끝점보다 커서 유효하지 않은 구간이 주어질 수 있으며 
        이때의 정적분 결과는 -1로 정의합니다.

예시

  [ 예시 ]
        k	 ranges	                               result
        5	 [[0,0],[0,-1],[2,-3],[3,-3]]	 =>    [33.0,31.5,0.0,-1.0]

    [입출력 예 #1]
        5로 시작하는 우박수열은 5168421 입니다. 
        그래프에서 꺾이는 지점을 경계로 5개의 구역으로 나눠보면 각각의 구간 넓이는 10.5, 12, 6, 3, 1.5 입니다.

        주어진 점이 겹치면  0 
        주어진 점의 범위가 뒤로 넘어가면 -1
        나머지는 계산
    
    [그래프 예시]
       
               16
                      8
       
         5   
                            4
                                 2 
                                       1

        (0)   (1)   (2)   (3)   (4)  (5)
        (시작점 0 ~ 5)           (끝시작점 0 ~ -5)

 

사용

0) while"참일 때 돌린다"
1) forif 의 적절한 조화 ( for"참이면 돌린다"는 사실 명심 )
2) map 의 안에, 배열 자체를, 값으로 넣는 방법 사용
    map 안에 돌리는 value 에 "배열"을 넣으면 따로 분리되서 사용된다.

    const A = [[1, 2],[3, 4]] ;
    A.map(([a, b]) => console.log(a, b));       // 1,2      // 3,4

 

내코드

function solution(k, range) {
    const square = [];      // 각 범위마다의 넓이

    for (i = 0; k !== 1; i++) {
        if (k % 2 === 0) {
            square.push((k + k / 2) / 2);
            k = k / 2;
        } else {
            square.push((k + (k * 3 + 1)) / 2);
            k = k * 3 + 1;
        }
    }
    return range.map(([s, e]) => {              // range 를 기준으로, 값에, 시작 끝 이 들어있는 배열을 그대로 집어넣음 ***
        if (square.length + e < s) return -1;       // 끝 범위가 시작 범위를 넘어선다.
        else if (square.length + e === s) return 0;     // 끝 범위와 시작 범위가 동일하다.
        else if (e === 0) {                             // 끝이 0 인경우
            return square.slice(s, square.length).reduce((a, b) => a + b);
        } else {
            return square.slice(s, e).reduce((a, b) => a + b);	// 일반적인 경우
        }
    });
}

 

댓글