배열 자료구조 문제풀이 #3

오늘은 백준에서 프로그래머스로 넘어와 배열 문제를 풀어보았습니다.

문제

: 정수 n, left, right가 주어집니다. 다음 과정을 거쳐서 1차원 배열을 만들고자 합니다.

n행 n열 크기의 비어 있는 2차원 배열을 만듭니다.
i = 1, 2, 3, ..., n에 대해서 다음 과정을 반복합니다.
1행 1열부터 i행 i열까지의 영역 내의 모든 빈칸을 숫자 i로 채웁니다.
1행, 2행, ..., n행을 잘라내어 모두 이어 붙인 새로운 1차원 배열을 만듭니다.
새로운 1차원 배열을 arr이라 할 때, arr[left], arr[left+1], ..., arr[right]만 남기고 나머지는 지웁니다.
정수 n, left, right가 매개변수로 주어집니다. 주어진 과정대로 만들어진 1차원 배열을 return 하도록 solution 함수를 완성해 주세요.

& 제한 사항

1 ≤ n ≤ 10⁷
0 ≤ left ≤ right < n²
right - left < 10⁵

처음 풀이

• 처음 풀이는 2차원 배열을 만들어서 행과 열의 index 값을 비교해 큰 값에 +1을 하면 각 요소의 값이 되는 규칙을 찾아서 아래와 같이 만들었습니다.

(1) n차원 배열 정의
(2) 이중 반복문을 사용해 각 요소에 숫자 부여
(3) 1차원 배열로 합체
(4) slice를 사용해서 정답 도출

그러나 아래의 코드로 실행한 결과, 시간 초과 결과를 받았습니다.

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

  let result = [];
  // 1. n으로 n차원 배열 정의
  for (let i = 0; i < n; i++) {
    result.push(new Array(n).fill(0));
  }

  // 각 요소들 비교 시작
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      result[i][j];
      let x = Math.max(i, j);
      if (x === 0) {
        result[i][j] = 1;
      } else {
        result[i][j] = x + 1;
      }
    }
  }

  // 배열을 1차원 배열로 합체
  result.forEach((item, index) => {
    answer = [...answer, ...item];
  });

  // left, right 자르기
  answer = answer.slice(left, right + 1);

  return answer;
}

---

다른 방법으로 해결

그래서 2차원 배열을 만드는 방식이 아닌, 한 번의 반복문으로 left index 값부터 right index 값까지만 돌며 답을 도출하는 방법으로 해결했습니다.

• 위에서 발견한 행과 열 중 큰 숫자 +1이라는 규칙을 이용해서 순서대로 배열에 추가할 수 있는 방법으로 변경해 문제를 해결할 수 있었습니다.

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

  // 시작점
  let y = Math.floor(left / n);
  // 마지막 지점
  let x = left % n;
  for (let i = 0; i <= right - left; i++) {
    answer.push(Math.max(x, y) + 1);
    if (x + 1 < n) {
      x++;
    } else {
      y++;
      x = 0;
    }
  }
  return answer;
}

결론 및 느낀 점

• 이번 문제에서는 프로그래머스에서 제공해 준 예시 애니메이션이 함정이었습니다.
• 예시대로 순차적으로 풀었더니 시간 초과가 났고, 규칙을 찾아 해결하는 방법이 맞았습니다.
• 다른 사람들의 후기들도 대부분 저와 같은 실수를 했고, 이후에 문제를 해결한 것을 알 수 있었습니다.
• 예시에 속아 넘어가면 안 되고, 문제의 의도를 좀 더 정확히 파악할 필요가 있을 것 같습니다.