1248 Guess (자바스크립트)

문제

Given a sequence of integers, a1, a2, …, an, we define its sign matrix S such that, for 1 ≤ i ≤ j ≤ n, Sij="+" if ai + … + aj > 0; Sij="−" if ai + … + aj < 0; and Sij="0" otherwise. 

For example, if (a1, a2, a3, a4)=( −1, 5, −4, 2), then its sign matrix S is a 4×4 matrix: 

 12341234

-	+	0	+
	+	+	+
		-	-
			+

We say that the sequence (−1, 5, −4, 2) generates the sign matrix. A sign matrix is valid if it can be generated by a sequence of integers. 

Given a sequence of integers, it is easy to compute its sign matrix. This problem is about the opposite direction: Given a valid sign matrix, find a sequence of integers that generates the sign matrix. Note that two or more different sequences of integers can generate the same sign matrix. For example, the sequence (−2, 5, −3, 1) generates the same sign matrix as the sequence (−1,5, −4,2). 

Write a program that, given a valid sign matrix, can find a sequence of integers that generates the sign matrix. You may assume that every integer in a sequence is between −10 and 10, both inclusive. 

입력

The first line contains an integer n(1 ≤ n ≤ 10), where n is the length of a sequence of integers. The second line contains a string of n(n+1)/2 characters such that the first n characters correspond to the first row of the sign matrix, the next n−1 characters  to the second row, ..., and the last character to the n-th row. 

출력

Output exactly one line containing a sequence of n integers which generates the sign matrix. If more than one sequence generates the sign matrix, you may output any one of them. Every integer in the sequence must be between −10 and 10, both inclusive.

=====

문제 분석

정답으로 출력 될 배열은 n의 길이를 가졌다. 이를 arr로 칭한다.

입력에 주어진 문자열을 통해 gr을 구할 수 있으며 gr[i][j] 는 arr[i] 부터 arr[j]까지 합의 부호를 나타낸다.

const gr = Array.from({ length: n }, () =>
        Array.from({ length: n }, () => ' ')
    );
let c = 0;
for (let i = 0; i < n; i++) {
    for (let j = i; j < n; j++) {
	    gr[i][j] = str[c++];
    }
}

각 인덱스의 숫자는 -10부터 10의 값을 나타나고 있으며 

각 인덱스별로 -10부터 10의 값을 넣어보면서 재귀를 돌린다면 arr를 구할 수 있다. 

이때 첫 인덱스부터 숫자를 넣어보면서 gr의 적혀있는 부호를 통해 알맞은 숫자를 구할 수 있겠지만, 이럴 경우 첫 인덱스부터 끝 인덱스까지 조건에 부합하는지 찾아봐야하고, 그 다음으로는 두번째 인덱스부터 끝 인덱스까지 맞는지 또 구해봐야한다.

이러한 불필요한 연산을 줄이기 위해 마지막 인덱스부터 부합하는 요소들을 찾으며 그 이전 인덱스에 숫자를 넣어보며 찾아봐야한다.

const next = row - 1;
let a = gr[next][next] === '-' ? -1 : 1;

for (let t = 1; t <= 10; t++) {
    const num = t * a;
    let s = num;
    let isSuccess = true;

    for (let col = row; col < n; col++) {
        s += arr[col];

        if (s === 0 && gr[next][col] !== '0') {
            isSuccess = false;
            break;
        }
        if (s > 0 && gr[next][col] !== '+') {
            isSuccess = false;
            break;
        }
        if (s < 0 && gr[next][col] !== '-') {
            isSuccess = false;
            break;
        }
    }
    if (isSuccess) {
        const temp = [...arr];
        temp[next] = num;
        dfs(next, temp);
    }
}

이 로직대로 재귀를 돌린다면 정답이 출력됨.

오답 노트

이러한 로직으로 배열을 구하는데 계속 틀렸길래 문제를 읽어보니 첫번째 인덱스만 0이 아닌 수가 온다는 점을 놓쳐서였다.

정답 코드

const main = (n, str) => {
    const gr = Array.from({ length: n }, () =>
        Array.from({ length: n }, () => ' ')
    );
    let c = 0;
    for (let i = 0; i < n; i++) {
        for (let j = i; j < n; j++) {
            gr[i][j] = str[c++];
        }
    }

    const dfs = (row, arr) => {
        if (row === 0) {
            console.log(arr.join(' '));
            process.exit(0);
        }
        const next = row - 1;

        if (gr[next][next] === '0') {
            let s = 0;
            let isSuccess = true;

            for (let col = row; col < n; col++) {
                s += arr[col];

                if (s === 0 && gr[next][col] !== '0') {
                    isSuccess = false;
                    break;
                }
                if (s > 0 && gr[next][col] !== '+') {
                    isSuccess = false;
                    break;
                }
                if (s < 0 && gr[next][col] !== '-') {
                    isSuccess = false;
                    break;
                }
            }
            if (isSuccess) {
                const temp = [...arr];
                temp[next] = 0;
                dfs(next, temp);
            }

            return;
        }

        let a = gr[next][next] === '-' ? -1 : 1;

        for (let t = 1; t <= 10; t++) {
            const num = t * a;
            let s = num;
            let isSuccess = true;

            for (let col = row; col < n; col++) {
                s += arr[col];

                if (s === 0 && gr[next][col] !== '0') {
                    isSuccess = false;
                    break;
                }
                if (s > 0 && gr[next][col] !== '+') {
                    isSuccess = false;
                    break;
                }
                if (s < 0 && gr[next][col] !== '-') {
                    isSuccess = false;
                    break;
                }
            }
            if (isSuccess) {
                const temp = [...arr];
                temp[next] = num;
                dfs(next, temp);
            }
        }
    };

    if (str.at(-1) === '0') {
        const temp = Array.from({ length: n }, () => -1);
        temp[n - 1] = 0;

        dfs(n - 1, temp);
    } else {
        let aa = str.at(-1) === '-' ? -1 : 1;
        for (let i = 1; i <= 10; i++) {
            const temp = Array.from({ length: n }, () => -1);
            temp[n - 1] = i * aa;

            dfs(n - 1, temp);
        }
    }
};
const input = require('fs')
    .readFileSync(process.platform === 'linux' ? '/dev/stdin' : './input.txt')
    .toString()
    .trim()
    .split('\n');

const n = +input[0];
const gr = input[1].split('');

main(n, gr);