경사로
📚 문제 설명
N * N 크기의 지도가 주어지고 각각의 위치의 높이가 주어진다.
나에게는 높이 1, 길이 L의 발판이 갯수는 무제한으로 있다.
- 발판은 겹칠 수 없다.
- 발판은 평평한 곳에만 설치할 수 있다.
- 발판은 L의 길이의 땅이 있어야 설치할 수 있다.
- 길은 가로 새로 길만 존재한다. (아래 그림 참고)
- 가로 새로 겹치는 부분에 중복으로 발판을 놓는 경우는 고려하지 않는다. (가로, 새로 각각 별도로 계산해도 괜찮다.)
발판이 있을 때만 높이가 다른 곳으로 갈 수 있다고 할 때, N * N 의 지도에서 지나갈 수 있는 길의 갯수를 구하여라.
👨🏻💻 풀이 과정
가로 새로를 각각 별도로 보고 발판을 따로따로 고려한다면 생각보다 간단하다.
1차원 배열을 보고 발판을 두고 지나갈 수 있는지 확인하는 함수만 만들면 된다.
예를 들어
N = 3, L = 2
1 1 1
1 1 2
2 3 4위와 같이 입력이 들어왔을 때 가로 새로 각각 1차원 배열로 [1, 1, 1], [1, 1, 2], [2, 3, 4], [1, 1, 2], [1, 1, 3], [1,2,4] 각각 함수에 넣어서 확인한 후 갯수만 카운팅하면 된다.
💡1차원 배열 검사 함수
1차원 배열을 읽고 검사하는 함수의 전체적인 로직은 다음과 같다.
- 이전 위치 저장.
- 현재까지 길이 저장.
- 반복문으로 다음위치 확인.
- 높이가 2이상 -> 종료 (false 리턴).
- 평지
- 길이 증가.
- 오르막길
- 발판을 놓지 못함 -> 종료 (false 리턴).
- 발판을 놓음 -> 위치 갱신, 길이 갱신.
- 내리막길
- L만큼 앞에 놓을 수 있는지 확인.
- 발판을 놓음 -> i를 변경하여 발판 다음 위치를 확인하도록 수정, 위치 갱신, 길이 갱신.
- 발판을 놓지 못함 -> 종료 (false 리턴).
const check = (arr, n) => {
let answer = true;
// 이전 위치의 높이
let prev = arr[0];
// 이전 위치의 길이
let len = 1;
for (let i = 1; i < n; i++) {
// 높낮이 2이상은 제거.
if (Math.abs(prev - arr[i]) > 1) {
answer = false;
break;
}
// 평지
if (prev === arr[i]) {
len++;
continue;
}
// 오르막길
if (prev < arr[i]) {
if (len < L) { //발판을 놓지 못함.
answer = false;
break;
} else { // 발판을 놓음.
prev = arr[i]; // 위치 갱신.
len = 1;
}
}
// 내리막길
if (prev > arr[i]) {
let flag = true;
// 발판을 놓을 수 있는지 체크.
for (let j = 1; j < L; j++) {
if (arr[i] !== arr[i + j]) {
flag = false;
}
}
// 발판을 놓으면 i 값을 변경.
if (flag) {
prev = arr[i + L - 1];
i = i + L - 1;
len = 0;
} else {
answer = false;
break;
}
}
}
return answer;
};이제 전체 지도를 읽고 1차원 배열을 하나씩 check(arr, n) 함수에 전달하여 결과만 카운팅하면 된다.
💡solution(main) 함수
const solution = () => {
let answer = 0;
const rowArr = board[0].map((_, index) => {
return board.map(v => v[index]);
});
board.forEach(v => {
if (check(v, N)) {
answer++;
}
});
rowArr.forEach(v => {
if (check(v, N)) {
answer++;
}
});
console.log(answer);
};💡전체 코드
let input = require("fs").readFileSync(0, 'utf-8').toString().trim().split("\n");
const [N, L] = input.shift().split(' ').map(Number);
const board = input.map(v => v.split(' ').map(Number));
const check = (arr, n) => {
let answer = true;
// 이전 위치의 높이
let prev = arr[0];
// 이전 위치의 길이
let len = 1;
for (let i = 1; i < n; i++) {
// 높낮이 2이상은 제거.
if (Math.abs(prev - arr[i]) > 1) {
answer = false;
break;
}
// 평지
if (prev === arr[i]) {
len++;
continue;
}
// 오르막길
if (prev < arr[i]) {
if (len < L) { //발판을 놓지 못함.
answer = false;
break;
} else { // 발판을 놓음.
prev = arr[i]; // 위치 갱신.
len = 1;
}
}
// 내리막길
if (prev > arr[i]) {
let flag = true;
// 발판을 놓을 수 있는지 체크.
for (let j = 1; j < L; j++) {
if (arr[i] !== arr[i + j]) {
flag = false;
}
}
// 발판을 놓으면 i 값을 변경.
if (flag) {
prev = arr[i + L - 1];
i = i + L - 1;
len = 0;
} else {
answer = false;
break;
}
}
}
return answer;
};
const solution = () => {
let answer = 0;
const rowArr = board[0].map((_, index) => {
return board.map(v => v[index]);
});
board.forEach(v => {
if (check(v, N)) {
answer++;
}
});
rowArr.forEach(v => {
if (check(v, N)) {
answer++;
}
});
console.log(answer);
};
solution();🧐 후기
오랜만에 구현 문제들을 풀고 있는데 생각보다 놓치는 반례들이 많아서 고생하고 있다.
그리고 디버깅 기능을 최대한 많이 사용하려고 하는데 그냥 콘솔을 찍는 것보다 더 좋은 것 같다.
JavaScript를 사용하는 모두를 위해...