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

woolee의 기록보관소·2022년 10월 26일

Algorithms 알고리즘개념정리

알고리즘 문제풀이

목록 보기

20/178

문제 출처

프로그래머스 lev2 - n^2 배열 자르기

문제

나의 풀이

시도1

아래 풀이는 signal: aborted (core dumped) 오류 발생

function solution(n, left, right) {
  let od = Array.from({length:n}, () => Array.from({length:n}, () => 0));
  let cnt=1;

  for (let i=1; i<=n; i++) {
    let tmp=cnt;
    for (let j=tmp; j<=n; j++) {
      od[i-1][j-1]=j;
    }
    for (let j=1; j<od.length; j++) {
      if (od[i-1][j-1]==0) {
        od[i-1][j-1]=tmp;
      }
    }
    cnt++;
  }

  return od.flat().slice(left, right+1);
}

console.log(solution(3, 2, 5));

시도2

마찬가지로 signal: aborted (core dumped) 오류 발생...

function fl(array) {
  return array.reduce((result, x) => result.concat(
    Array.isArray(x) ? fl(x) : x), [])
}

function solution(n, left, right) {
  let od = Array.from({length:n}, () => Array.from({length:n}, () => 0));
  let cnt=1;

  for (let i=1; i<=n; i++) {
    let tmp=cnt;
    for (let j=tmp; j<=n; j++) {
      od[i-1][j-1]=j;
    }

    for (let k=1; k<od.length; k++) {
      if (od[i-1][k-1]==0) {
        od[i-1][k-1]=tmp;
      }
    }
    cnt++;
  }

  return fl(od).slice(left, right+1);
}

시도3

애초에 중첩 배열을 만들지 않고 바로 answer에 넣고 count가 right보다 커지면 break 함으로써 좀 더 빠르게 해봤더니 tc11까지는 통과된다..! 이후는 런타임 에러 등장

function solution(n, left, right) {
  let cnt=1;
  let count=0;
  let answer = [];

  for (let i=1; i<=n; i++) {
    if (count>right) break;

    let tmp=cnt;
    for (let j=1; j<=n; j++) {
      if (j<tmp) {
        answer.push(tmp);
        count++;
      }
      else if (j>=tmp) {
        answer.push(j);
        count++;
      }
    }
    cnt++;
  }

  return answer.slice(left, right+1);
}

시도4

left ~ right만 answer 배열엔 넣기. tc12까지 통과. 이제는 런타임이 아니라 시간 초과

function solution(n, left, right) {
  let cnt=1;
  let count=0;
  let answer=[];

  for (let i=1; i<=n; i++) {
    if (count>right) break;
    let tmp=cnt;
    for (let j=1; j<=n; j++) {
      if (j<tmp && count >= left && count <= right) {
        answer.push(tmp);
      }
      else if (j>=tmp && count >= left && count <= right) {
        answer.push(j);
      }

      count++;
    }
    cnt++;
  }

  return answer;
}

console.log(solution(4, 7, 14));

다른 풀이(통과 코드)

시간초과가 발생할 것 같을 때는 차근차근 규칙을 찾아봐야 한다.

각 행과 열에서 규칙을 찾기.

1행 1열 (1,1) = 1
1행 2열 (1,2) = 2
1행 3열 (1,3) = 3
2행 3열 (2,3) = 3
...

즉, (행,열)의 값은 Math.max(행,열) 혹은 idx 관점으로는 Math.max(행,열)+1

function solution(n, left, right) {
    var answer = [];

    for (let i = left; i <= right; i++) {
        answer.push(Math.max(i % n, parseInt(i / n)) + 1)
    }

    return answer;
}

function solution(n, left, right) {
    const ans = [];

    while (left <= right) {
        ans.push(Math.max(Math.floor(left / n), left++ % n) + 1);
    }

    return ans;
}

[참고]배열 평탄화 작업

function flat(arr) {
  return arr.reduce((a, b) => a.concat(
    Array.isArray(b) ? flat(b) : b), [])
}

혹은
const flat =arr =>
    arr.reduce((a,b) => 
        [...a, ...(Array.isArray(b) ? flat(b) : [b])]
    , []);

중복 제거 후 배열 합치기
var a
var a1 = [1, 2, 3];
var a2 = [3, 4, 5, 6];

var merged = a1.concat(a2);
var unique = merged.filter((item, pos) => merged.indexOf(item) === pos);

console.log(unique);
// [1, 2, 3, 4, 5, 6]