[백준] 2469 사다리 타기 (Javascript)

잭슨·2024년 5월 30일

구현 백준 알고리즘 자바스크립트

알고리즘 문제 풀이

목록 보기

95/130

문제

BOJ2469_사다리 타기

풀이

요구사항

사다리 타기의 출발 순서와 도착 순서를 알고 있고 하나의 행이 가려져 있을 때, 가려진 행을 맞추는 문제다.

해결방안

우리는 출발 순서와 도착순서를 알고있다.

const start = Array.from(Array(k), (_, i) => String.fromCodePoint(65 + i));
const finish = expected.map((e) => e);

출발 순서는 start라는 배열에 저장하고, 도착 순서는 finish 라는 배열에 저장한다.

let hiddenIdx = 0;
for (let i = 0; i < n; i++) {
    if (ladder[i][0] === '?') {
        hiddenIdx = i;
        break;
    }
}

그리고 감춰진 행의 인덱스를 구한다.

for (let i = 0; i < hiddenIdx; i++) {
    for (let j = 0; j < k; j++) {
        if (ladder[i][j] === '-') {
            [start[j], start[j + 1]] = [start[j + 1], start[j]];
        }
    }
}

for (let i = n - 1; i > hiddenIdx; i--) {
    for (let j = 0; j < k; j++) {
        if (ladder[i][j] === '-') {
            [finish[j], finish[j + 1]] = [finish[j + 1], finish[j]];
        }
    }
}

0 ~ hiddenIdx-1 까지 1씩 증가시키며 각각의 행의 사다리를 확인한다. 만약 사다리[i][j] === '-' 라면 start[j]는 오른쪽으로 이동해야되고, start[j+1]은 왼쪽으로 이동해야 하기 때문에 이 둘을 서로 스왑해준다.
즉, 위에서부터 hiddenIdx-1까지 사다리를 타고 내려온다.

그리고 finish는 n ~ hiddenIdx+1 까지 1씩 감소시키며
마찬가지로 사다리[i][j] === '-' 일 경우 스왑해준다. 즉, 밑에서부터 hiddenIdx+1까지 사다리를 타고 올라간다.

let answer = '';
for (let i = 0; i < k - 1; i++) {
    if (start[i] === finish[i]) {
        answer += '*';
    } else if (start[i] === finish[i + 1] && start[i + 1] === finish[i]) {
        answer += '-';
        [start[i], start[i + 1]] = [start[i + 1], start[i]];
    } else {
        answer = 'x'.repeat(k - 1);
        break;
    }
}

이제 start와 finish의 동일한 인덱스에 있는 알파벳을 비교하여 만약 동일한 인덱스의 동일한 알파벳이 있다면 그대로 일자로 내려오면 되기 때문에 *을 추가해주고, 그렇지 않고 만약 start[i] === finish[i + 1] && start[i + 1] === finish[i] 라면 즉, 교차했을 때 알파벳이 같다면 start를 교차시켜주고 -를 추가해준다.

만약 두 조건중 하나도 포함되지 않는다면 감추어진 행을 어떻게 구해도 원하는 순서를 얻을 수 없기 때문에 x를 k-1개 만큼 채운다.

전체 코드

const filePath = process.platform === 'linux' ? '/dev/stdin' : './Javascript/input.txt';
const input = require('fs').readFileSync(filePath).toString().trim().split('\n');
const k = +input[0];
const n = +input[1];
const expected = input[2].trimEnd().split('');
const ladder = input.slice(3, 3 + n).map((e) => e.trimEnd().split(''));

// 가로 줄 두 개가 연속으로 붙는 경우는 없다.
// 1. 길이 k의 start, finish 배열 생성
// 2. 가려진 행이 i라고 했을때, start는 0 ~ i-1 까지 1씩 증가, finish는 n-1 ~ i+1 까지 1씩 감소
// 3. ladder[j] === '-'라면 swap([j],[j+1])

let hiddenIdx = 0;
for (let i = 0; i < n; i++) {
    if (ladder[i][0] === '?') {
        hiddenIdx = i;
        break;
    }
}

const start = Array.from(Array(k), (_, i) => String.fromCodePoint(65 + i));
const finish = expected.map((e) => e);

for (let i = 0; i < hiddenIdx; i++) {
    for (let j = 0; j < k; j++) {
        if (ladder[i][j] === '-') {
            [start[j], start[j + 1]] = [start[j + 1], start[j]];
        }
    }
}

for (let i = n - 1; i > hiddenIdx; i--) {
    for (let j = 0; j < k; j++) {
        if (ladder[i][j] === '-') {
            [finish[j], finish[j + 1]] = [finish[j + 1], finish[j]];
        }
    }
}

let answer = '';
for (let i = 0; i < k - 1; i++) {
    if (start[i] === finish[i]) {
        answer += '*';
    } else if (start[i] === finish[i + 1] && start[i + 1] === finish[i]) {
        answer += '-';
        [start[i], start[i + 1]] = [start[i + 1], start[i]];
    } else {
        answer = 'x'.repeat(k - 1);
        break;
    }
}

console.log(answer);