Q 14453 Hoof, Paper, Scissors (Silver)

💡 문제 요약 및 분석

John과 Bessie가 N번동안 가위 바위 보를 한다. Bessie 는 John 이 낼 수를 미리 알고 있지만 N번 동안 단 한 번만 자신의 수를 바꿀 수 있다. 예를 들어 x번 동안 가위를 냈다면, 남은 N-x번 동안 보를 낼 수 있는 것이다. Bessie 가 최대로 이길 수 있는 횟수가 몇 번인지 계산하자.

💡 알고리즘 설계

🔥 힌트를 보고 풀었다. 누적합 배열을 활용해서 풀어야 한다.

1. 입력

   • 표준입력 받는 John 의 가위바위보 순서를 참고하여 세 개의 누적합 배열을 만든다. (H, P, S 를 냈을 때의 누적합)

2. 연산

   • Bessie 가 플레이하는 경우의 수는 6개다. (H,P)(H,S)(P,H)(P,S)(S,H)(S,P)
   • 각 경우의 수를 N번 반복하면서 누적합의 max 를 찾는다. (H,P) 를 예로 들자면 H(0,i) + P(i+1,N) 합을 구하는 것이다.

3. 출력

   • max 변수를 출력한다.

💡 코드

import java.io.*;

public class Main {
    static int max;
    static int N;
    static void process(int[] A, int[] B) {
        for (int i = 1; i < N + 1; i++) {
            int temp = A[i-0] + B[N] - B[i-1];
            max = max < temp ? temp : max;
        }
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        int[] P = new int[N + 1];
        int[] H = new int[N + 1];
        int[] S = new int[N + 1];

        for (int i = 1; i < N + 1; i++) {
            char input = br.readLine().charAt(0);
            if (input == 'P') {
                P[i] = P[i-1] + 0;
                H[i] = H[i-1] + 0;
                S[i] = S[i-1] + 1;
            }
            if (input == 'H') {
                P[i] = P[i-1] + 1;
                H[i] = H[i-1] + 0;
                S[i] = S[i-1] + 0;
            }
            if (input == 'S') {
                P[i] = P[i-1] + 0;
                H[i] = H[i-1] + 1;
                S[i] = S[i-1] + 0;
            }
        }

        process(H,P);
        process(H,S);
        process(P,S);
        process(P,H);
        process(S,H);
        process(S,P);

        System.out.println(max);
    }
}

💡 시간 복잡도, 공간 복잡도

시간 복잡도	공간 복잡도
O(n)	O(n)

💡 다른 풀이

어떻게든 풀긴 했지만 process() 함수를 하드코딩 해버린게 마음에 걸려서 다른 풀이를 찾아봤다. 내가 만든 P, H, S 3개의 배열을 아예 이차원 배열로 만들어서 for문으로 각 쌍 조합을 확인하면 더욱 간단하고 유지보수하기 좋은 코드가 된다.

// P, H, S 누적합을 저장할 이차원 배열 생성
int[][] prefix = new int[3][N + 1];

// 표준입력을 받아 누적합 계산
for (int i = 1; i < N + 1; i++) {
    char input = br.readLine().charAt(0);
    for (int j = 0; j < 3; j++) {
        prefix[j][i] = prefix[j][i-1];  // 누적합하기위해 이전 값을 미리 넣어둔다.
    }
    if (input == 'P') prefix[0][i]++;
    else if (input == 'H') prefix[1][i]++;
    else if (input == 'S') prefix[2][i]++;
}

// 각 쌍 조합에 대해 A(0,i), B(i+1,N) 전략으로 진행
int max = 0;
for (int a = 0; a < 3; a++) {
    for (int b = 0; b < 3; b++) {
        if (a == b) continue;
        for (int i = 0; i < N + 1; i++) {
            int wins = prefix[a][i] + prefix[b][N] - prefix[b][i];
            max = Math.max(max, wins);
        }
    }
}

System.out.println(max);