n^2 배열 자르기 [프로그래머스]

wkahd01·2021년 11월 1일
1

알고리즘

목록 보기
18/24
post-thumbnail

문제

https://programmers.co.kr/learn/courses/30/lessons/87390

입출력 예 #2 [4,7,14]

풀이

2가지 방법으로 풀었는데, 첫 번째 방법은 시간초과가 떴고, 두 번째 방법은 정상적으로 테스트를 통과하였다.

첫 번째 방법(시간초과)

Code

function solution(n, left, right) {
    let frame = Array.from({length: n}, (v, i) => i+1);
    const answer = [];
    let index = parseInt(left/n);
    
    for(let i=0;i<n;i++){
        if(i<=index) frame[i]=index+1
    }
    answer.push(...frame)
    
    for(let i=index+1;i<parseInt(right/n)+1;i++){
        for(let j=0;j<n;j++){
        if(frame[j]<=i) frame[j]=i+1
    }
        answer.push(...frame)
    }
    return answer.slice(left-index*n,right-index*n+1);
    //return answer;

}

idea


left(7)가 포함된 색부터(노란색) right(14)가 포함된 색까지 배열 구하기


Process

1. 노란색 부분의 2,2,3,4를 구한다.
2. 보라색 부분까지의 배열을 구한다. [2,2,3,4,3,3,3,4,4,4,4,4]
3. slice를 사용해 { } 사이의 부분을 구한다.

문제점:

이중 for문을 돌리기 때문에 O(n^2)이 나옴.



두 번째 방법(성공)

Code

function solution(n, left, right) {
    var answer = [];
    
    let frame = Array.from({length: right-left+1}, (v, i) => i+left);
    for(let i=0;i<frame.length;i++){
        // 몫+1
        const quotient = parseInt(frame[i]/n)+1
        // 나머지+1
        const remainder = frame[i]%n+1
        if(remainder>quotient) {
            answer[i] = remainder
        }
        else{
            answer[i] = quotient
        }
        //console.log(quotient,remainder)
    }
    //console.log(frame)
    return answer;
}

idea


left(7) 부터 right(14)가 들어있는 배열을 만들어 모듈러 연산으로 해를 구한다.


Process

1. [7,8,9,10,11,12,13,14]의 배열을 만든다.
2. 배열 내부의 각 요소에서 n을 나눈 몫, 나머지를 구한다.

3. 만들어진 몫(quotient), 나머지(remainder)에 +1씩 더한다.

4. (나머지 +1) 보다 (몫 +1)이 더 큰 경우에는 result에 (몫+1)을 넣어주고,
작은 경우에는 result에 (나머지+1)을 넣어준다.

profile
꾸준하게 공부하기

0개의 댓글