BOJ 7181 - Mõttemeister

문제

BOJ 7181 - Mõttemeister

4자리 숫자로 이루어진 비밀번호 맞추기 게임이다. 비밀번호 A와 추측 B가 주어질 때, 두 가지 점수를 계산한다. 첫 번째 점수는 순서에 상관없이 A와 B에 공통으로 존재하는 숫자의 수(중복 고려), 두 번째 점수는 같은 위치에 같은 숫자가 있는 개수이다. Bull and Cow 게임과 유사한 구조다.

입력

첫째 줄에 비밀번호 A(4자리 숫자 문자열)가 주어진다. 둘째 줄에 추측 수 N이 주어진다. 이후 N줄에 걸쳐 추측 B가 주어진다.

출력

각 추측 B에 대해 cc ccc를 출력한다. cc는 공통 숫자 수(순서 무관), ccc는 정확히 위치까지 일치하는 수이다.

예제

풀이

빈도 배열을 이용해 공통 숫자 수를 계산하고, 직접 비교로 위치 일치 수를 구한다.

1. 비밀번호 A를 읽은 뒤 추측 수 N을 읽는다.
2. 각 추측 B에 대해:
   • c[0~9] 배열에 B의 각 숫자 빈도를 기록한다.
   • A의 각 자리를 순회하며 c[A[j]-'0'] > 0이면 cc를 증가시키고 해당 빈도를 1 감소시킨다.
   • A와 B의 같은 위치 자리를 직접 비교하여 ccc를 계산한다.
3. cc와 ccc를 출력한다.

핵심 아이디어: 공통 숫자 수(cc)를 구할 때 단순 비교가 아닌 빈도 배열을 사용해야 중복 숫자를 올바르게 처리할 수 있다. 예를 들어 A=1122, B=2211이면 cc=4이어야 한다. ccc는 별도로 직접 위치 비교로 구한다.

코드

#include <cstdio>
 
int N;
char A[5], B[5];
int main(void)
{
  scanf("%s\n%d\n", A, &N);
  for (int i = 0; i < N; ++i)
  {
    scanf("%s", B);
 
    int c[10];
    for (int j = 0; j < 10; ++j)
      c[j] = 0;
    for (int j = 0; j < 4; ++j)
      c[B[j] - '0']++;
    int cc = 0;
    for (int j = 0; j < 4; ++j)
    {
      if (c[A[j] - '0'] <= 0)
        continue;
      c[A[j] - '0']--;
      cc++;
    }
 
    int ccc = 0;
    for (int j = 0; j < 4; ++j)
    {
      if (A[j] == B[j])
        ccc++;
    }
 
    printf("%d %d\n", cc, ccc);
  }
 
  return 0;
}

복잡도

• 시간: O(N) — N번의 추측, 각 추측마다 O(1) (4자리 고정)
• 공간: O(1) — 크기 10의 빈도 배열 (상수)