[Softeer] lv2. [21년 재직자 대회 예선] 전광판 / Javascript

[21년 재직자 대회 예선] 전광판

 

1. 문제

문제가 길어서 패스 아래 url 참고

https://softeer.ai/practice/6268

Softeer - 현대자동차그룹 SW인재확보플랫폼

 

2. 언어별 시간/메모리

3. 풀이

const readline = require('readline');

const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout
});

function symmetricDifference(setA, setB) {
    const result = new Set(setA);

    setB.forEach(elem => {
        if (result.has(elem)) {
            result.delete(elem)
        } else {
            result.add(elem)
        }
    })

    return result;
}

const METRIC = {
    '0': new Set([0,1,2,4,5,6]),
    '1': new Set([2,5]),
    '2': new Set([0,2,3,4,6]),
    '3': new Set([0,2,3,5,6]),
    '4': new Set([1,2,3,5]),
    '5': new Set([0,1,3,5,6]),
    '6': new Set([0,1,3,4,5,6]),
    '7': new Set([0,1,2,5]),
    '8': new Set([0,1,2,3,4,5,6]),
    '9': new Set([0,1,2,3,5,6]),
};

const emptySet = new Set([]);
let T = 0;
let caseList = [];

rl.on('line', (line) => {
    // 첫번째줄 처리
    if (T === 0) {
        T = Number(line)
    } else {
        // '1 2' 받아서 처리
        caseList.push(line.split(' ')); // ['1', '2'];

        if (T === caseList.length) {
            rl.close();
        }
    }
});

rl.on('close', () => {
    caseList.forEach(testCase => {
        let result = 0;
        const [a, b] = testCase; // a = '9881' b = '10724'
        // // 비교해야되는 최대 count
        const n = Math.max(a.length, b.length)

        // reverse 처리 (1의 자리부터 비교해야 됨)
        const reversedA = [...a].reverse(); // [1,8,8,9]
        const reversedB = [...b].reverse(); // [4,2,7,0,1]

        for(let i=0; i<n; i++) {
            // 예외 한쪽 자리수가 없을 때
            const A = reversedA[i] === undefined ? emptySet : METRIC[reversedA[i]]
            const B = reversedB[i] === undefined ? emptySet : METRIC[reversedB[i]]

            result += symmetricDifference(A, B).size;
        }
        
        console.log(result);
    });
});

 

핵심 아이디어

1. 0~9의 숫자는 각각의 매트릭을 가지고 있음. 이를 배열 형태의 상수로 미리 정의함

2. A -> B로 변경시 필요한 처리: A와 B의 공통된 부분을 빼면 됨

3. Set 자료 구조를 사용해서 symmetricDifference 메서드를 사용하려고 했음. 하지만 동작하지 않음 mdn 찾아보니 Node 22부터 지원됨. Softeer은 12.22.12 버전 사용중(25.4.24 기준) -> symmetricDifference를 직접 구현함 (set 자료구조의 has, add, delete 메소드가 있어서 쉽게 구현할 수 있었음)

 

symmetricDifference

symmetricDifference 브라우저 호환성

 

 

4. 시간복잡도

O(T*D)

 

- T: 테스트 케이스 개수 (최대 1,000개)

- D: 각 숫자의 최대 자리수(최대 5)

 

→ 따라서 최악의 경우에도 O(1000 * 5) = O(5000)

 

Set을 쓰는게 최선인가?

지금처럼 Set을 쓰는 이유는:

• symmetricDifference 같은 집합 연산이 필요하고
• 비교 대상의 크기(세그먼트 수)가 7개로 고정되어 있음

즉, 메모리 효율보다는 코드의 단순성과 논리적 명확함이 더 중요하기 때문에, Set 선택은 합리적이라고 생각. 메모리 차이도 사실상 무시할 수 있을 만큼 미미할 정도의 트레이트 오프라고 생각됨