낚시왕
📚 문제 설명
R * C 크기의 격자에 물고기가 있고 낚시 왕은 이 격자 가장 왼쪽보다 한칸 왼쪽에 있다.
이 격자에서 1초 동안 아래와 같은 과정이 순서대로 일어난다고 한다.
- 낚시왕이 오른쪽으로 한칸 이동.
- 낚시왕이 있는 열에서 가장 가까운 물고기를 잡음.
- 물고기 이동.
물고기가 이동할 때는 물고기가 바라보는 방향 ( 1: 상, 2: 하, 3: 우, 4: 좌 )로 s 의 속도로 간다.
격자 끝에 만나면 물고기는 반대 방향으로 이동한다.
같은 위치에 물고기가 2마리 이상 있다면, 가장 큰 물고기가 나머지를 잡아먹는다.
👨🏻💻 풀이 과정
이 문제를 읽고 가장 먼저 생각이 났던 방법은
- 2중 for문을 이용해 격자에 직접 체크를 하는 방식.
Map()을 이용해 상어만 따로 저장하여 확인하는 방식.
이렇게 2가지 이다.
이 2가지 방법 중 한 풀이에서 문제가 발생했는데 이 문제가 최근에 다른 문제를 풀면서도 또 발생하게 되었고 그 원인을 기록하고자 한다.
💡1차 제출 코드 (Map 사용)
Map()을 사용하는 풀이는 간략하게 말하면 다음과 같다.
Shark변수를Map()으로 선언.- Key로
"X좌표,Y좌표", Value로{speed: ?, dir: ?, size: ?}를 사용. - 낚시꾼이 낚아가면
Map.prototype.delete()을 이용해 제거,answer변수에size를 더해줌. - 상어가 이동하면 새로운
new Map()인NextSharkMap에 담는다. - 모든 상어 이동 후
NextSharkMap을Shark에 부여. - 위 과정 반복.
전체적인 풀이는 위의 과정을 구현하면 완료되는데 한가지 생각할 것이 있다.
만약 speed 값이 한바퀴를 돌아서 다시 내 자리에 온다면, 그 전까지 진행했던 과정은 불필요해진다.
따라서 방향에 따라 speed % ( 2 * ( 가로 or 세로 - 1 ) ) 를 진행하고
이 결과만큼만 이동하면 된다.
만약 이 과정을 넣지 않으면 시간 초과가 발생하니 꼭 넣어야 한다.
전체 코드
let input = require("fs").readFileSync(0, 'utf-8').toString().trim().split("\n");
const [N, M, S] = input.shift().split(' ').map(Number);
const sharks = input.map(v => v.split(' ').map(Number));
//d가 1인 경우는 위, 2인 경우는 아래, 3인 경우는 오른쪽, 4인 경우는 왼쪽
// Map 변수 선언
let Shark = new Map();
// 초기값 부여.
for (const [x, y, speed, dir, size] of sharks) {
Shark.set(`${x - 1},${y - 1}`, {speed:speed, dir:dir, size: size})
}
// 상어가 움직일 때
const SharkMove = (SharkMap) => {
// 다음 위치의 상어를 저장할 변수.
const NextSharkMap = new Map();
const directions = [[-1, 0], [1, 0], [0, 1], [0, -1]];
// 상어 각각의 위치 계산.
SharkMap.forEach((value, key) => {
// 현재 위치
let [x, y] = key.split(',').map(Number);
let {speed, dir, size} = value;
// 앞으로 이동할 방향.
let [dx, dy] = directions[dir - 1];
// 한바퀴를 돌아서 제자리면 계산할 필요 X
// 이부분 필수 !!! (넣지 않으면 시간 초과)
let remainingSpeed = dir <= 2 ? speed % (2 * (N - 1)) : speed % (2 * (M - 1));
// 이동.
while (remainingSpeed--) {
// 만약 끝부분이면 방향 전환.
if (dir === 1 && x === 0 || dir === 2 && x === N - 1) {
dir = dir === 1 ? 2 : 1;
} else if (dir === 3 && y === M - 1 || dir === 4 && y === 0) {
dir = dir === 3 ? 4 : 3;
}
// 다음 이동 방향 갱신.
[dx, dy] = directions[dir - 1];
// 위치 변경.
x += dx;
y += dy;
}
// 상어가 같은 위치에 2마리 이상이면 사이즈가 큰놈만 남긴다.
if (NextSharkMap.has(`${x},${y}`)) {
if (NextSharkMap.get(`${x},${y}`).size < size) {
NextSharkMap.set(`${x},${y}`, {speed, dir, size});
}
} else {
NextSharkMap.set(`${x},${y}`, {speed, dir, size});
}
});
return NextSharkMap;
};
const main = () => {
let answer = 0;
for (let i = 0; i < M; i++) {
for (let j = 0; j < N; j++) {
// 같은 열에 상어가 있는지 확인.
if (Shark.has(`${j},${i}`)) {
answer += Shark.get(`${j},${i}`).size;
Shark.delete(`${j},${i}`);
break;
}
}
// 상어 이동.
Shark = SharkMove(Shark);
}
console.log(answer);
};
main();
위의 풀이대로 제출을 하면 이제 Map()을 이용한 풀이의 문제점을 볼 수 있다.
체점 현황에서 다른 사람들의 풀이 시간을 확인하면 3300이 넘는 속도는 무언가 잘못되었다고 생각할 수 있다.
💡2차 제출 코드
앞선 Map()을 이용한 풀이의 문제점을 파악하기 위해 우선 가장 처음 생각했던 2중 for문을 이용한 풀이를 진행해보자.
2중 for문을 이용한 풀이는 Map()을 이용한 풀이보다 훨씬 더 직관적으로 풀면 된다.
- 낚시왕이 있는 열에 반복문 실행.
- 상어 제거, 물고기 무게 저장.
- 2중 for문을 돌며 상어를 확인.
NextMap에 1초 후 상어의 위치를 넣어줌.- 1초 후,
NextMap에 저장된 값을 현재 지도인map에 넣어줌. - 위의 과정 반복.
전체 풀이
let fs = require("fs");
let input = fs.readFileSync("./input.text").toString().trim().split("\n");
// let input = require("fs").readFileSync(0, 'utf-8').toString().trim().split("\n");const [N, M, S] = input.shift().split(' ').map(Number);
const [N, M, S] = input.shift().split(' ').map(Number);
const sharks = input.map(v => v.split(' ').map(Number));
//d가 1인 경우는 위, 2인 경우는 아래, 3인 경우는 오른쪽, 4인 경우는 왼쪽
let map = Array.from({length: N}, _ => Array.from({length: M}, _ => 0));
for (const [x, y, speed, dir, size] of sharks) {
map[x - 1][y - 1] = [speed, dir, size];
}
let answer = 0;
// 상어 이동
const SharkMove = (inputMap) => {
let NextMap = Array.from({length: N}, _ => Array.from({length: M}, _ => 0));
const directions = [[-1, 0], [1, 0], [0, 1], [0, -1]];
for (let i = 0; i < N; i++) {
for (let j = 0; j < M; j++) {
if (inputMap[i][j] !== 0) {
let [SPEED, DIR, SIZE] = inputMap[i][j];
let nextX = i;
let nextY = j;
let remainingSpeed = DIR <= 2 ? SPEED % (2 * (N - 1)) : SPEED % (2 * (M - 1));
let cnt = 0;
while (remainingSpeed > cnt) {
if (DIR === 1 && nextX === 0 || DIR === 2 && nextX === N - 1) {
DIR = DIR === 1 ? 2 : 1;
}
else if (DIR === 3 && nextY === M - 1 || DIR === 4 && nextY === 0) {
DIR = DIR === 3 ? 4 : 3;
}
nextX += directions[DIR - 1][0];
nextY += directions[DIR - 1][1];
cnt++;
}
if (NextMap[nextX][nextY] !== 0) {
if (NextMap[nextX][nextY][2] < SIZE) {
NextMap[nextX][nextY] = [SPEED, DIR, SIZE];
}
} else {
NextMap[nextX][nextY] = [SPEED, DIR, SIZE];
}
}
}
}
return NextMap;
};
// 낚시꾼 이동
for (let i = 0; i < M; i++) {
//열에서 가장 가까운 상어
for (let j = 0; j < N; j++) {
if (map[j][i] !== 0) {
answer += map[j][i][2];
map[j][i] = 0;
break;
}
}
map = SharkMove(map);
}
console.log(answer);
아래 보이는 Map() 사용 풀이보다 확실히 시간이 줄어든 것을 볼 수 있다.
가운데 시간 초과는 SPEED 값을
speed % ( 2 * ( 가로 or 세로 - 1 ) )로 계산하지 않아서 발생.
🧐 후기
풀이를 고민하다가 Map을 이용해 상어의 위치만 저장한 후에 이를 이용하면 더 좋을 것 같다고 생각해서 그렇게 진행했는데 생각보다 오히려 비효율적이라서 당황했던 문제였다. 정확하게 오버헤드 때문에 시간차이가 이렇게 발생한다고 말 할 수는 없지만 Map 구조를 이용해서 발생하는 여러 오버헤드 때문에 시간차이가 발생한다고 추측하고 있다.
