[코딩테스트합격자되기-자바편] 문제14. 표 편집

💡 해당 풀이는 코딩 테스트 합격자되기 - 자바편 에서 발췌된 내용을 바탕으로 작성되었습니다.

 

문제

출처: 프로그래머스 - 표 편집

 

내용

 

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

 

행 번호	이름
0	무지
1	콘
2	어피치
3	제이지
4	프로도
5	네오
6	튜브
7	라이언

 

위 표에서 헤더를 제외하고 볼드 처리된 칸은 현재 선택된 행을 나타냅니다. 한 번에 한 행만 선택할 수 있으며 표의 범위를 벗어날 수 없습니다. 이때 다음과 같은 명령어를 이용하여 표를 편집합니다.

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

 

 

예를 들어 위 표에서 "D 2"를 수행할 경우 아래 표처럼 4행이 선택되며

 

행 번호	이름
0	무지
1	콘
2	어피치
3	제이지
4	프로도
5	네오
6	튜브
7	라이언

 

 

"C"를 수행하면 선택된 행을 삭제하고 바로 아래 행이었던 "네오"가 적힌 행을 선택합니다.

 

행 번호	이름
0	무지
1	콘
2	어피치
3	제이지
4	네오
5	튜브
6	라이언

 

 

 

다시 "U 3"을 수행한 다음 "C"를 수행한 후의 표 상태는 아래와 같습니다.

 

행 번호	이름
0	무지
1	어피치
2	제이지
3	네오
4	튜브
5	라이언

 

 

 

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

 

행 번호	이름
0	무지
1	어피치
2	제이지
3	네오
4	튜브

 

 

 

"Z"를 수행하면 가장 최근에 제거했던 "라이언"행이 복구됩니다.

 

행 번호	이름
0	무지
1	어피치
2	제이지
3	네오
4	튜브
5	라이언

 

 

현재 선택된 행은 바뀌지 않는 점에 주의하세요.

처음 표의 행 개수를 나타내는 정수 n, 처음에 선택된 행의 위치를 나타내는 정수 k, 수행한 명령어들이 담긴 문자열 배열 cmd가 매개변수로 주어질 때, 모든 명령어를 수행한 후 표의 상태와 처음 주어진 표의 상태를 비교하여 삭제되지 않은 행은 O, 삭제된 행은 X로 표시하여 문자열 형태로 반환하도록 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를 순서대로 이어붙인 문자열 형태로 반환해주세요.

 

정확성 테스트 케이스 제한 조건

• 정확성 테스트: 10초
• 5 ≤ n ≤ 1,000
• 1 ≤ cmd의 원소 개수 ≤ 1,000

효율성 테스트 케이스 제한 조건

• 효율성 테스트: 언어별로 작성되 정다 코드의 실행 시간의 적정 배수
• 주어진 조건 외 추가 제한사항 없습니다.

 

 

기록하기

💡 어디까지 생각해봤는지 단계적으로 기록해봅니다.

어떤 알고리즘을 적용하려 했나요?

적용 근거는 무엇인가요?

삭제 동작에 대하여 undo 가 존재하므로 최근 삭제한 행을 저장할 스택이 필요합니다.

 

문제 풀이 과정에서 해당 알고리즘을 어떻게 코드로 구현하려 했나요?

1. n 의 개수만큼 인덱스를 값으로 가지는 배열 생성
2. cmd Map 생성 필요
3. 최근 선택된 행을 담는 변수 생성
4. 스택 생성
5. 스택에는 없어진 index 담기
6. 최종적으론 스택에 담긴 index를 가져와서 문자열 치환

 

풀이

풀이 시간

 

시작 시각	종료 시각	총 소요 시간
21:22	22:30	- (failed)

 

문제 분석

 

제약 사항 파악 & 테스트 케이스 작성

 

• 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를 순서대로 이어붙인 문자열 형태로 반환해주세요.

 

 

입력값 분석

💡 입력값을 분석하면 문제에서 요구하는 알고리즘의 시간 복잡도를 간접적으로 파악할 수 있습니다.

n	k	cmd	result
8	2	["D 2", "C", "U3", "C", "D 4", "C", "U 2", "Z", "Z"]	"OOOOXOOO"
8	2	["D 2", "C", "U 3", "C", "D 4", "C", "U 2", "Z", "Z", "U 1", "C"]	"OOXOXOOO"

 

 

의사 코드 작성

💡 의사 코드는 동작 중심으로 작성하는 것이 중요합니다.

💡 의사 코드는 문제 해결 순서로 작성합니다.

💡 의사 코드를 충분히 테스트해봅니다.

solution(n, k, cmd) {
    // n개 만큼 인덱스를 값으로 가지는 배열 생성
    int[] array = new int[n];
    // LinkedList 생성
    LinkedList<Integer> list = new Linkedist<>();
    for (int i = 0; i < array.length; i++) {
        array[i] = i;
        list.add(i);
    }

    // cmd Map 생성
    HashMap cmdMap
    // map 에 U, D put

    // 최근 선택된 행을 담는 변수 생성
    int seletcted = k;

    // 스택 생성
    Stack<Integer> deleted

    // cmd 해석 및 적용
    for (String s: cmd) {
        // 0 번 명령어
        // U or D 일 경우 선택된 행 있음
            // 2 번 선택된 행
        // C 일 경우
            // deleted 에 push
        // Z 일 경우 && deleted 가 비어있지 않을 경우
            // deleted 에서 pop
    }

    // answer는 StringBuilder 이용하기
    for (int a : array) {
        if (deleted.contains(a)) {
            // add "O" to answer
        } else {
            // add "X" to answer
        }
    }
    return answer;
}

 

 

구현

 

 

failed

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Stack;

class Solution {
    public String solution(int n, int k, String[] cmd) {
        // 1 2 3 5 7 8 9  - 6 0 4
        // n개 만큼 인덱스를 값으로 가지는 배열 생성
        int[] array = new int[n];
        // LinkedList 생성
        LinkedList<Integer> linkedList = new LinkedList<>();
        for (int i = 0; i < array.length; i++) {
            array[i] = i;
            linkedList.add(i);
        }

        // cmd Map 생성
        HashMap<Character, Integer> cmdMap = new HashMap<>();
        // map 에 U, D put
        cmdMap.put('U', -1);
        cmdMap.put('D', 1);

        // 최근 선택된 행을 담는 변수 생성
        int selected = k;

        // 스택 생성
        Stack<Integer> deleted = new Stack<>();

        // cmd 해석 및 적용
        for (String s: cmd) {
            // 0 번 명령어
            char c = s.charAt(0);

            if (cmdMap.containsKey(c)) {
                // U or D 일 경우 선택된 행 있음
                // 2 번 선택된 행
                char i = s.charAt(2);
                selected += Math.max(0, Math.min(n - 1, Integer.valueOf(i) * cmdMap.get(c)));
            } else {
                if (c == 'C') {
                    // C 일 경우
                    // deleted 에 push
                    int value = linkedList.get(k);
                    deleted.push(value);
                    linkedList.remove(k);
                    selected = Math.min(selected, linkedList.size() - 1);
                } else if (c == 'D' && !deleted.isEmpty()) {
                    // Z 일 경우 && deleted 가 비어있지 않을 경우
                    // deleted 에서 pop
                    int undo = deleted.pop();
                    if (linkedList.size() - 1 < undo) {
                        linkedList.addLast(undo);
                    } else {
                        linkedList.add(array[k], k);
                    }

                }    
            }
        }
        System.out.println(linkedList);
        System.out.println(deleted);

        // answer는 StringBuilder 이용하기
        StringBuilder sb = new StringBuilder();
        for (int a: array) {
            if (deleted.contains(a)) {
                // add "X" to answer
                sb.append("X");
            } else {
                // add "O" to answer
                sb.append("O");
            }
        }
        return sb.toString();
    }
}

 

복기하기

저자 권장 시간	권장 시간 복잡도
80분	O(N)

 

답안과 나의 풀이를 비교해보세요

import java.util.Arrays;
import java.util.Stack;

class Solution {
    public String solution(int n, int k, String[] cmd) {
        // 삭제된 행의 인덱스를 저장하는 스택 생성
        Stack<Integer> deleted = new Stack<>();

        // 배열을 그대로 사용
        // 각 행을 기준으로 연산에 따른 위치를 표시하기 위한 배열
        int[] up = new int[n + 2];
        int[] down = new int[n + 2];

        for (int i = 0; i < n + 2; i++) {
            up[i] = i - 1;
            down[i] =i + 1;
        }

        // 현재 위치
        k++;



        // cmd 해석 및 적용
        for (String c: cmd) {
            if (c.startsWith("C")) {
                // 현재 위치 삭제
                deleted.push(k);
                up[down[k]] = up[k];
                down[up[k]] = down[k];
                // 그 다음 위치로 이동
                k = n < down[k] ? up[k] : down[k];
            } else if (c.startsWith("Z")) {
                // 가장 최근에 삭제된 행 보완
                int restore = deleted.pop();
                down[up[restore]] = restore;
                up[down[restore]] = restore;
            } else {
                // 현재 위치 이동
                String[] s = c.split(" ");
                int x = Integer.parseInt(s[1]);
                for (int i = 0; i < x; i++) {
                    k = s[0].equals("U") ? up[k] : down[k];
                }
            }
        }

        // OX 표시
        char[] answer = new char[n];
        Arrays.fill(answer, 'O');

        for (int i : deleted) {
            answer[i - 1] = 'X';
        }

        return new String(answer);
    }
}

 

 

배열을 그대로 사용합니다.

• 상대적 위치를 이용합니다.
  • up은 -1부터, down은 1부터
    • 0번째의 위는 없기 때문에 -1
    • 0번째의 아래는 1이기 때문에 1
    • 1의 아래는 2 => down[1] == 2
    • 1의 위는 0 => up[1] == 0

 

삭제 시

• k의 아래(down)에 있는 행의 윗 부분(up)은 k의 윗부분(up)이 되어야 합니다.
  • up[down[k]] = up[k]
• k의 위(up)에 있는 행의 아랫부분(down)은 k의 아랫부분(down)이 되어야 합니다.
  • down[up[k]] = down[k]

 

 

복원 시

• 행 번호 restore를 기준으로 윗 행(up)의 다음(down)은 restore가 되어야 합니다.
  • down[up[restore]] = restore
• 행 번호 restore를 기준으로아래 행(down)의 이전(up)은 restore가 되어야 합니다.
  • up[down[restore]] = restore

 

요약하기

• 난이도 🌕🌕🌕🌕🌕🌕🌕🌕🌕🌕🌕🌕🌕🌕🌕