[프로그래머스] 표 편집 Java (2021 카카오 채용연계형 인턴십)

문제 링크

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

코딩테스트 연습 - 표 편집

 

문제 요약

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

위 그림에서 파란색으로 칠해진 칸은 현재 선택된 행을 나타냅니다. 단, 한 번에 한 행만 선택할 수 있으며, 표의 범위(0행 ~ 마지막 행)를 벗어날 수 없습니다. 이때, 다음과 같은 명령어를 이용하여 표를 편집합니다.

• "U X": 현재 선택된 행에서 X칸 위에 있는 행을 선택합니다.
• "D X": 현재 선택된 행에서 X칸 아래에 있는 행을 선택합니다.
• "C" : 현재 선택된 행을 삭제한 후, 바로 아래 행을 선택합니다. 단, 삭제된 행이 가장 마지막 행인 경우 바로 윗 행을 선택합니다.
• "Z" : 가장 최근에 삭제된 행을 원래대로 복구합니다. 단, 현재 선택된 행은 바뀌지 않습니다.

예를 들어 위 표에서 "D 2"를 수행할 경우 아래 그림의 왼쪽처럼 4행이 선택되며, "C"를 수행하면 선택된 행을 삭제하고, 바로 아래 행이었던 "네오"가 적힌 행을 선택합니다(4행이 삭제되면서 아래 있던 행들이 하나씩 밀려 올라오고, 수정된 표에서 다시 4행을 선택하는 것과 동일합니다).

다음으로 "U 3"을 수행한 다음 "C"를 수행한 후의 표 상태는 아래 그림과 같습니다.

다음으로 "D 4"를 수행한 다음 "C"를 수행한 후의 표 상태는 아래 그림과 같습니다. 5행이 표의 마지막 행 이므로, 이 경우 바로 윗 행을 선택하는 점에 주의합니다.

다음으로 "U 2"를 수행하면 현재 선택된 행은 2행이 됩니다.

위 상태에서 "Z"를 수행할 경우 가장 최근에 제거된 "라이언"이 적힌 행이 원래대로 복구됩니다.

다시한번 "Z"를 수행하면 그 다음으로 최근에 제거된 "콘"이 적힌 행이 원래대로 복구됩니다. 이때, 현재 선택된 행은 바뀌지 않는 점에 주의하세요.

이때, 최종 표의 상태와 처음 주어진 표의 상태를 비교하여 삭제되지 않은 행은 "O", 삭제된 행은 "X"로 표시하면 다음과 같습니다.

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

 

입력

제한사항

• 5 ≤ n ≤ 1,000,000
• 0 ≤ k < n
• 1 ≤ cmd의 원소 개수 ≤ 200,000
  • cmd의 각 원소는 "U X", "D X", "C", "Z" 중 하나입니다.
  • X는 1 이상 300,000 이하인 자연수이며 0으로 시작하지 않습니다.
  • X가 나타내는 자연수에 ',' 는 주어지지 않습니다. 예를 들어 123,456의 경우 123456으로 주어집니다.
  • cmd에 등장하는 모든 X들의 값을 합친 결과가 1,000,000 이하인 경우만 입력으로 주어집니다.
  • 표의 모든 행을 제거하여, 행이 하나도 남지 않는 경우는 입력으로 주어지지 않습니다.
  • 본문에서 각 행이 제거되고 복구되는 과정을 보다 자연스럽게 보이기 위해 "이름" 열을 사용하였으나, "이름"열의 내용이 실제 문제를 푸는 과정에 필요하지는 않습니다. "이름"열에는 서로 다른 이름들이 중복없이 채워져 있다고 가정하고 문제를 해결해 주세요.
• 표의 범위를 벗어나는 이동은 입력으로 주어지지 않습니다.
• 원래대로 복구할 행이 없을 때(즉, 삭제된 행이 없을 때) "Z"가 명령어로 주어지는 경우는 없습니다.

 

출력

정답은 표의 0행부터 n - 1행까지에 해당되는 O, X를 순서대로 이어붙인 문자열 형태로 return 해주세요.

 

접근법

많은 분들이 연결 리스트를 사용해서 구현을 하신 것 같은데, boolean 배열로 구현을 했다. 이런 아이디어도 있다는 걸 공유하는 느낌으로 포스팅한다.

사실 효율성 테스트만 아니면 이 문제는 단순 구현문제라고 봐도 무방하다. 삭제를 취소하는 것도 그냥 stack만 이용하면 간단히 구현할 수 있기 때문. 따라서 이 문제의 핵심은 최적화에 있다고 볼 수 있다.

이 문제의 핵심은 다음 3가지 정도라고 생각한다.

1. 문제에 나와있는 것 처럼 "이름"과 같은 데이터가 존재하지 않고, 행 번호의 개념만 존재하기 때문에 연결 리스트가 아닌 행의 삭제 여부를 표시할 수 있는 boolean 배열로 쉽게 구현이 가능하다.
2. 연결 리스트를 사용하지 않는 이상은 삭제는 실제로 어떤 오브젝트나 원소를 삭제하는 것이 아니다. 구현 방식에 따라 다르긴 하겠지만, 어떤 식으로든 해당 원소가 삭제되었다는 표시만 해주고, 실제로 삭제하지는 않는다. 실제로 삭제하는 경우, 삭제를 취소할 때 해당 원소를 삽입하는 데 O(N)이 소요되기 떄문.
3. 2번의 내용에 의해, 커서(가리키는 행)를 움직이는 데 오버헤드가 생긴다. 이를 해결하기 위해 연속된 커서 이동(중간에 C나 Z 명령이 없는 연속된 U와 D 명령)이 존재하는 경우 하나의 U 혹은 D 명령어로 합쳐준다.

사실 연결리스트로 구현한 뒤 실제로 원소를 삭제하는 경우와 비교했을 때 뭐가 더 빠른지 잘 모르긴 하다. 내 구현 방식은 커서 이동에 오버헤드가 생기고, 연결리스트의 경우에는 실행 취소에서 오버헤드가 생기기 떄문. 트레이드 오프가 있는 부분이 다른 구현 방식이다.

 

2022-04-15 추가
연결리스트와 boolean 배열 구현 방식의 시간 복잡도 차이가 Big-O notation 상으로는 차이가 없는 것으로 보인다.
연속된 U와 D를 합쳐주는 과정을 거치면, 삭제와 실행 취소 명령은 연속되게 올 수 있지만, U나 D 명령은 반드시 앞뒤로 삭제나 실행취소 명령이 존재해야 하므로, (U와 D 명령어의 총 개수) <= (삭제, 실행 취소 명령의 개수의 총 개수) 라는 식이 성립한다.
따라서 실행 취소 명령의 개수가 U와 D 명령어의 총 개수와 비슷한 경우에는 연결 리스트 구현과 boolean 배열 구현의 시간 복잡도 차이가 크지 않을 것으로 예상된다.
대략적인 추측이기 때문에 혹시 다른 의견이 있으시면 댓글로 남겨주시면 감사하겠다.

 

boolean 배열을 활용한 구현 방식은 커서 이동에 오버헤드가 크기 때문에, 반드시 연속된 커서 이동(중간에 C나 Z 명령이 없는 연속된 U와 D 명령)이 존재하는 경우 하나의 U 혹은 D 명령어로 합쳐주는 작업을 거쳐야 한다. 이 작업을 하지 않으면 효율성 테스트 뒷부분에서 시간초과가 뜬다.

 

시간 복잡도

한번의 삭제와 커서 이동에서 worst case의 경우 O(N)이 필요하다.

단 실행 취소는 O(1)이다.

 

공간 복잡도

주어진 입력 + n 크기의 boolean 배열 + 압축된 명령어 배열

 

풀면서 놓쳤던 점

딱히 없다.

 

이 문제에서 얻어갈 점

이중 연결 리스트의 활용(나는 사용 안했지만)

 

코드

import java.util.*;

class Solution {
    
    int lastRowIdx;
    
    public String solution(int numOfRows, int startRow, String[] cmd) {
        
		//U와 D 명령어가 연속적으로 있는 경우 하나로 압축해준다.
		//동시에 String[] 형태의 명령어를 ArrayList<Command>로 바꿔준다.
        ArrayList<Command> commands = compressCmd(cmd);
        
		//문제에 언급된 것처럼 "이름"과 같은 실제 데이터가 존재하지 않기 때문에
		//행의 삭제 여부만 알면 됨. 따라서 행의 삭제 여부를 true/false로 표현가능한
		//boolean 배열을 사용했다.
        boolean[] rows = new boolean[numOfRows];
        Arrays.fill(rows, true); //true = 삭제되지 않음
        
		//삭제된 행의 index를 push할 stack
        Stack<Integer> deletedRows = new Stack<>();
        
        int rowIdx = startRow;

		//맨 마지막 행을 삭제하는 경우에는 커서가 위로 올라가기 때문에
		//지워지지 않은 맨 마지막 행의 index를 저장하고 있어야 한다.
        lastRowIdx = rows.length - 1;
        
        for (Command command : commands)
        {
            if (command.type == 'C')
                rowIdx = deleteRow(rows, rowIdx, deletedRows);
            else if (command.type == 'Z')
                undoDeleteRow(rows, deletedRows);
            else if (command.type == 'U')
                rowIdx = moveUpCursor(rows, rowIdx, command.val);
            else
                rowIdx = moveDownCursor(rows, rowIdx, command.val);
        }
        
        StringBuilder answer = new StringBuilder();
        
        for (boolean row : rows)
        {
            if (row)
                answer.append('O');
            else
                answer.append('X');
        }
        
        return answer.toString();
    }
    
    int moveUpCursor(boolean[] rows, int rowIdx, int val)
    {
        int moveCnt = 0;
        
		//삭제된 행은 이동 횟수에서 제외해야한다
        while (moveCnt < val)
            if (rows[--rowIdx])
                moveCnt++;
        
        return rowIdx;
    }
    
    int moveDownCursor(boolean[] rows, int rowIdx, int val)
    {
        int moveCnt = 0;
        
		//삭제된 행은 이동 횟수에서 제외해야한다
        while (moveCnt < val)
            if (rows[++rowIdx])
                moveCnt++;
        
        return rowIdx;
    }
    
    void undoDeleteRow(boolean[] rows, Stack<Integer> deletedRows)
    {
        int deletedRowIdx = deletedRows.pop(); //가장 최근에 지워진 row의 index
        
        rows[deletedRowIdx] = true;
        
		//복구된 row가 가장 마지막 row라면 lastRowIdx가 갱신된다.
        lastRowIdx = Math.max(lastRowIdx, deletedRowIdx);
    }
    
    int deleteRow(boolean[] rows, int rowIdx, Stack<Integer> deletedRows)
    {
        rows[rowIdx] = false;
        deletedRows.push(rowIdx); //'Z' 명령어를 위해 stack에 넣어준다
        
		//지운 row가 마지막 row인 경우 index가 삭제되지 않은 바로 위 row를 가리킴
        if (rowIdx == lastRowIdx)
        {
            while (!rows[rowIdx])
                rowIdx--;
            lastRowIdx = rowIdx; //마지막 row가 지워졌으므로 갱신
        }
		//지운 row가 마지막 row가 아닌 경우 index는 삭제되지 않은 바로 아래 row를 가리킴
        else
            while (!rows[rowIdx])
                rowIdx++;
        
        return rowIdx;
    }
    
    ArrayList<Command> compressCmd(String[] cmd)
    {
        ArrayList<Command> commands = new ArrayList<>();
        
        int idx = 0;
        while (idx < cmd.length)
        {
            if (cmd[idx].charAt(0) == 'C' || cmd[idx].charAt(0) == 'Z')
            {
                commands.add(new Command(cmd[idx].charAt(0)));
                idx++;
            }
			//연속된 U와 D를 압축. 이 작업 안해주면 효율성 테스트 뒷부분 시간초과 뜸.
            else
                idx = CompressSequentialUAndD(commands, cmd, idx);
        }
        
        return commands;
    }
    
    int CompressSequentialUAndD(ArrayList<Command> commands, String[] cmd, int idx)
    {
        int val = 0;
        char type;
        
        while (idx < cmd.length)
        {
            type = cmd[idx].charAt(0);
            
            if (type == 'U')
                val += Integer.parseInt(cmd[idx].substring(2));
            else if (type == 'D')
                val -= Integer.parseInt(cmd[idx].substring(2));
            else
                break;
            
            idx++;
        }
        
        if (val > 0)
            commands.add(new Command('U', val));
        else if (val < 0)
            commands.add(new Command('D', -val));
        
        return idx;
    }
}

class Command
{
    char type;
    int val;
    
    Command (char type, int val)
    {
        this.type = type;
        this.val = val;
    }
    
    Command (char type)
    {
        this.type = type;
    }
}