백준 2966번 [찍기](C++) -yes6686- 티스토리

백준 문제 풀이: 2966 (찍기)

---

문제 링크: https://www.acmicpc.net/problem/2966

문제 설명:

세 사람 **Adrian**, **Bruno**, **Goran**이 시험 문제를 찍는 규칙을 가지고 있습니다. 주어진 정답 문자열과 각 사람의 규칙에 따라 채점을 하고, 가장 많은 점수를 받은 사람을 출력합니다. 동점자가 있으면 이름을 알파벳 순서대로 출력합니다.

---

문제 해결 코드

#include <iostream>
#include <algorithm>
using namespace std;

// 각 사람의 찍기 패턴
char ad[3] = { 'A', 'B', 'C' };
char br[4] = { 'B', 'A', 'B', 'C' };
char go[6] = { 'C', 'C', 'A', 'A', 'B', 'B' };

// 비교 함수: 점수를 기준으로 내림차순 정렬
bool compare(pair<int, string> a, pair<int, string> b) { 
    if (a.first == b.first) {
        return a.second < b.second; // 점수가 같으면 이름 오름차순
    }
    return a.first > b.first; // 점수 내림차순
}

pair<int, string> ans[3]; // 점수와 이름을 저장할 배열

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n; // 문제 개수
    string s;
    cin >> s; // 정답 문자열

    int adi = 0, bri = 0, goi = 0; // 각 사람의 패턴 인덱스 초기화

    // 이름 설정
    ans[0].second = "Adrian";
    ans[1].second = "Bruno";
    ans[2].second = "Goran";

    // 정답 비교 및 점수 계산
    for (int i = 0; i < n; i++) {
        if (ad[adi] == s[i]) ans[0].first++;
        if (br[bri] == s[i]) ans[1].first++;
        if (go[goi] == s[i]) ans[2].first++;

        adi = (adi + 1) % 3; // 패턴 반복
        bri = (bri + 1) % 4;
        goi = (goi + 1) % 6;
    }

    // 점수 정렬
    sort(ans, ans + 3, compare);

    // 최고 점수 출력
    cout << ans[0].first << '\n';
    cout << ans[0].second << '\n';

    // 동점자 처리
    for (int i = 1; i < 3; i++) {
        if (ans[i].first == ans[i - 1].first) {
            cout << ans[i].second << '\n';
        } else {
            break;
        }
    }

    return 0;
}

---

코드 설명

코드의 주요 로직과 사용된 알고리즘 설명:

• 찍기 패턴: - **Adrian**: A, B, C 반복 (3개) - **Bruno**: B, A, B, C 반복 (4개) - **Goran**: C, C, A, A, B, B 반복 (6개)
• 정답 채점: - 각 사람의 패턴과 정답 문자열을 비교하여 점수를 누적합니다.
• 정렬 기준: - 점수를 기준으로 내림차순 정렬, 점수가 같다면 이름을 기준으로 오름차순 정렬합니다.
• 결과 출력: - 가장 높은 점수를 출력하고, 동점자가 있을 경우 이름도 출력합니다.

시간 복잡도 분석

• 문제 개수를 n이라 할 때, 채점 과정의 시간 복잡도는 **O(n)**입니다.
• 정렬은 상수 크기(3명)를 기준으로 수행되므로 **O(1)**입니다.
• 따라서 전체 시간 복잡도는 **O(n)**입니다.

---

결과

정답 패턴을 비교하여 가장 높은 점수를 받은 사람의 이름과 점수를 출력합니다.

• 입력 예시:

  9  
  AAAABBBBB

• 출력 예시:

  4  
  Adrian  
  Bruno

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!