Q 2966 찍기

💡 문제 요약 및 분석

상근, 창영, 현진이는 C언어 필기 시험을 찍으려고 한다. 세 사람은 다음과 같은 법칙으로 문제를 찍는다. 필기 시험 N개의 정답이 주어졌을 때 가장 많은 문제를 맞힌 사람이 누구인지 출력하자. (1 ≤ N ≤ 100) 여러 명일 경우 상근 » 창영 » 현진 순으로 한 줄에 하나씩 출력한다.

상근 (Adrian) - A, B, C, A, B, C, A, B, C, A, B, C, ...
창영 (Bruno) - B, A, B, C, B, A, B, C, B, A, B, C, ...
현진 (Goran) - C, C, A, A, B, B, C, C, A, A, B, B, ...

💡 알고리즘 설계

1. 친구들의 찍기 법칙을 분석해보자. 상근 - 1,2,3,1,2,3,... 으로 3개짜리 배열을 순차적으로 순환하는 구조이다. 창영 - 2,1,2,3,2,1,2,3,... 으로 홀수 번째 순서마다 1,3 이 반복되며, 이는 2-1, 2+1 이라고 생각할 수 있다. 현진 - 3,3,1,1,2,2,3,3,... 으로 상근이와 비슷하게 3 부터 시작해서 1,1,2,2,3,3 으로 이어지는 구조가 된다.

2. 위 패턴을 코드로 정의해보자. for(int i = 0; i < N; i++) 반복문 안에 들어갈 연산이다. 상근 - int adrian = i % 3 + 1; 창영 - int bruno = 2 + varBruno; varBruno = varBruno * -1; 현진 - int testGoran = j % 3 + 1; ... 이하 생략

3. 점수집계용 배열을 선언하여 정답 횟수마다 +1 한다.

4. 최댓값을 가진 친구의 아이디를 출력한다.

💡 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {

    public static int[] answer = {0, 0, 0};
    public static int adrian = 0;
    public static int bruno = 0;
    public static int goran = 3;
    public static int varBruno = -1;
    public static int varGoran = 0;
    public static int j = 0;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        String str = br.readLine();
        int[] input = new int[N];
        for (int i = 0; i < N; i++) {
            char temp = str.charAt(i);
            switch (temp) {
                case 'A' :
                    input[i] = 1;
                    break;
                case 'B' :
                    input[i] = 2;
                    break;
                case 'C' :
                    input[i] = 3;
                    break;
            }
        }

        for (int i = 0; i < N; i++) {
            // 상근
            adrian = i % 3 + 1;
            int checkAdrian = (adrian == input[i]) ? 1 : 0;
            answer[0] += checkAdrian;

            // 창영
            if(i % 2 != 0) {
                bruno = 2 + varBruno;
                varBruno = varBruno * -1;
            } else {
                bruno = 2;
            }
            int checkBruno = (bruno == input[i]) ? 1 : 0;
            answer[1] += checkBruno;

            // 현진
            if (varGoran == 2) {
                goran = j % 3 + 1;
                j++;
                varGoran = 1;
            } else {
                varGoran++;
            }
            int checkGoran = (goran == input[i]) ? 1 : 0;
            answer[2] += checkGoran;
        }

        int max = 0;
        for (int i = 0; i < answer.length; i++) {
            max = (max > answer[i]) ? max : answer[i];
        }
        System.out.println(max);

        for (int i = 0; i < answer.length; i++) {
            if (max == answer[i]) {
                switch (i) {
                    case 0 :
                        System.out.println("Adrian");
                        break;
                    case 1 :
                        System.out.println("Bruno");
                        break;
                    case 2 :
                        System.out.println("Goran");
                        break;
                }
            }
        }

    }

}

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

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

💡 다른 풀이

처음 봤을 때, 각각의 패턴을 배열로 선언해서 풀면 되겠다 싶었는데… 괜히 수식화 해보고 싶은 마음에 멀리 돌아간 것 같다.

char[] adrian = {'A','B','C'};
char[] bruno = {'B','A','B','C'};
char[] goran = {'C','C','A','A','B','B'};