[백준] 27919번 UDPC파티

https://www.acmicpc.net/problem/27919

문제 요약

• 투표 결과: U, D, P, C로 구성된 문자열이 주어집니다.
  • U: 윤이
  • D: 달구
  • P: 포닉스
  • C: 기권
• 문제의 핵심: 글씨체와 방향 때문에 U와 C, D와 P가 서로 혼동될 수 있습니다. 이를 고려하여 각 마스코트가 우승할 수 있는지를 판단해야 합니다.
• 우승 조건: 한 마스코트의 표가 다른 두 마스코트의 표보다 모두 많을 경우 그 마스코트가 우승합니다.
• 출력: 우승할 수 있는 마스코트를 U, D, P 순서대로 출력하며, 아무도 우승하지 못하면 C를 출력합니다.

import java.io.*;
import java.util.*;

public class Main {
  public static void main(String[] args) throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    String str = br.readLine();

    int cuCnt = 0;
    int dpCnt = 0;

    for (int i = 0; i < str.length(); i++) {
      String s = str.substring(i, i+1);

      if (s.equals("C") || s.equals("U")) {
        cuCnt++;
      } else if (s.equals("D") || s.equals("P")) {
        dpCnt++;
      }
    }
    String result = "";

    // U가 채택되는 경우
    // 반례 uc 50 d 45 p 45 인 경우 UDP 출력
    if (cuCnt > ((dpCnt + 1) / 2)) {
      result += "U";
    }

    // DP가 채택되는 경우
    if (dpCnt > 0) {
      result += "DP";
    }

    System.out.println(result);
  }
}

코드 동작 방식

1. 입력 처리:
   • BufferedReader를 사용하여 표의 결과 문자열 str을 입력받습니다.
2. 카운트 계산:
   • cuCnt: U와 C의 총 개수를 셉니다.
   • dpCnt: D와 P의 총 개수를 셉니다.
   • 각 문자를 순회하며 U 또는 C인 경우 cuCnt를, D 또는 P인 경우 dpCnt를 증가시킵니다.
3. 우승 조건 판단 및 결과 구성:
   • 윤이(U) 우승 조건:
     • cuCnt > ((dpCnt + 1) / 2)이면 U가 우승할 수 있다고 판단하여 결과 문자열에 "U"를 추가합니다.
     • 이는 U와 C의 총 개수가 D와 P의 총 개수의 절반보다 많을 때 U가 우승할 수 있다고 해석한 것입니다.
   • 달구(D)와 포닉스(P) 우승 조건:
     • dpCnt > 0이면 D와 P 중 하나라도 표를 받았다고 판단하여 결과 문자열에 "DP"를 추가합니다.
     • 이는 D와 P가 최소한 하나의 표를 받았을 경우, 이들 중 하나가 우승할 수 있다고 해석한 것입니다.
4. 결과 출력:
   • 최종적으로 구성된 result 문자열을 출력합니다.

코드의 문제점 및 반례

주어진 코드는 문제의 요구 사항을 완벽하게 충족하지 않습니다. 특히, 다음과 같은 반례에서 잘못된 결과를 출력할 수 있습니다.

반례:

• 입력: UC (U와 C가 각각 1표씩)
• cuCnt = 2
• dpCnt = 0
• cuCnt > ((dpCnt + 1) / 2) → 2 > 0.5 → 참 → "U" 추가
• dpCnt > 0 → 0 > 0 → 거짓 → "DP" 미추가
• 출력: "U"

하지만, 실제로는 U와 C가 혼동되므로 U와 C 중 어떤 것을 U로 해석하든 U의 최대 개수는 2, 최소 개수는 0입니다. 이 경우, U가 우승할 수 있으나, D와 P가 모두 0표이므로 우승 조건을 만족하지 않아야 합니다. 그러나 이 반례는 코드가 제대로 작동하는 것으로 보입니다.

더 큰 반례:

• 입력: UUC, DPP
• cuCnt = 3, dpCnt = 3
• cuCnt > ((dpCnt + 1) / 2) → 3 > 2 → 참 → "U" 추가
• dpCnt > 0 → 3 > 0 → 참 → "DP" 추가
• 출력: "UDP"

이 경우, U와 C가 혼동될 수 있으므로 U의 최대 개수는 3, 최소 개수는 0입니다. D와 P의 최대 개수는 3, 최소 개수는 0입니다. 따라서, U가 우승할 수 있고, D와 P도 각각 우승할 수 있는 가능성이 있으므로 "UDP"가 출력됩니다. 이는 올바른 결과입니다.

그러나 코드의 로직은 문제의 모든 가능한 조합을 고려하지 않습니다. 문제는 U와 C, D와 P의 가능한 모든 조합을 고려하여 각 마스코트의 최대 및 최소 표를 계산해야 합니다. 주어진 코드는 이를 단순히 총 합을 비교하는 방식으로 접근하여 일부 경우에 정확한 판단을 내리지 못할 수 있습니다.

시간 복잡도

• 입력 처리 및 카운트 계산:
  • 문자열의 길이를 N이라고 할 때, 각 문자를 한 번씩 순회하여 U/C와 D/P를 카운트하므로 O(N) 시간 복잡도를 가집니다.
• 조건 판단 및 결과 구성:
  • 상수 시간 내에 이루어지므로 O(1)입니다.
• 전체 시간 복잡도: O(N)

사용된 알고리즘 및 자료구조

• 알고리즘:
  • 카운팅 알고리즘: 각 문자(U, D, P, C)의 개수를 세는 방식으로, 이를 통해 우승 가능성을 판단합니다.
• 자료구조:
  • 기본 정수 변수: cuCnt와 dpCnt를 사용하여 U/C와 D/P의 개수를 저장합니다.
  • 문자열 조작: String.substring을 사용하여 각 문자를 추출합니다. 그러나 이 방식은 비효율적일 수 있습니다.