[프로그래머스] 표 편집(java)

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

프로그래머스

처음 보자마자 생각난 방법은 링크드 리스트였다.

아마 정석적인 풀이 방법이 링크드 리스트라고 생각한다.

하지만 이 문제는 StringBuilder를 사용하면 쉽게 풀 수 있다.

 

 

핵심

StringBuilder의 함수를 잘 사용하면 매우 쉽게 풀 수 있다.

 

정답 코드

import java.util.Stack;

class Solution {
    public String solution(int n, int k, String[] cmd) {
        Stack<Integer> remove = new Stack<>();
        int size = n;

        for (String s : cmd) {
            char c = s.charAt(0);
            if (c == 'D') {
                k += Integer.parseInt(s.substring(2));
            }
            if (c == 'U') {
                k -= Integer.parseInt(s.substring(2));
            }
            if (c == 'C') {
                remove.add(k);
                size--;
                if (k == size) {
                    k--;
                }
            }
            if (c == 'Z') {
                if (remove.pop() <= k) {
                    k++;
                }
                size++;
            }
        }

        StringBuilder result = new StringBuilder();

        result.append("O".repeat(size));

        while (!remove.isEmpty()) {
            result.insert(remove.pop(), "X");
        }

        return result.toString();
    }
}

풀이

단순 구현이라고 생각할 수 있다.

D와 U의 경우 단순하게 현재 위치 k를 움직이면 된다.

C도 단순히 삭제를 하는 것인데, 복구 시에 최근 삭제를 복구해야 하기에 stack을 사용하였다.

만약 k가 사이즈와 동일할 경우 위치를 위로 올린다.

 

결과는 StringBuilder를 사용하여 쉽게 만들 수 있다.

O의 개수는 어차피 size만큼만 있기에 우선 채워준다.

이후 remove에 있는 값들을 꺼내어 해당 위치에 X를 넣어준다.

 

 

배운 점

분명 문제를 쉽게 풀 수 있을 것이라 생각했다.

링크드 리스트 말고는 다른 방법은 없는지 고민하다. 시간복잡도 측면을 생각하였다.

이후 StringBuiler를 사용해도 괜찮을 것 같다는 판단을 하였다.

복잡한 알고리즘을 사용하여 푸는 것도 좋지만, 쉽게 풀 수 있는 아이디어가 더욱 중요하다고 생각한다.