프로그래머스 level 3 ) 표 편집

하우르·2021년 7월 17일

링크: 프로그래머스 level 3 ) 표 편집

문제

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

처음 표의 행 개수를 나타내는 정수 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 해주세요.

정확성 테스트 케이스 제한 사항

5 ≤ n ≤ 1,000

1 ≤ cmd의 원소 개수 ≤ 1,000

풀이

처음 코테에서 풀었는데 그때는 ListIterator로 풀려고 시도했다.
그때 에러때문에 못풀었던거 같다.
다시 보니 현재 위치만 저장해주고 stack으로 Z기능을 완성하면 될거 같았다.

import java.util.LinkedList;
import java.util.Stack;
class Solution {
   public String solution(int n, int k, String[] cmd) {
    String answer = "";
		Stack<Integer> order = new Stack<Integer>();
		Stack<Integer> index = new Stack<Integer>();
		LinkedList<Integer> graph = new LinkedList<>();
		for(int i=0; i<n; i++)
			graph.add(i);
		for(int i=0; i<cmd.length; i++) {
			char c = cmd[i].charAt(0);
			if(c=='D')
				k+=Integer.parseInt(cmd[i].substring(2));
			else if(c=='U')
				k-=Integer.parseInt(cmd[i].substring(2));
			else if(c=='C') {
				order.add(k);
				index.add(graph.get(k));
				graph.remove(k);
				if(k==graph.size())
					k--;
			}
			else if(c=='Z') {
				graph.add(order.peek(), index.pop());
				if(order.pop()<=k)
					k++;
			}
			//System.out.println(k);
		}
		int temp_index=0;
		for(int i=0; i<n; i++)
		{
			if(i==graph.get(temp_index)) {
				answer+="O";
				temp_index++;
			}
			else
				answer+="X";
		}
       return answer;
   }
}

결과

응~ 시간초과
정확성도 3개 정도 런타임에러가 있다.

런타임에러 잡기
시간초과 잡기

시간초과가 나는 이유는 LinkedList때문인거 같다.
LinkedList의 remove와 add는 시간 복잡도가 O(1)인데
실제로 탐색때는 처음부터 탐색해서 삭제할곳을 찾기 때문에
O(n)이 시간 복잡도이다.

푸는 방법을 달리 해야한다.

다른 분 거를 참고했다.
놀랍게도 LinkedList 사용 안해도됨ㅋㅋㅋㅋㅋ
아주 놀라운 풀이였다

import java.util.LinkedList;
import java.util.Stack;
class Solution {
    public String solution(int n, int k, String[] cmd) {
        Stack<Integer> remove_order = new Stack<Integer>();
        int table_size = n;
        for(int i=0; i<cmd.length; i++) {
            char c = cmd[i].charAt(0);
            if(c=='D')
                k+=Integer.parseInt(cmd[i].substring(2));
            else if(c=='U')
                k-=Integer.parseInt(cmd[i].substring(2));
            else if(c=='C') {
                remove_order.add(k);
                table_size--;
                if(k==table_size)
                    k--;
            }
            else if(c=='Z') {
                if(remove_order.pop()<=k)
                    k++;
                table_size++;
            }
        }
        StringBuilder builder = new StringBuilder();
        for(int i=0; i<table_size; i++)
            builder.append("O");
        while(!remove_order.isEmpty())
            builder.insert(remove_order.pop().intValue(), "X");
        String answer=builder.toString();
        return answer;
    }
}