백준 9935 - 문자열 폭발 - Java

 

https://www.acmicpc.net/problem/9935

 

접근방법

스택 문제이기 때문에 Stack클래스를 사용하는 방향으로 문제에 접근했다.

1. 스택에 입력된 문자열의 문자를 하나씩 넣기
2. 넣을 때마다 조건 확인
   • 조건 : 폭발 문자열의 마지막 글자와 같은지, 스택이 폭발 문자열의 길이보다 긴지 
3. 조건에 맞는다면 폭발 문자열인지 확인
4. 맞다면 폭발 문자열을 스택에서 제거
5. 아니라면 제거하지 않고 1번으로 돌아가기

 

참고사항 

N : 입력 문자열의 길이

M : 폭발 문자열의 길이

1차 시도 : Stack 사용 - O(N*M)

결과 : 시간초과

import java.util.Scanner;
import java.util.Stack;

public class Main {
    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);
        
        String input = scanner.nextLine();
        
        String boom = scanner.nextLine();
        char boomLast = boom.charAt(boom.length() - 1);
        
        Stack<Character> stack = new Stack<>();

        // 문자열의 단어를 하나씩 스택에 추가
        for (int i = 0; i < input.length(); i++) {
            
            char c = input.charAt(i);
            stack.push(c);
            
            // 연쇄폭발을 생각해서 while문을 구현
            while (stack.size() >= boom.length() && stack.peek() == boomLast) {
				
                StringBuilder sb = new StringBuilder();
                for (int j = 0; j < boom.length(); j++) {
                    sb.append(stack.elementAt(stack.size() - boom.length() + j));
                }
                
                // 폭발문자라면
                if (sb.toString().equals(boom)) {
                    for (int j = 0; j < boom.length(); j++) {
                        stack.pop();
                    }
                }
                // 아니면 탈출
                else break;
            }
        }

		// 출력
        if (stack.isEmpty()) {
            System.out.println("FRULA");
        } else {
            for (int i = 0; i < stack.size(); i++) {
                System.out.print(stack.elementAt(i));
            }
        }
    }
}

2차 시도 : StringBuilder 사용 - O(N)

비교문에서 단어 하나 하나 비교하고 추가 연산하는게 너무 오래 걸리나 싶어서 StringBuilder를 스택으로 사용

비교는 substring함수와 equals함수로 단순화

또한 stack.length함수 반복호출을 줄이기 위해, 대신 stackSize변수를 따로 만들고 관리해서 사용

결과 : 성공

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);

		String input = scanner.nextLine();
        
        String boom = scanner.nextLine();
        char boomLast = boom.charAt(boom.length() - 1);
        
        StringBuilder stack = new StringBuilder();
        int stackSize = 0;

		// 문자열의 단어를 하나씩 스택에 추가
        for (int i = 0; i < input.length(); i++) {
        
            char c = input.charAt(i);
            stack.append(c);
            stackSize++;
        
            while (stackSize >= boom.length() && stack.charAt(stackSize - 1) == boomLast) {
                // 폭발문자라면
                if (stack.substring(stackSize - boom.length(), stackSize).equals(boom)) {
                    stack.delete(stack.length() - boom.length(), stackSize);
                    stackSize -= boom.length();
                }
                // 아니면 탈출
                else break;
            }
        }
        if (stack.length() == 0) {
            System.out.println("FRULA");
        } else {
            System.out.println(stack);
        }
    }
}

근데 문득 든 생각

> 문자열 비교하려면 하나하나 까보는 수밖에 없지 않나? equals는 어떻게 동작하지?

그래서 찾아보니 여기서는 이렇다고 하더라, 또 라이브러리를 따라가보니 아래와 같은 코드로 구현되어 있었다.

살펴보니 즉, 어차피 하나하나 비교 한다는 소리다. -> 사실 2차 시도는 1차 시도와 마찬가지로 시간복잡도가 O(N*M)이었다!!

@IntrinsicCandidate
public static boolean equals(byte[] value, byte[] other) {
    if (value.length == other.length) {
        for (int i = 0; i < value.length; i++) {
            if (value[i] != other[i]) {
                return false;
            }
        }
        return true;
    }
    return false;
}

 

 

그럼 통과에 영향을 미치는게 뭐지?

while문 내부는 영향을 미치지 않는다면, 소거법에 의해 이후 코드가 범인이 될 수밖에 없다.

근데 그럼 출력밖에 없는데?? 하면서 코드를 다시 살펴봤다.

 

둘의 차이는 System.out.print함수를 통한 출력 횟수였다.

N번 호출하냐 vs 한 번 호출하냐 

 

처음 내 생각은 "어차피 O(N*M) 이하의 시간복잡도만 맞춘다면 시간 안에 실행되지 않나?" 였다.

심지어 출력함수의 호출 횟수는 N번인데!! 그런데도 통과가 안되는건 현실이었다...

위 결과를 나는 이렇게 해석했다.

> N번 출력하는게 N*M번 연산하는 것보다 더 느리다!

 

그리고 찾아보던 중 System.out.print가 겁나게 느리다는 걸 여기서 알 수 있었다.

3차 시도 : 출력 횟수 변경

찾아본 내용을 바탕으로 그냥 Stack을 사용하고, 대신 출력을 연산으로 바꿔서 구현한 후에 제출해봤다.

결과 : 성공

import java.io.BufferedWriter;
import java.io.OutputStreamWriter;
import java.util.Scanner;
import java.util.Stack;
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        BufferedWriter bufferedWriter = new BufferedWriter(new OutputStreamWriter(System.out));
        String input = scanner.nextLine();
        String boom = scanner.nextLine();
        int boomSize = boom.length();
        char boomLast = boom.charAt(boom.length() - 1);
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < input.length(); i++) {
            char c = input.charAt(i);
            stack.push(c);
            if (stack.size() >= boomSize && c == boomLast) {
                boolean isBoom = true;
                for (int j = 0; j < boomSize; j++) {
                    if (stack.get(stack.size() - boomSize + j) != boom.charAt(j)) {
                        isBoom = false;
                        break;
                    }
                }
                if (isBoom) {
                    for (int j = 0; j < boomSize; j++) {
                        stack.pop();
                    }
                }
            }
        }
        if (stack.isEmpty()) {
            System.out.println("FRULA");
        } else {
       		
            // 출력 대신 Stack의 값들을 StringBuilder에 옮기기
            StringBuilder stringBuilder = new StringBuilder();
            for (int i = 0; i < stack.size(); i++) {
                stringBuilder.append(stack.get(i));
            }
            // 한번에 출력
            System.out.println(stringBuilder);
        }
    }
}

 

이 외에 여러가지 시도들과 최종 코드

Stack.elementAt() 함수와 Stack.get()의 차이 - 속도 차이 없음

• 둘다 Vector 클래스에서 상속받는다.
• 다만 get()의 경우, 일반적으로 Java의 컬렉션 프레임워크에서 사용되는 메서드로, List 인터페이스를 구현한 클래스에서도 동일한 방식으로 동작한다.
• 여기서는 Vector클래스는 lagacy 클래스로 ArrayList에 대체되었다고 한다. 따라서 elementAt()보다는 ArrayList에 인터페이스에 가까운 get()함수를 사용하는게 좀 더 알맞아보인다.
• 추가적으로 같은 기능을 하기 때문에 속도에는 차이가 없다고 해서 한번 비교해본 결과, 음.. 사실이다 그렇게 차이가 나지는 않는다.

 

System.out.print대신 BufferedWriter사용하기 - 속도 차이 있음

• 위에서 이미 말했듯 System.out.print는 겁나 느리다. 
• 하지만 모든 출력이 저놈처럼 겁나 느리진 않다. 자바에서는 BufferedWriter는 저놈보다 30배 정도 빠르다.
• 그래서 한번 사용해봤는데 확실히 30배 빠름을 증명했다. 1차 시도에서 출력만 BufferedWriter로 바꿨는데 통과했다.
  • 하지만 속도는 다른 제출들 보다 느리긴 했다.
• 아까 말 했듯 StringBuilder를 사용하면 출력을 한 번에 할 수 있다.
  • 그런데도 그럼 BufferedWriter 쓰려고 한다면 선언, 할당,함수호출등 추가 연산이 들어간다.
  • 즉 오버헤드가 발생한다. 배보다 배꼽이 더 커진다. 
  • 그래서 StringBuilder로 구현한다면 그냥 System.out.print를 사용하는게 깔끔하고 속도도 빠르다.

 

연산량 줄이기 - 속도 차이 없음

• 시도2에서 stack.length()함수의 반복호출을 줄이기 위해 stackSize변수를 사용했다.
• 둘다 연산량은 O(1)이기 때문에, 실행되는 횟수가 중요하다 생각했고, 개인적으로 추가된 연산(21번, 27번줄의 연산) 횟수보다 StringBuilder.length() 반복호출 횟수가 더 많이 감소할 것으로 예측했다.
  • StringBuilder.length()를 사용한다면 while문 안에서 5번 사용된다.
  • 하지만 stackSize변수로 인한 추가연산은 for문 안에서 1번 while문 안에서 1번 뿐이다.
• 하지만 여러번 코드를 제출해본 결과, 그렇게 큰 차이는 없었다. 
• 아마 생각보다 추가된 연산과, 반복호출 횟수 사이의 차이가 그리 크지 않아서라고 추측된다. 
• + boom.length()는 다를 거라 생각했다. 안변하니까! 추가 연산이 없으니까! 근데 막상 변수화해서 제출해봤는데... 마찬가지로 그렇게 속도에 큰 변화는 없었다.

 

while문 if문으로 교체 - 속도 차이 있음

• 연쇄적으로 폭발문자열이 삭제되는 걸 고려해서 while문을 사용했는데, 생각해보니 단어마다 확인하기 때문에 if문으로 교체해도 정상작동할 것으로 보여서 while문 if문으로 교체했다.
• 이렇게 되면 if문을 내부 if문과 합칠 수 있어서 코드가 깔끔해지고 빨라졌다.

 

번외 : 시간 복잡도 계산방법

문제 제한시간은 2초, input의 최대크기(N)는 10⁶,폭발문자열의 최대 크기(M)는 36

보통 백준에서는 1초에 10⁸번의 연산이 가능하다.

따라서 그 아래까지만 맞춰주면 된다.

N*M = 3.6*10⁷ < 2*10⁸ 임으로, 시간복잡도가 O(N*M)이면 제한 시간 안에 널널히 들어온다고 판단했다.

 

최종코드

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        String input = scanner.nextLine();

        String boom = scanner.nextLine();
        int boomLength = boom.length();
        char boomLast = boom.charAt(boomLength - 1);

        StringBuilder stack = new StringBuilder();
        int stackSize = 0;

        // 문자열의 단어를 하나씩 스택에 추가
        for (int i = 0; i < input.length(); i++) {
            char c = input.charAt(i);
            stack.append(c);
            stackSize++;

            /*조건
             * 1. 스택이 폭발 문자열보다 길 것
             * 2. 스택의 top에 있는 문자가 폭발 문자의 끝 문자일 것
             * 3. 스택의 끝이 폭발 문자열과 일치한다면
             * */
            if (stackSize >= boomLength
                    && stack.charAt(stackSize - 1) == boomLast
                    && stack.substring(stackSize - boomLength, stackSize).equals(boom)) {
                stack.delete(stackSize - boomLength, stackSize);
                stackSize -= boomLength;
            }
        }
        if (stackSize == 0) {
            System.out.println("FRULA");
        } else {
            System.out.println(stack);
        }
    }
}

 

 

---

참고자료

• https://github.com/WooVictory/Ready-For-Tech-Interview/blob/master/Java/%5BJava%5D%20equals()%20%EB%A9%94%EC%86%8C%EB%93%9C%20%EB%8F%99%EC%9E%91%20%EC%9B%90%EB%A6%AC.md

Ready-For-Tech-Interview/Java/[Java] equals() 메소드 동작 원리.md at master · WooVictory/Ready-For-Tech-Interview

• https://www.acmicpc.net/blog/view/57
• https://stackoverflow.com/questions/18248774/whats-the-difference-between-getint-index-and-elementatint-index

What's the difference between get(int index) and elementAt(int index)?