[Baekjoon] 25381_ABBC

Gold IV

문제(출처: https://www.acmicpc.net/problem/25381)

---

< ABBC >

 

문제 풀이 

 

A -> B , B -> C를 지우기 위해서는 어디에 위치한 B를 지우는가가 중요하다고 생각했다.

 

A를 뒤에서부터 지울 때 B 또한 뒤에서부터 지운다.

B를 앞에서부터 지울 때 C 또한 앞에서부터 지운다.

 

이 방식을 사용해서 문제를 해결했다.

 

 

 my solution (Java)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Collections;
import java.util.Deque;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;

public class _25381_ { // ABBC

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

		String str = bf.readLine();

		PriorityQueue<Integer> aQueue = new PriorityQueue<>(Collections.reverseOrder());
		Deque<Integer> bQueue = new ArrayDeque<>();
		Queue<Integer> cQueue = new LinkedList<>();

		int result = 0;

		for (int i = 0; i < str.length(); i++) {
			char x = str.charAt(i);
			if (x == 'A') {
				aQueue.add(i);
			} else if (x == 'B') {
				bQueue.add(i);
			} else if (x == 'C') {
				cQueue.add(i);
			}
		}

		while (!aQueue.isEmpty()) {
			int num = aQueue.poll();
			if (!bQueue.isEmpty() && num < bQueue.peekLast()) {
				result += 1;
				bQueue.pollLast();
			}
		}

		while (!bQueue.isEmpty()) {
			int num = bQueue.pollFirst();
			while(!cQueue.isEmpty() && num > cQueue.peek()) {
				cQueue.poll();
			}
			if(!cQueue.isEmpty() && num < cQueue.peek()) {
				result+=1;
				cQueue.poll();
			}
		}

		System.out.println(result);
	}
}

 

Main

변수)
str : 문자열
aQueue : PriorityQueue <Integer>
bQueue : Deque <Integer> 
cQueue : Queue <Integer>
result : 시행할 수 있는 최대 횟수

 

- 문자열(str) 입력

- 문자열 탐색하면서 A, B, C의 각각 index를 저장

- 문자열 뒤에 있는 A부터 제거하며 B 또한 뒤에 있는 B부터 제거

: A의 index보다 B의 index가 커야 result+1 후 제거 가능

- 문자열 앞에 있는 B부터 제거하며 C 또한 앞에 있는 C부터 제거

: B의 index보다 C의 index가 작다면 계속해서 제거할 수 없으므로 C의 index가 더 커질 때까지 제거

: B의 index가 C의 index보다 작다면 result+1 후 C 제거

- 시행할 수 있는 최대 횟수(result) 출력

---

---