[자바] 백준 31778 - PPC 만들기 (java)

목차

문제 : boj31778

 

 

필요 알고리즘

• 그리디, 투 포인터 (두 포인터), 수학 
  
  • 그리디 아이디어로 풀 수 있고, 내 경우 투 포인터를 사용해 구현했다. 경우의 수를 찾기 위해 약간의 수학적 지식도 필요하다.

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

 

 

풀이

  우선 어떻게 K번 연산을 적용해야 PPC 부분문자열의 최대치가 될지부터 생각해보자. 직관적으로 찾기 어렵지 않은데, 아무튼 최대한 많은 P가 앞쪽으로 가야하고, 최대한 많은 C가 뒤쪽으로 가야한다. 그 말은 뒤에서부터 P를 찾고, 앞에서부터 C를 찾으면서 최대 K번 서로 교체해버리면 된다는 얘기이다.

int s = 0;	// 앞에서부터 시작하는 포인터
int e = n-1;// 뒤에서부터 시작하는 포인터
while (k>0 && s<e) {
    while (s<n && arr[s] == 'P') s++;	// 앞에서부터 C를 찾는다.
    while (e>0 && arr[e] == 'C') e--;	// 뒤에서부터 P를 찾는다.
    if (s<e) {
        k--;	// 연산을 사용했으므로 k--
        arr[s] = 'P';	// 현재 가장 앞의 C와 가장 뒤의 P를 바꿔준다.
        arr[e] = 'C';
    }
}

 

 

  위의 그리디 아이디어를 통해 최대 K번의 연산이 적용되었다면 PPC 부분문자열의 최대치가 가능한 배열이 마련되었을꺼다. 그러니 이제 PPC 부분문자열 개수만 세주면 된다. 말로 설명하면 간단한데, 좌측부터 우측으로 배열을 살펴보다가 'C'를 만났다고 해보자. 그럼 'C'를 만나기 이전까지 존재했던 P의 개수를 X라 하자. 이 때 XC2 (X개 중 2개를 뽑는 경우의 수) 를 매번 답에 더해주면 된다.

 

  그렇게 해도 되고, 내 경우엔 어차피 전부 살펴보면서 계산할꺼니깐 XC2 값을 누적해서 계산했다. 최종적으로 c를 출력하면 답이 된다.

long a = 0;	// 현재까지 나온 'P' 갯수
long b = 0;	// 현재까지 가능한 'PP' 조합의 갯수
long c = 0;	// 현재까지 가능한 'PPC' 조합의 갯수
for (char cur : arr) {
    if (cur == 'P') b += a++;	// 'P'라면 일단 'PP' 조합 늘려주고, a는 1 증가
    else c += b;	// 'C'라면 현재까지 가능한 'PPC' 수에다가 'PP' 수를 더해주면 된다.
}

 

 

 

코드 : github

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

public class Main {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in), 1 << 16);

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

    private void solution() throws Exception {
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());
        char[] arr = br.readLine().toCharArray();

        int s = 0;
        int e = n-1;
        while (k>0 && s<e) {
            while (s<n && arr[s] == 'P') s++;
            while (e>0 && arr[e] == 'C') e--;
            if (s<e) {
                k--;
                arr[s] = 'P';
                arr[e] = 'C';
            }
        }

        long a = 0;
        long b = 0;
        long c = 0;
        for (char cur : arr) {
            if (cur == 'P') b += a++;
            else c += b;
        }
        System.out.println(c);
    }
}