[ BOJ ] 1296 : 팀 이름 정하기 ( BRONZE 1 ) / C, Python

문제

연두는 프로그래밍 대회에 나갈 팀 이름을 정하려고 한다. 미신을 믿는 연두는 이환이에게 공식을 하나 받아왔고, 이 공식을 이용해 우승할 확률이 가장 높은 팀 이름을 찾으려고 한다.

이환이가 만든 공식은 사용하려면 먼저 다음 4가지 변수의 값을 계산해야 한다.

• L = 연두의 이름과 팀 이름에서 등장하는 L의 개수
• O = 연두의 이름과 팀 이름에서 등장하는 O의 개수
• V = 연두의 이름과 팀 이름에서 등장하는 V의 개수
• E = 연두의 이름과 팀 이름에서 등장하는 E의 개수

그 다음, 위에서 구한 변수를 다음 식에 입력하면 팀 이름의 우승할 확률을 구할 수 있다.

((L+O) × (L+V) × (L+E) × (O+V) × (O+E) × (V+E)) mod 100

연두의 영어 이름과 팀 이름 후보 N개가 주어졌을 때, 우승할 확률이 가장 높은 팀 이름을 구해보자. 확률이 가장 높은 팀이 여러가지인 경우 사전 순으로 가장 앞서는 팀 이름이 우승할 확률이 가장 높은 것이다.

입력

첫째 줄에 연두의 영어 이름이 주어진다. 둘째 줄에는 팀 이름 후보의 개수 N이 주어진다. 셋째 줄부터 N개의 줄에 팀 이름이 한 줄에 하나씩 주어진다.

연두의 영어 이름과 팀 이름은 길이는 1보다 크거나 같고, 20보다 작거나 같으며, 알파벳 대문자로만 이루어져 있다. N은 50보다 작거나 같은 자연수이다.

출력

첫째 줄에 우승할 확률이 가장 높은 팀 이름을 출력한다.

풀이 과정

문제에 맞춰 천천히 단계별로 구현한다.

1. 연두의 이름과 팀 이름에서 등장하는 L, O, V, E의 개수를 세서 ((L+O) × (L+V) × (L+E) × (O+V) × (O+E) × (V+E)) mod 100 식을 통해 우승할 확률을 구한다. 

2. 우승할 확률이 가장 높은 순서대로, 우승할 확률이 같다면 팀 이름이 사전 순으로 앞서는 순서대로 정렬한다.

3. 우승할 확률이 가장 높은 팀 이름을 출력한다.

C

#include <stdio.h>
#include <string.h>

typedef struct _TEAM {
    char name[30];
    int winable;
} Team;

int main(void) {
    char search[5] = "LOVE";

    char yeondu[30];
    int yeondu_count[4] = {0,}; // L, O, V, E;
    scanf("%s", yeondu);
    for (int i = 0; i < strlen(yeondu); i++) {
        for (int j = 0; j < 4; j++) {
            if (yeondu[i] == search[j]) {
                yeondu_count[j] += 1;
                break;
            }
        }
    }

    int n;
    Team t[50];

    scanf("%d", &n);
    getchar();
    for (int i = 0; i < n; i++) {
        scanf("%s", t[i].name);
        t[i].winable = 0;
        
        int count[4] = {0,};
        for (int j = 0; j < strlen(t[i].name); j++) {
            for (int k = 0; k < 4; k++) {
                if (t[i].name[j] == search[k]) {
                    count[k] += 1;
                    break;
                }
            }
        }       

        for (int j = 0; j < 3; j++) {
            for (int k = j + 1; k < 4; k++) {
                if (j == 0 && k == 1)
                    t[i].winable = ((yeondu_count[j] + count[j]) + (yeondu_count[k] + count[k]));
                else
                    t[i].winable *= ((yeondu_count[j] + count[j]) + (yeondu_count[k] + count[k]));
            }
        }
        t[i].winable %= 100;
    }

    // Selection Sort
    for (int i = 0; i < n - 1; i++) {
        int max = i;
        for (int j = i + 1; j < n; j++) {
            if (t[max].winable < t[j].winable || (t[max].winable == t[j].winable && strcmp(t[max].name, t[j].name) > 0)) max = j;
        }

        if (max != i) {
            Team tmp = t[max];
            t[max] = t[i];
            t[i] = tmp;
        }
    }

    printf("%s", t[0].name);
    return 0;
}

Python

import sys
input = sys.stdin.readline

yeondu = input().rstrip()
string = 'LOVE'
n = int(input().rstrip())
arr = []
for _ in range(n):
    arr.append(input().rstrip())


max_value = -1
max_name = ""

for a in arr:
    now = 1
    for i in range(3):
        for j in range(i+1,4):
            now *= (yeondu.count(string[i]) + a.count(string[i])) + (yeondu.count(string[j]) + a.count(string[j]))
    now %= 100

    if now > max_value:
        max_value = now
        max_name = a
    elif now == max_value:
        if a == min(max_name, a):
            max_value = now
            max_name = a

print(max_name)