[백준] 25381번 - ABBC [Java]

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

 

[백준] 25381번 - ABBC [Java]

[백준] 25381번 - ABBC [Java]

---

1.  아이디어

 

시행할 수 있는 최대 횟수는 B와 C를 먼저 지우고 A와 B를 지울 때 최대가 되는 것을 이용했다.

---

2. 문제풀이

 

B와 C, A와 B를 지울 때 앞의 문자를 기준으로 가장 가까운 뒷쪽에 위치한 문자와 삭제할 때 가장 많이 지울 수 있다.

 

B와 C를 지울 때는 B를 발견하면 그 뒤로 가장 가까운 C와 매핑시켜 지우는 과정을 반복하고, A와 B를 지울 때는 A를 발견하면 그 뒤로 가장 가까운 B와 매핑시켜 지우는 과정을 반복하면 된다.

 

이 과정에서 처음엔 여러 개의 Deque를 만들어서 풀이를 했는데 52점을 받았다. 예외 케이스를 찾다가 A 15만개 뒤에 B 15 만개가 붙은 문자열에서 시간이 매우 많이 소요되는 것을 발견해서 로직을 다시 작성했다.

 

풀이는 배열과 투 포인터를 활용해서 left에 매핑시키는 앞쪽 원소의 인덱스, right에 매핑시키는 뒤쪽 원소의 인덱스를 찾아서 삭제하고 카운팅하는 과정을 반복했다. 이 과정에서 right는 항상 left의 오른쪽에 있어야 함에 주의해야 한다.

---

3. 코드

 

import java.io.*;

public class Main {

    private static char[] S;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        S = br.readLine().toCharArray();

        int ans = 0;

        ans += delete('B', 'C');
        ans += delete('A', 'B');

        System.out.println(ans);
    }

    private static int delete(char c1, char c2) {
        int left = 0;
        int right = left + 1;
        int cnt = 0;

        while (true) {
            while (left < S.length && S[left] != c1) {
                left++;
            }
            while (right < S.length && (S[right] != c2 || left > right)) {
                right++;
            }

            if (right == S.length) {
                break;
            }

            S[left] = ' ';
            S[right] = ' ';
            cnt++;
        }

        return cnt;
    }

}

---

4. 후기