본문 바로가기

Algorithm

백준 1406 에디터 Java

언뜻 봤을 땐 쉬워 보였던 문제이다.

하지만 한 번 틀리고 정답률을 보았을 때 쉽지 않은 문제라는 걸 알게되었다.

 

문제는 간단하다.

문자열이 주어지면 처음엔 커서가 문자열 맨 끝에 있고

 

L :  커서를 한칸 왼쪽으로

D : 커서를 한칸 오른쪽으로

B : 커서 왼쪽에 있는 문자 삭제

P : 다음에 주어지는 문자를 커서 왼쪽에 삽입

 

물론 L이나D의 경우에 커서가 더 이상 갈 곳이 없을 땐 처리해줘야 한다.

 

나는 당연히 문제를 보고 StringBuilder를 이용해서 풀 생각을 했다.

 

처음 틀렸을 당시 내 코드는 이렇다.

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        String s = reader.readLine();
        int n = Integer.parseInt(reader.readLine());
        StringBuilder builder = new StringBuilder(s);
        int cs = s.length();
        
        for(int i=0; i<n; i++) {
            StringTokenizer st = new StringTokenizer(reader.readLine());
            String c = st.nextToken();
            switch(c) {
                case "L":
                    if(cs>0)
                        cs--;
                    break;
                case "D":
                    if(cs!=builder.length())
                        cs++;
                    break;
                case "B":
                    if(cs>0) {
                        builder.delete(cs-1, cs);
                        cs--;
                    }
                    break;
                case "P":
                    builder.insert(cs, st.nextToken());
                    cs++;
                    break;
            }
        }
        System.out.println(builder.toString());
        
    }
 

커서의 위치를 int형 배열로 기억해두고 명령어를 switch문으로 받아서

StringBuilder의 delete(), insert() 메소드를 호출해 처리하는 식의 코드를 작성했다.

 

어렵다는 걸 깨닫고 최백준님의 문제해설을 보았을 때,

내가 얼마나 멍청했는지 깨달을 수 있었다.

 

우선 시간 제한이 0.3초이고 

n은 50만까지 가능하고  문자열 길이는 10만까지 가능하다.

StringBuilder의 delete메소드와 insert메소드는 각각 삭제하고 삽입하고

다시 문자열들을 땡겨오거나 밀어주는데 O(n)일 것이다.

그리고 명령어의 개수인 n만큼 반복문을 또 돌리므로

내가 짠 코드는 O(n^2)일 것이다. n이 50만일때 약 2500억 번 정도 연산을 한다고 보면 될 것 같다.

 

그게 정답일리는 절대 없다.

내가 생각한 코드가 문제에 주어진 조건이랑 되는지 안되는지 생각도 안해보고

문제를 푼것이고 시간을 날린 것이다. 

 

최백준님은 문제 해설은 너무 경이로웠다.

커서를 기준으로 왼쪽 스택과 오른쪽 스택을 생성해서 문제를 푸는 방법을 해설해 주셨다.

 

L :  커서를 한칸 왼쪽으로 -> 왼쪽 스택을 pop해 오른쪽 스택에 push

D : 커서를 한칸 오른쪽으로 -> 오른쪽 스택을 pop해 왼쪽 스택에 push

B : 커서 왼쪽에 있는 문자 삭제 -> 왼쪽 스택 pop

P : 다음에 주어지는 문자를 커서 왼쪽에 삽입 -> 왼쪽 스택 push

 

처음 듣고 놀랐다. 혼자 아무리 고민했어도 저렇게 푸는 방법은 생각하지 못했을 것이다..

이렇게 하면 push와 pop 메소드는 O(1)이기 때문에 명령어의 개수만큼만 반복문이 돌면 된다

따라서 O(n)인 것이다. 문득 떠오르는 출력에 대한 고민은

왼쪽스택을 다 pop해 오른쪽 스택에 push하면 해결된다.

 

여기까지 설명을 듣고 문제를 다시 풀었다.

결과는 또 틀렸다. 디버깅을 열심히 해서 어디서 틀렸는지 찾아냈다.

왼쪽 스택을 다 pop해 오른쪽 스택에 push하는 과정에서 틀린 것이다.

 

1
2
3
4
5
    for(int i=0; i<left.size(); i++//왼쪽 스택을 전부 오른쪽 스택에 push
        right.push(left.pop());
    for(int i=0; i<right.size(); i++//오른쪽 스택을 전부 
        System.out.print(right.pop());
 
 

예전에도 같은 이유로 틀렸었는데 또 같은 실수를 반복했다.

스택의 size를 조건에 넣은 것이 원인이였다.

스택은 pop을 하며 계속 size가 줄어들기 때문에

for문은 애초에 내가 원했던 스택의 사이즈 만큼 돌지 않았던 것이다.

while문으로 고쳐 해결하였다.

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
        public static void main(String[] args) throws IOException {
            BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
            String s = reader.readLine();
            int n = Integer.parseInt(reader.readLine());
            Stack<String> left = new Stack<>();
            Stack<String> right = new Stack<>();
            
            for(int i=0; i<s.length(); i++//왼쪽 스택에 입력받은 문자열을 전부 넣는다.
                left.push(s.substring(i,i+1));
            
            
            for(int i=0; i<n; i++) {
                StringTokenizer st = new StringTokenizer(reader.readLine());
                String c = st.nextToken();
                switch(c) {
                    case "L":
                        if(!left.isEmpty())
                            right.push(left.pop());
                        break;
                    case "D":
                        if(!right.isEmpty())
                            left.push(right.pop());
                        break;
                    case "B":
                        if(!left.isEmpty()) 
                            left.pop();
                        break;
                    case "P":
                        left.push(st.nextToken());
                        break;
                }
            }
        
            while(!left.isEmpty()) //오른쪽 스택에 왼쪽 스택 옮기기
                right.push(left.pop());
 
            while(!right.isEmpty())
                System.out.print(right.pop());
        }
    
    }
 
 

커서 기준 거리 1이내로 연산이 행해지는 문제였기 때문에

모든 연산이 O(1)인 스택을 사용하겠다는 생각을 했었어야 했다. 난 멍청이다 

 

'Algorithm' 카테고리의 다른 글

백준 9095 1, 2, 3 더하기 Java  (0) 2019.04.09
백준 11726 2xn 타일링 Java  (0) 2019.04.09
백준 1463 1로만들기 Java  (2) 2019.04.09
백준 10799 쇠막대기 Java  (2) 2019.04.08
백준 10951 A+B - 4 Java  (0) 2019.04.08