표 편집

문제

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

코드

import java.util.*;

class Solution {

    class Node{
        int idx;
        Node prev;
        Node next;
        public Node(int idx, Node prev, Node next){
            this.idx = idx;
            this.prev = prev;
            this.next = next;
        }
    }

    public String solution(int n, int k, String[] cmd) {
        String answer = "";
        StringBuilder sb = new StringBuilder("O".repeat(n));
        Stack<Node> q = new Stack<>();
        Node head = null;
        Node tail = null;
        Node cur = null;

        for(int i=0; i<n; i++){
            if(i == 0){
                head = new Node(i, null, null);
                cur = head;
            }else if(i == n-1){
                cur.next = new Node(i, cur, null);
                cur.next.prev = cur;
                cur = cur.next;
                tail = cur;
            }else{
                cur.next = new Node(i, cur, null);
                cur.next.prev = cur;
                cur = cur.next;
            }
        }

        cur = head;
        for(int i=0; i<k; i++)
            cur = cur.next;

        for(String str : cmd){
            String[] cmds = str.split(" ");
            if(cmds[0].equals("U")){
                int offset = Integer.valueOf(cmds[1]);
                for(int i=0; i<offset; i++)
                    cur = cur.prev;
            }else if(cmds[0].equals("D")){
                int offset = Integer.valueOf(cmds[1]);
                for(int i=0; i<offset; i++){
                    cur = cur.next;
                }
            }else if(cmds[0].equals("C")){
                sb.setCharAt(cur.idx, 'X');
                q.push(cur);
                if(cur.next != null)
                    cur.next.prev = cur.prev;
                if(cur.prev != null)
                    cur.prev.next = cur.next;
                if(cur.next == null)
                    cur = cur.prev;
                else
                    cur = cur.next;
            }else if(cmds[0].equals("Z")){
                Node tmp = q.peek();
                sb.setCharAt(tmp.idx, 'O');
                q.pop();
                if(tmp.prev != null)
                    tmp.prev.next = tmp;
                if(tmp.next != null)
                    tmp.next.prev = tmp;
            }
        }

        return sb.toString();
    }
}

피드백

• 분류와 같이, 2021 카카오 하계 채용형 인턴 문제이다. 난 그리고 다 푼적이 있어서 걍 쉽게 생각하고 접근을 했다.
• 큰 풀이는 링크드리스트와 스택을 사용하는 것이다. 이건 그냥함
• 근데 TLE가 남.
  • answer을 만들때 check를 확인해서 'O' 또는 'X'를 더하기 때문
  • 근데 생각을 해보면, java는 리터럴에 대해서 새로운 리터럴이 생기면 새로운 문자열을 저장하게 된다.
  • 그러면 복사를 하고 더하고 복사를 하고 더하고 하면... O(N^2) 가 나올 수도 있다는 생각이 든다.
• 이에 대한 해답은 StringBuilder였다.
  • 진정한 문자열 배열마냥 사용이 가능, 각 자리수에 접근하여 수정하는 시간복잡도가 O(1), 새로운 문자열을 만들지도 않는다.
• 우리 StringBuilder를 많이 애용하자.

출처

https://moonsbeen.tistory.com/294