Baekjoon 3111 검열 - 문자열+스택

더 깔끔한 노션을 원한다면

Baekjoon 3111 검열

3111번: 검열

처음 생각 - StringBuilder

문제 포인트들을 천천히 살펴보았다.

1. T에 A가 없으면 알고리즘을 종료한다.
2. T에서 처음 등장하는 A를 찾은 뒤, 삭제한다.
3. T에 A가 없으면 알고리즘을 종료한다.
4. T에서 마지막으로 등장하는 A를 찾은 뒤, 삭제한다.
5. 1번으로 돌아간다.

위 포인트대로 구현하면 되는 문제였다.

1. StringBuilder로 풀이 ❗

두 번 뒤집기에서 String은 메모리 초과가 난다는 것을 배우고 푼 터라 StringBuilder로 접근하였다.

indexOf와 delete, reverse 등, StringBuilder의 메서드를 활용했으나 시간초과!

indexOf의 시간복잡도가 O(n)이므로 총 O(n^2)가 되므로 시간초과!

sb.append(T);
int index = sb.indexOf(A);
String reverseA = reverse(A);
while(index != -1) {
  sb = sb.delete(index, index + size).reverse();
  reverseCount++;
  if(reverseCount % 2 == 0) {
    index = sb.indexOf(A);
  } else {
    index = sb.indexOf(reverseA);
  }
}

2. 문자열 스택 ❗

힌트를 확인해보니 역시 문자열+스택이었다.

start, end(투 포인터)로 Key를 찾아준다.

start = 0;
end = text.length() - 1;
boolean isRemove = false;
int keyLength = key.length();
while (start <= end) {
  if (!isRemove) {
    isRemove = SearchKeyLeft(left, keyLength);
  }
  if (isRemove && start <= end) {
    isRemove = SearchKeyRight(right, keyLength);
  }
}

T에서 처음 등장하는 A를 찾은 뒤, 삭제한다.(SearchKeyLeft)

private static boolean SearchKeyLeft(Stack<Character> left, int keyLength) {
  left.push(text.charAt(start++));
  if (left.size() >= keyLength && left.peek() == key.charAt(keyLength - 1)) {
    int keyLen = keyLength - 1;
    boolean check = true;
    for (int j = left.size() - 1; j >= left.size() - keyLength; j--) {
      if (left.get(j) != key.charAt(keyLen--)) {
        check = false;
        break;
      }
    }
    if (check) {
      for (int j = 0; j < keyLength; j++) {
        left.pop();
      }
      return true;
    }
  }
  return false;
}

T에서 마지막으로 등장하는 A를 찾은 뒤, 삭제한다.(SearchKeyRight)

private static boolean SearchKeyRight(Stack<Character> right, int keyLength) {
  String keyReverse = new StringBuilder(key).reverse().toString();
  right.push(text.charAt(end--));
  if (right.size() >= keyLength && right.peek() == keyReverse.charAt(keyLength - 1)) {
    int keyLen = keyLength - 1;
    boolean check = true;
    for (int j = right.size() - 1; j >= right.size() - keyLength; j--) {
      if (right.get(j) != keyReverse.charAt(keyLen--)) {
        check = false;
        break;
      }
    }
    if (check) {
      for (int j = 0; j < keyLength; j++) {
        right.pop();
      }
      return false;
    }
  }
  return true;
}

주의 사항 📢

SearchKeyLeft와 SearchKeyRight가 끝났다고 정답이 아니다.

left와 right를 합쳤을 때 key가 발견될 수 있기 때문!

이 곳에는 indexOf와 delete를 사용해주었다.

while (true) {
  int idx = sb.indexOf(key);
  if (idx < 0)
    break;
  sb.delete(idx, idx + key.length());
}

전체 코드

/**
 * @처음생각 indexOf, delete를 사용 => 시간초과 O(N^2)
 * @포인트 left, right스택으로 해결
 */
import java.io.*;
import java.util.*;

public class Main {
  public static void main(String[] args) throws IOException {
    System.out.println(P3111());
  }

  static String key, text;
  static int start, end;

  static String P3111() throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    // StringTokenizer st = new StringTokenizer(br.readLine());
    StringBuilder sb = new StringBuilder();
    key = br.readLine();
    text = br.readLine();
    Stack<Character> left = new Stack<>();
    Stack<Character> right = new Stack<>();
    start = 0;
    end = text.length() - 1;
    boolean isRemove = false;
    int keyLength = key.length();
    while (start <= end) {
      if (!isRemove) {
        isRemove = SearchKeyLeft(left, keyLength);
      }
      if (isRemove && start <= end) {
        isRemove = SearchKeyRight(right, keyLength);
      }
    }
    while (!left.isEmpty()) {
      right.push(left.pop());
    }
    while (!right.isEmpty()) {
      sb.append(right.pop());
    }
    while (true) {
      int idx = sb.indexOf(key);
      if (idx < 0)
        break;
      sb.delete(idx, idx + key.length());
    }
    return sb.toString();
  }

  private static boolean SearchKeyLeft(Stack<Character> left, int keyLength) {
    left.push(text.charAt(start++));
    if (left.size() >= keyLength && left.peek() == key.charAt(keyLength - 1)) {
      int keyLen = keyLength - 1;
      boolean check = true;
      for (int j = left.size() - 1; j >= left.size() - keyLength; j--) {
        if (left.get(j) != key.charAt(keyLen--)) {
          check = false;
          break;
        }
      }
      if (check) {
        for (int j = 0; j < keyLength; j++) {
          left.pop();
        }
        return true;
      }
    }
    return false;
  }

  private static boolean SearchKeyRight(Stack<Character> right, int keyLength) {
    String keyReverse = new StringBuilder(key).reverse().toString();
    right.push(text.charAt(end--));
    if (right.size() >= keyLength && right.peek() == keyReverse.charAt(keyLength - 1)) {
      int keyLen = keyLength - 1;
      boolean check = true;
      for (int j = right.size() - 1; j >= right.size() - keyLength; j--) {
        if (right.get(j) != keyReverse.charAt(keyLen--)) {
          check = false;
          break;
        }
      }
      if (check) {
        for (int j = 0; j < keyLength; j++) {
          right.pop();
        }
        return false;
      }
    }
    return true;
  }
}