[백준] 17281_⚾ (Javascript)

문제

BOJ17281_⚾

코드

const filePath = process.platform === 'linux' ? '/dev/stdin' : './Javascript/input.txt';
const input = require('fs').readFileSync(filePath).toString().trim().split('\n');
const N = +input[0];
const arr = input.slice(1).map((e) => e.split(' ').map(Number));
const visited = Array(9).fill(false);
let answer = 0;
permutation([]);
console.log(answer);

// 모든 조합 확인 O(n!)
function permutation(players) {
    if (players.length === 9) play([...players]); // 타순이 정해진 경우
    else if (players.length === 3) permutation([...players, 0]); // 1번 선수는 4번 타자로 항상 고정
    else {
        // 1번 선수 제외하고 순회
        for (let i = 1; i <= 8; i++) {
            if (!visited[i]) {
                visited[i] = true;
                permutation([...players, i]);
                visited[i] = false;
            }
        }
    }
}

// 현재 타순으로 몇 득점을 낼 수 있는지 확인
function play(battingOrderList) {
    let score = 0;
    let order = 0;

    for (let i = 0; i < N; i++) {
        const inning = arr[i];
        let out = 0;
        let base1 = 0;
        let base2 = 0;
        let base3 = 0;

        while (out < 3) {
            const result = inning[battingOrderList[order++ % 9]];

            if (result === 0) out++;
            else if (result === 1) {
                score += base3;
                base3 = base2;
                base2 = base1;
                base1 = 1;
            } else if (result === 2) {
                score += base3 + base2;
                base3 = base1;
                base2 = 1;
                base1 = 0;
            } else if (result === 3) {
                score += base3 + base2 + base1;
                base3 = 1;
                base2 = base1 = 0;
            } else if (result === 4) {
                score += base3 + base2 + base1 + 1;
                base3 = base2 = base1 = 0;
            }
        }
    }
    answer = Math.max(answer, score);
}

시간복잡도

이 문제는 모든 순열을 구해서 선수들의 타순을 구한 뒤 각 타순으로 낼 수 있는 득점을 계산하여 가장 큰 득점일 때의 점수를 출력해야 한다.

선수들의 수를 n이라고 했을 때 순열을 구하는 알고리즘의 시간 복잡도는 $O(n!)$ 이다. 선수들의 수는 9명이고 1번 선수는 항상 4번 타자로 고정이니 1번 선수를 제외하면 $O(8!)$ 이다.

그리고 하나의 순열이 완성될 때 마다 해당 순열로 모든 이닝을 확인한다. 이닝 수는 최대 50이고, 각 이닝마다 아웃이 3번 나올 때까지 또다시 반복문을 수행한다.

각 이닝에는 최소한 하나의 아웃이 있다고 문제에 나와있으므로 최악의 경우 27(9*3)번 반복한다.

따라서 최악의 경우 연산 횟수는 대략 $8!\times50\times27=54,432,000$ 정도일 것으로 예상되므로 통과할 수 있다.

풀이

이 문제는 크게 '모든 타순 조합 구하기' 부분과 '현재 타순 조합으로 낼 수 있는 득점 계산' 부분으로 나눌 수 있다.

우선 재귀를 통해 모든 타순 조합을 만들어 줘야한다.

만약 9명의 타순이 정해졌다면, play 함수를 실행시키고 인자로 현재 타순을 넘겨준다.

if (players.length === 9) play([...players]);

play 함수에서는 인자로 전달받은 타순으로 모든 이닝을 종료했을 때 득점이 얼마나 되는지 확인하고 만약 answer 변수에 저장되어 있는 값보다 크다면 최댓값을 갱신해준다.

play 함수의 내부를 더 자세히 살펴보자면, order 변수는 처음에만 0으로 초기화 하고 모든 이닝을 수행하는 동안 계속해서 1씩 증가한다. 이는 현재 이닝이 종료될 때의 타순을 다음 이닝에서도 유지해가기 위함이다.

그리고 result 변수는 battingOrderList 의 타순으로 현재 inning 에서 order번 째 선수가 안타를 칠지, 1루타, 2루타를 칠지, 홈런을 칠지, 아웃을 당할지에 대한 정보가 저장되고, result 값에 따라 base1, base2, base3 에 대한 정보와 득점이 달라진다.