[Java] 특정 문자 제거

문제

문자열 n과 삭제할 문자열 m이 주어질 때, n에서 m을 지운 n을 출력하는 알고리즘을 작성하라.

풀이

가장 먼저 생각나는 방법은 n 문자열을 전부 순회하면서 m이랑 일치하는지 확인하고 일치하면 그냥 두고 일치하지 않으면 출력할 배열에 추가하는 방법이다.
하지만 이 방법은 O(n^2)이기 때문에 조금 더 효율적인 방법을 찾아봐야 한다.
삭제할 문자열 m을 기준으로 bool 배열을 만들어서 true로 저장하고 n을 돌면서 bool 배열에 없다면 출력할 배열에 추가한다.

느낀점

항상 코드를 작성하기 전에 어떤 알고리즘이 합당한지 생각해보고 (이게 되려면 일단 많이 나오는 알고리즘을 공부해야 하고 그게 어떤 알고리즘이며 코드는 어떤식으로 구현되는지 이해해야 한다. 외우면 언젠가는 까먹기 때문에 꼭 이해해야 한다.) 최악의 케이스를 생각한다.
O(n^2)의 시간복잡도가 나오는 문제가 코딩테스트에 나올 확률은 적기 때문에 다른 방법을 생각해봐야 한다.
또한 문자열은 ascii 값 기준으로 나오는 경우가 많기 때문에 ascii값이 총 128개인 것을 기억해두자.

코드

public StringBuilder solution(String str, String remove) {

        StringBuilder answer = new StringBuilder();

        // bool 배열을 이용해서 remove 문자열만 true로 지정한다.
        // ascii 문자열은 128개니까 127로 배열 크기 초기화해야한다.
        // 이유는 배열 index는 ascii 값으로 들어가기 때문이다.
        boolean flag[] = new boolean[127];
        for (char c : remove.toCharArray()) {
            flag[c] = true;
        }

        // str 문자열을 순회하면서 flag 배열안에 없으면 answer 문자열에 추가한다.
        for (int i = 0; i < str.length(); i++) {
            char c = str.charAt(i);
            if (!flag[c]) {
                answer.append(c);
            }
        }

        return answer;
    }