본문 바로가기
개발/알고리즘

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

by ISA(류) 2021. 10. 18.

# 문제 원문

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

  1. n행 n열 크기의 비어있는 2차원 배열을 만듭니다.
  2. i = 1, 2, 3, ..., n에 대해서, 다음 과정을 반복합니다.
    • 1행 1열부터 i행 i열까지의 영역 내의 모든 빈 칸을 숫자 i로 채웁니다.
  3. 1행, 2행, ..., n행을 잘라내어 모두 이어붙인 새로운 1차원 배열을 만듭니다.
  4. 새로운 1차원 배열을 arr이라 할 때, arr[left], arr[left+1], ..., arr[right]만 남기고 나머지는 지웁니다.

정수 n, left, right가 매개변수로 주어집니다. 주어진 과정대로 만들어진 1차원 배열을 return 하도록 solution 함수를 완성해주세요.


제한사항

  • 1 ≤ n ≤ 107
  • 0 ≤ left ≤ right < n2
  • right - left < 105

입출력 예

n / left / right / result

3 2 5 [3,2,2,3]
4 7 14 [4,3,3,3,4,4,4,4]

 

# 문제 풀이

 

생각보다 난이도가 높은 문제이다. 문제에서 설명하는 내용은 실제로 정해진 과정을 거쳐서 만든 결과를 리턴하라고 하지만 그걸 따라 할 경우 통과를 못한다.ㅎㅎ 나름 함정인가. 메모리 사용량 초과로 (signal: aborted (core dumped)) 에러가 나는 테스트케이스가 많기 때문이다. 그래서 배열에 저장 하지 않는 방식으로 필요한 left, right 구간을 바로 구하면 시간 초과가 뜬다. ^ㅁ^...뭐냐? 여기서 대략 멘붕이 한번 오게 되는데 그 left, right사이를 arr를 만들지 않고 바로 규칙에 따라서 구해야한다는 것.. 즉 지문 내용과 다르게 정해진 룰에 따라서 만들어질 left, right 구간에 있을 요소들을 바로 도출해내야 한다는 것이다. 어쨌든 함정 케이스들을 피하면 그렇게 어렵진 않은 문제이다.(솔직히 멘탈을 공격하는게 목적으로 보임)

 

삽질 한 내역은 아래 내 개인 깃허브 레포에서 확인 할 수 있다.

https://github.com/yoonjonglyu/algorithmTestEX/blob/main/programmers/level2/n%5E2%20%EB%B0%B0%EC%97%B4%20%EC%9E%90%EB%A5%B4%EA%B8%B0.js

 

GitHub - yoonjonglyu/algorithmTestEX: algorithm, js

algorithm, js. Contribute to yoonjonglyu/algorithmTestEX development by creating an account on GitHub.

github.com

# 솔루션 플로우

1. 입력 받은 left와 right 사이를 반복한다.

2. idx / n과 idx % n 사이를 비교해서 큰 값에 + 1 해준 값들을 구한다.(rdx보다 낮은 cdx의 경우 rdx로 보정되는 룰)

3. 구해진 result를 반환한다.

1. 반복문을 활용한 풀이

function solution(n, left, right) {
    return [true].reduce((result, _) => {
        for (let idx = left; idx <= right; idx++) {
            result.push(Math.max(idx % n, Math.floor(idx / n)) + 1);
        }
        return result;
    }, []);
}
반응형