야구⚾
📚 문제 설명
N번의 이닝 동안 타자가 공을 친다고 한다.
각각의 이닝에서 타자가 어떻게 칠지 결과를 알고 있다고 할 때, 점수가 최대가 되도록 타순을 정하려고 한다.
이 때 점수의 최댓값을 구하여라.
단, 첫번째 선수가 반드시 4번 타자라고 한다.
👨🏻💻 풀이 과정
처음 타순을 정할 때 1번 타자를 제외한 인원의 결과를 내림차순으로 sort()를 진행하여 타순을 정하려고 했다.
그런데 생각을 해보니 각각의 타자가 어떻게 칠지 각각의 이닝마다 달라지기 때문에
한개의 이닝만 보고 내림차순으로 정렬하면 안된다.
따라서 1번 선수를 4번 타자에 넣고 나머지 모든 경우를 조합해야 한다.
💡조합 (Combination)
조합의 경우 1번부터 9번까지의 선수들을
HitterArr라는 타석에 빈타석에 하나씩 넣는 방식으로 구현했다.
전체 풀이
let fs = require("fs");
let input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");let N = parseInt(input.shift());
// 선수들의 결과.
let Hitter = input.map(v => v.split(' ').map(Number));
// 타석.
let HitterArr = new Array(9).fill(0);
// 타석이 채워져있는지 확인.
let visited = new Array(9).fill(false);
// 최대 점수.
let max = 0;
// 4번 타자는 고정.
visited[3] = true;
HitterArr[3] = 1;
// 조합.
// PlayerNum 1부터 9 까지 지정.
const Combination = (PlayerNum) => {
// 만약 9번까지 모든 타자에게 타석을 정해줬을 경우.
if (PlayerNum === 10) {
// OnGame()으로 점수 계산.
let score = OnGame(HitterArr);
// 최댓값 갱신.
max = max < score ? score : max;
// 재귀 종료.
return;
}
for (let i = 0; i < 9; i++) {
//각각의 타석이 비어있는지 확인.
if (!visited[i]) {
// 타석 채워짐.
visited[i] = true;
// 타석 지정.
HitterArr[i] = PlayerNum;
// 재귀.
Combination(PlayerNum + 1);
// 다음 조합을 위해 타석을 다시 비워둠.
visited[i] = false;
}
}
};
// 1번 선수는 4번 타석에 이미 정해져 있음.
Combination(2);💡게임 진행 함수 (OnGame)
게임 진행의 경우 생각보다 간단하다.
각각의 베이스를 변수로 지정해서 베이스에 선수가 있다면 1, 선수가 없다면 0을 할당했다.
그리고 각각의 결과에 따라 변수를 구조 분해 할당을 이용해 SWAP 해주고
outCnt를 통해 아웃 카운트를 체크하여 3 아웃이면,
init() 함수를 이용해 모든 베이스와 outCnt를 초기화 했다.
const OnGame = (HitterCombination) => {
// 점수, 베이스
let [score, base1, base2, base3] = [0, 0, 0, 0];
// 아웃 카운트
let outCnt = 0;
// 몇번 타석이 나올 차례인지.
let hitter = 0;
// 초기화 함수.
const init = () => {
[ base1, base2, base3, outCnt] = [0, 0, 0, 0];
};
// 각각의 타자가 쳤을 때.
const Hit = (v) => {
if (v === 1) {
[score, base1, base2, base3] = [score + base3, 1, base1, base2];
} else if (v === 2) {
[score, base1, base2, base3] = [score + base2 + base3, 0, 1, base1];
} else if (v === 3) {
[score, base1, base2, base3] = [score + base1 + base2 + base3, 0, 0, 1];
} else if (v === 4) {
[score, base1, base2, base3] = [score + base1 + base2 + base3 + 1, 0, 0, 0];
} else if (v === 0) {
outCnt++;
}
};
// 타석 순서대로 게임 진행.
for (let i = 0; i < N; i++) {
// 아웃 카운트가 3이 될 때까지 진행.
while (outCnt < 3) {
Hit(Hitter[i][HitterCombination[hitter % 9] - 1]);
hitter++;
}
// 아웃 카운트가 3이면 초기화.
if (outCnt === 3) init();
}
return score;
};이제 두 함수를 이용해 결과 값인 max를 출력하면 정답이 될 것이다.
1차 제출 코드(주석X)
let fs = require("fs");
let input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");
let N = parseInt(input.shift());
let Hitter = input.map(v => v.split(' ').map(Number));
let HitterArr = new Array(9).fill(0);
let visited = new Array(9).fill(false);
let max = 0;
visited[3] = true;
HitterArr[3] = 1;
const OnGame = (HitterCombination) => {
let [score, base1, base2, base3] = [0, 0, 0, 0];
let outCnt = 0;
let hitter = 0;
const init = () => {
[ base1, base2, base3, outCnt] = [0, 0, 0, 0];
};
const Hit = (v) => {
if (v === 1) {
[score, base1, base2, base3] = [score + base3, 1, base1, base2];
} else if (v === 2) {
[score, base1, base2, base3] = [score + base2 + base3, 0, 1, base1];
} else if (v === 3) {
[score, base1, base2, base3] = [score + base1 + base2 + base3, 0, 0, 1];
} else if (v === 4) {
[score, base1, base2, base3] = [score + base1 + base2 + base3 + 1, 0, 0, 0];
} else if (v === 0) {
outCnt++;
}
};
for (let i = 0; i < N; i++) {
while (outCnt < 3) {
Hit(Hitter[i][HitterCombination[hitter % 9] - 1]);
hitter++;
}
if (outCnt === 3) init();
}
return score;
};
const Combination = (PlayerNum) => {
if (PlayerNum === 10) {
let score = OnGame(HitterArr);
max = max < score ? score : max;
return;
}
for (let i = 0; i < 9; i++) {
if (!visited[i]) {
visited[i] = true;
HitterArr[i] = PlayerNum;
Combination(PlayerNum + 1);
visited[i] = false;
}
}
};
Combination(2);
console.log(max);
그런데 이렇게 하면 시간 초과가 나게 된다.
다른 풀이를 봐도 전체적인 로직은 다를게 없다.
그래서 질문 게시판을 찾아봤는데 한 글을 발견하게 되었다.
그 글의 핵심은 구조 분해 할당 을 통해 Swap을 하거나 값을 초기화하며 진행할 경우 시간 초과 가 난다는 말이었다.
따라서 OnGame 함수에 있는 모든 구조 분해 할당 부분을 변경하여 다시 제출했다.
2차 제출 코드(주석X)
let fs = require("fs");
let input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");
let N = parseInt(input.shift());
let Hitter = input.map(v => v.split(' ').map(Number));
let HitterArr = new Array(9).fill(0);
let visited = new Array(9).fill(false);
let max = 0;
visited[3] = true;
HitterArr[3] = 1;
const OnGame = (HitterCombination) => {
let base1 = 0;
let base2 = 0;
let base3 = 0;
let outCnt = 0;
let hitter = 0;
let score = 0;
const init = () => {
base1 = 0;
base2 = 0;
base3 = 0;
outCnt = 0;
};
const Hit = (v) => {
if (v === 1) {
score += base3;
base3 = base2;
base2 = base1;
base1 = 1;
} else if (v === 2) {
score += base3 + base2;
base3 = base1;
base2 = 1;
base1 = 0;
} else if (v === 3) {
score += base3 + base2 + base1;
base1 = base2 = 0;
base3 = 1;
} else if (v === 4) {
score += base3 + base2 + base1 + 1;
base1 = base2 = base3 = 0;
} else if (v === 0) {
outCnt++;
}
};
for (let i = 0; i < N; i++) {
while (outCnt < 3) {
Hit(Hitter[i][HitterCombination[hitter % 9] - 1]);
hitter++;
}
if (outCnt === 3) init();
}
return score;
};
const Combination = (PlayerNum) => {
if (PlayerNum === 10) {
let score = OnGame(HitterArr);
max = max < score ? score : max;
return;
}
for (let i = 0; i < 9; i++) {
if (!visited[i]) {
visited[i] = true;
HitterArr[i] = PlayerNum;
Combination(PlayerNum + 1);
visited[i] = false;
}
}
};
Combination(2);
console.log(max);
🧐 후기
전에 최소힙을 구현하는 과정에서 백준은 swap을 할 때 구조 분해 할당을 통해 하는 것보다 tmp 변수를 이용하여 하는것이 시간 복잡도가 더 좋다고 하는 글을 봤었는데 그 때 당시에는 그냥 구조 분해 할당으로 진행해도 문제가 없어서 별 생각 없이 넘겼었다.
그런데 이번 문제를 풀며 구조 분해 할당을 이용하면 시간 초과가 나는 것을 보고 전에 봤던 그 글이 다시 생각나게 되었다.
JavaScript를 사용하는 모두를 위해...