[자바] 백준 25381 - ABBC (java)

목차

문제 : boj25381

 

 

필요 알고리즘

• 그리디
  
  • 적절한 규칙을 적용해 선택해 나가는 방식으로 풀 수 있는 문제이다.

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

 

풀이

  어.. 이럼 되지 않나? 해서 구현해보니 됬다. 그래서 딱히 풀이랄건 없구 규칙을 적어보면 다음과 같다.

1. 'C'를 좌측부터 우측으로 차례대로 찾으면서, 해당 위치 이전에 가장 처음으로 나왔던 'B'와 함께 지운다.

2. 'A'를 우측부터 좌측으로 차례대로 찾으면서, 해당 위치 이후에 가장 마지막으로 나왔던 'B'와 함께 지운다.

 

  딱히 증명이라기보다는 그냥 이게 제일 C와 A 각자가 영향 안끼치면서 찾을 수 있을 것 같아 이렇게 하게 되었다.

구현 방식은 다양할 것 같다. 내 경우엔 TreeSet으로 구현했다.

 

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in), 1<<16);
    private static final int MAX = 300000;
    private static final int MIN = -1;

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }

    public void solution() throws Exception {
        String s = br.readLine();
        TreeSet<Integer> a = new TreeSet<>();
        TreeSet<Integer> b = new TreeSet<>();
        TreeSet<Integer> c = new TreeSet<>();

        for (int i = 0; i < s.length(); i++) {
            char cur = s.charAt(i);
            switch (cur) {
                case 'A': a.add(i); break;
                case 'B': b.add(i); break;
                case 'C': c.add(i); break;
            }
        }
        a.add(MAX); a.add(MIN);
        b.add(MAX); b.add(MIN);
        c.add(MAX); c.add(MIN);

        int cur = c.higher(MIN);
        int cnt = 0;
        while (cur != MAX) {
            int bPos = b.higher(MIN);
            if (bPos < cur) {
                c.remove(cur);
                b.remove(bPos);
                cnt++;
            };

            cur = c.higher(cur);
        }

        cur = a.lower(MAX);
        while (cur != MIN) {
            int bPos = b.lower(MAX);
            if (bPos > cur) {
                a.remove(cur);
                b.remove(bPos);
                cnt++;
            }

            cur = a.lower(cur);
        }

        System.out.println(cnt);
    }
}