Softeer [Level 3] [한양대 HCPC 2023] Phi Squared {언어 : JavaScript}

문제 링크

https://softeer.ai/practice/7697

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

정답 코드

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

const inputData = [];

rl.on("line", (line) => {
    inputData.push(line.split(" "));
}).on("close", () => {
    const solution = (dq) => {
        let stack = [];
        let si = -1;
        let di = 0;
        while (dq.length > 1) {
            // 만약 di가 dq.length와 같다면 dq는 이미 다 순회한 것이므로 초기화한다.
            if (di === dq.length) {
                dq = stack;
                si = -1;
                di = 0;
                stack = [];
                continue;
            }
            // 현재 미생물
            const [curIdx, curSize] = dq[di];
            di++; // 바로 인덱스 더해주기
            
            // 더해줄 미생물 크기
            let newSize = curSize;
            
            // 현재 미생물이 첫 번째 미생물인 경우
            if (di === 1) {
                const [nextIdx, nextSize] = dq[di];
                // 뒤의 미생물과 비교해서 크면 더해주기
                if (curSize >= nextSize) {
                    newSize += nextSize;
                    // 다음 다음으로 이동하기
                    di++;
                }
                stack.push([curIdx, newSize]);
                si++;
                continue;
            }

            // 앞의 미생물과 비교
            const [prevIdx, prevSize] = stack[si];
            if (curSize >= prevSize) {
                newSize += prevSize;
                stack.pop();
                si--;
            }

            // 뒤의 미생물과 비교
            // 하지만 마지막 미생물이라면 바로 stack에 넣기
            if (di === dq.length) {
                stack.push([curIdx, newSize]);
                continue;
            }

            // 뒤에 올 미생물이 현재 값보다 작은 경우
            const [nextIdx, nextSize] = dq[di];
            if (curSize >= nextSize) {
                newSize += nextSize;
                // 다음 다음으로 이동
                di++;
            }
            
            stack.push([curIdx, newSize]);
            si++;
        }
        const [resIdx, resSize] = dq[0];
        console.log(resSize);
        console.log(resIdx);
    }
    const deque = inputData[1].map((e, idx) => [idx+1, Number(e)]);
    solution(deque);
    process.exit(0);
})

풀이 방법

1. 풀이 방법은 간단하다.
2. dq(미생물 배열: {초기 위치: 숫자, 크기: 숫자})를 처음부터 끝까지 순회한다.
3. 현재 미생물 dq[di]의 크기를 앞 뒤로 비교한다.
   1. 하지만 dq가 맨 앞이라면 뒤에 있는 미생물과 비교한다.
   2. 또 맨 앞이라면 앞에 있는 미생물과 비교한다.
4. 비교한 미생물을 newSize와 함께 stack에 넣는다.
5. 혹시나 di가 dq의 길이와 같아지면 초기화 시켜서 while문을 다시 돌린다.
6. 이 과정을 미생물이 하나 남을 때까지 = 즉, dq.length 가 1이 될 때까지 반복하면 끝!

느낀점

• 처음 코드가 테스트 케이스는 통과하는데 시간초과가 나서 원인을 파악했다.
• 원인은 shift()에 있었다.
• 이론상 n이 2분의 1씩 줄어들기 때문에 O(n)의 시간복잡도를 예상했는데 shift()를 50만번씩 반복했기 때문에 시간초과가 났다.
• 이를 해결하기 위해서 그냥 인덱스로 값을 찾기로 했고 결국 통과할 수 있었다.
• 그리고 여기에 si, di가 나오는데 투 포인터 방식이라고 할 수도 있겠다.

시간초과 코드

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

const inputData = [];
let n = 0;
let deque = [];

rl.on("line", (line) => {
    inputData.push(line.split(" "));
}).on("close", () => {
    // 흡수하는 방식을 deque으로 만든다.
    // 처음 q에서 뺀 다음 앞 뒤로 흡수 할 수 있는 미생물이 있는지 확인한다.
    // 있다면 앞 뒤로 흡수한 다음 (위치, 미생물의 크기)형태로 newQ에 넣는다.
    // 이렇게 마지막 미생물 까지 순회한 뒤 q를 newQ로 치환한다.
    // 이를 q의 길이가 1이 될 때까지 반복한다.
    // 복잡도는 O(n)
    deque = inputData[1].map((e, idx) => [idx+1, Number(e)]);
    while (deque.length > 1) {
        const newQ = [];
        while (deque.length > 0) {
            let [idx, size] = deque.shift();
            let sumSize = 0;
            // 이미 지나간 미생물 합치기
            if (newQ.length > 0) {
                const [prevIdx, prevSize] = newQ[newQ.length-1];
                if (size >= prevSize) {
                    sumSize += prevSize;
                    newQ.pop();
                }
            }
            // 뒤에 나올 미생물 합치기
            if (deque.length > 0) {
                const [nextIdx, nextSize] = deque[0];
                if (size >= nextSize) {
                    sumSize += nextSize;
                    deque.shift();
                }
            }
            // 합쳐서 newQ에 넣기
            newQ.push([idx, size+sumSize]);
        }
        // deque을 newQ로 치환하기
        deque = newQ.map((e) => e);
    }
    const [location, lastSize] = deque[0];
    console.log(lastSize);
    console.log(location);
    process.exit(0);
})