문제
가로와 세로의 길이가 같은 2차원 배열의 크기 n이 주어졌을 때 각각의 배열은 1행 1열 부터 시작해 i행 i열까지 영역 내의 모든 빈칸의 숫자를 i로 채운다.
const array = [
[1, 2, 3],
[2, 2, 3],
[3, 3, 3],
];
위와 같은 배열이 만들어 졌을 때 1차원의 배열로 변환하여 left ~ right 인덱스 사이의 모든 수를 배열로 반환해야 한다.
문제 해결
코딩 문제를 풀때 손코딩 또한 중요하다. 손 코딩으로 간단한 케이스를 적어보면 위의 left, right가 가지는 의미를 새롭게 정의 할 수 있다.
2차원 배열의 값을 1차원으로 변환했을때 우리가 탐색해야 할 부분은 상당 부분 좁혀진다. 위의 문제를 인덱스 0부터 시작하여 탐색할 경우 탐색에 많은 시간이 필요하다. 이를 줄이기 위해서 특정 부분만 탐색할 수 있도록 시작 부분과 끝부분을 조정하자는 것이다.
start = Math.floor(left / n)
시작 부분은 전체 배열의 크기 길이가 정해져 있고 또한 1차원의 배열로 전환 했을 경우를 상정하여야 하기 때문에 성립된다. start는 탐색이 필요한 부분의 row 값을 의미한다.end = Math.floor(right / n)
이 또한 위와 같은 이유로 성립이 되며 마지막으로 탐색해야 할 값이 있어야 할 row 값에 해당한다.이를 적용하여 해결하면 아래와 같다.
function solution(n, left, right) {
let answer = [];
let start = Math.floor(left / n);
let end = Math.floor(right / n);
let count = start * n;
for (let i = start; i <= end; i += 1) {
let fillNum = i + 1;
for (let j = 0; j < n; j += 1) {
if (j > i) {
fillNum += 1;
}
count += 1;
if (left < count && count <= right + 1) {
answer.push(fillNum);
} else if (count > right + 1) {
break;
}
}
}
return answer;
}
하지만 시작 부분과 끝 부분을 나누지 않고 문제를 해결도 가능하다. left와 right가 2차원 배열에 어디에 해당하는지 알기 위해서 필요한 정보는 가로열과 세로열의 좌표이다.
row = Math.floor(i / n)
만약 구하고자 하는 left가 2이고 n이 3이라고 가정하면 left가 2차원 배열에서 해당하는 row 값은 0이 될 것이다.col = Math.floor(i % n)
구하고자 하는 right 값이 5이고 n이 3일 경우 right 값이 2차원 내에서 해당하는 col 값은 2가 될 것이다.이와 같은 방법을 이용하면
right-left의 값 만큼만 배열을 반복하여 순환하면 되기 때문에 실행 시간을 더 단축 시킬 수 있기 때문에 유용한 방법이다.maxInRow = Math.max(row, col)
위의 조건일 경우 각 (col, row)의 값은 row와 col 중 최대값에 해당하는 값이다.function solution(n, left, right) {
let answer = [];
for (let i = left; i <= right; i++) {
const row = Math.floor(i / n);
const col = i % n;
const maxInRow = Math.max(row, col);
answer.push(maxInRow + 1);
}
return answer;
}
이번 문제에서 얻은 것
손 코딩이 중요하다! 손으로 내가 생각한 내용을 최대한 간단한 케이스로 전환하여 테스트 해보는 것을 잊지 말자.