[2021 카카오 채용연계형 인턴십] 표 편집 - 자바

문제 링크 🔗

https://school.programmers.co.kr/learn/courses/30/lessons/81303?language=java

체감 난이도 🤔

상

유형 🗨️

구현, LinkedList, Stack

풀이 방법 📝

• 처음에 실패했던 풀이 방법으로는, ArrayList와 일반 배열을 생성해서 따로 분리해서 진행했었다. 이렇게 구현하니까 테스트 케이스는 다 통과했는데, 정확성과 효율성 테스트에서 통과하지 못했었다.
• 잘 모르겠어서 아래의 링크를 참고해서 풀이를 진행했다.
• [프로그래머스]표 편집 - JAVA
• 해당 풀이는 LinkedList를 이용해서 풀었다.
  • LinkedList는 삽입, 삭제에 대한 시간 복잡도가 O(1)이기 때문에 적합한 타입이다.
• 풀이 코드

import java.util.Stack;

class Node {
    int pointer;
    int prev;
    int next;

    Node(int pointer, int prev, int next) {
        this.pointer = pointer;
        this.prev = prev;
        this.next = next;
    }

    int getPointer() {
        return pointer;
    }

    int getPrev() {
        return prev;
    }

    int getNext() {
        return next;
    }
}
class Table {

    private Stack<Node> nodeStack;

    private StringBuilder result;

    private int pointer;

    private int[] prev;
    private int[] next;

    public Table(int n, int pointer) {
        this.pointer = pointer;
        nodeStack = new Stack<>();
        prev = new int[n];
        next = new int[n];
        result = new StringBuilder("O".repeat(n));

        // LinkedList
        for (int i = 0; i < n; i++) {
            prev[i] = i - 1;
            next[i] = i + 1;
        }
        next[n - 1] = -1;
    }

    // U X
    public void upChoice(int c) {
        while(c -- > 0)
            pointer = prev[pointer];
    }

    // D X
    public void downChoice(int c) {
        while(c -- > 0)
            pointer = next[pointer];
    }

    // C
    public void removeAndBelowChoice() {
        nodeStack.push(new Node(pointer, prev[pointer], next[pointer]));

        if (prev[pointer] != -1)
            next[prev[pointer]] = next[pointer];
        if (next[pointer] != -1)
            prev[next[pointer]] = prev[pointer];

        result.setCharAt(pointer, 'X');

        if (next[pointer] != -1)
            pointer = next[pointer];
        else
            pointer = prev[pointer];
    }

    // Z
    public void repairRecentlyDeleted() {
        Node node = nodeStack.pop();

        if (node.getPrev() != -1)
            next[node.getPrev()] = node.getPointer();

        if (node.getNext() != -1)
            prev[node.getNext()] = node.getPointer();

        result.setCharAt(node.getPointer(), 'O');
    }

    public String toString() {
        return result.toString();
    }
}

public class Main {
    public static String solution(int n, int k, String[] cmd) {
        Table table = new Table(n, k);

        for (String s : cmd) {
            if (s.startsWith("U")) {
                table.upChoice(Integer.parseInt(s.substring(2)));
            } else if (s.startsWith("D")) {
                table.downChoice(Integer.parseInt(s.substring(2)));
            } else if (s.startsWith("C")) {
                table.removeAndBelowChoice();
            } else {
                table.repairRecentlyDeleted();
            }
        }

        return table.toString();
    }
}

새로 알게된 메서드 💡

• Stack push vs add
  • 둘다 기능은 동일하나, add는 boolean 값을 반환하고 push는 E 타입을 반환한다.
  • stack인걸 알려주기 위해 값을 추가할 때는 push를 쓰는 것이 좋아보인다.
• String.repeat(n)
  • 스트링을 반복해서 추가할 수 있는 메서드이다.
• Stack pop vs peek
  • pop는 최상위 값을 뽑고나서 제거하는데, peek은 뽑고나서 제거하지 않는다.

느낀점 ⭐

• LinkedList라고 하면 자바 util 패키지에 정의되어 있는 LinkedList만 생각했는데, 이렇게 직접 구현해서 사용할 수도 있구나라는걸 알았다.
• Character.getNumericValue(char c)를 사용해서 U와 D의 인풋 값을 적용할려고 했는데, 이렇게 하면 10의 자리인 경우는 뒤에가 짤려서 오답이라고 나왔었다.
  • 이는 Integer.parseInt(String.substring(2))를 통해 뒤의 값 까지 잘 받아올 수 있게 처리하였다.