[programmers/js] 표 편집

표 편집

https://school.programmers.co.kr/learn/courses/30/lessons/81303

문제 설명

업무용 소프트웨어를 개발하는 니니즈웍스의 인턴인 앙몬드는 명령어 기반으로 표의 행을 선택, 삭제, 복구하는 프로그램을 작성하는 과제를 맡았습니다. 세부 요구 사항은 다음과 같습니다.

세부 요구 사항

• 한 번에 한 행만 선택할 수 있으며, 표의 범위(0행 ~ 마지막 행)를 벗어날 수 없습니다.
• 이때, 다음과 같은 명령어를 이용하여 표를 편집합니다.
  "U X": 현재 선택된 행에서 X칸 위에 있는 행을 선택합니다.
  "D X": 현재 선택된 행에서 X칸 아래에 있는 행을 선택합니다.
  "C" : 현재 선택된 행을 삭제한 후, 바로 아래 행을 선택합니다. 단, 삭제된 행이 가장 마지막 행인 경우 바로 윗 행을 선택합니다.
  "Z" : 가장 최근에 삭제된 행을 원래대로 복구합니다. 단, 현재 선택된 행은 바뀌지 않습니다.

처음 표의 행 개수를 나타내는 정수 n, 처음에 선택된 행의 위치를 나타내는 정수 k, 수행한 명령어들이 담긴 문자열 배열 cmd가 매개변수로 주어질 때, 모든 명령어를 수행한 후 표의 상태와 처음 주어진 표의 상태를 비교하여 삭제되지 않은 행은 O, 삭제된 행은 X로 표시하여 문자열 형태로 return 하도록 solution 함수를 완성해주세요.

풀이

처음에는 splice와 index를 직접 계산해 문제를 풀었는데, 효율성 및 점수에서 통과하지 못했습니다.

찾아본 결과 연결 링크드 리스트 문제로 이를 알 수 있는 조건들을 확인해보면,

1. 빈번한 중간 삽입/삭제가 많음
2. 위아래 이동

를 통해 연결 리스트 문제임을 확인 가능합니다.

function solution(n, k, cmd) {
    const prev = Array(n).fill().map((_, i) => i - 1);
    const next = Array(n).fill().map((_, i) => i + 1);
    next[n - 1] = -1;
    const st = []; // C로 제거된 값
    let cur = k;
    
    cmd.forEach((command) => {
        const [c, value] = command.split(" ");
        
        if (c === "U") {
            for (let i = 0; i < Number(value); i++) cur = prev[cur];
        } else if (c === "D") {
            for (let i = 0; i < Number(value); i++) cur = next[cur];
        } else if (c === "C") {
            st.push(cur);
            if (prev[cur] !== -1) next[prev[cur]] = next[cur];
            if (next[cur] !== -1) prev[next[cur]] = prev[cur];
            cur = next[cur] === -1 ? prev[cur] : next[cur];
        } else if (c === 'Z') {
            const restore = st.pop();
            if (prev[restore] !== -1) next[prev[restore]] = restore;
            if (next[restore] !== -1) prev[next[restore]] = restore;
        }
    });
    
    const result = Array(n).fill('O');
    st.forEach((v) => (result[v] = 'X'));
    return result.join('');
}