https://www.acmicpc.net/problem/1296
나의 풀이
from itertools import combinations
import sys
input = sys.stdin.readline
def _score(now_dict, now_name):
score = 1
local_dict = now_dict.copy()
for i in now_name:
if i in ('L','O','V','E'):
if i not in local_dict:
local_dict[i] = 1
else:
local_dict[i] += 1
if len(local_dict) < 3:
return 0
for i in ('L','O','V','E'):
if i not in local_dict:
local_dict[i] = 0
for a, b in combinations(local_dict.values(), 2):
score *= (a + b)
return score % 100
def _team_name(n_name, n_ct):
result_team, result_score = '', 0
team_ct_dict = {}
for i in n_name:
if i in ('L','O','V','E'):
if i not in team_ct_dict:
team_ct_dict[i] = 1
else:
team_ct_dict[i] += 1
for _ in range(n_ct):
name = input().rstrip()
now_score = _score(team_ct_dict, name)
if (now_score > result_score):
result_team, result_score = name, now_score
elif (now_score == result_score):
if (not result_team) or (name < result_team):
result_team = name
return result_team
n_name = input().rstrip()
n_ct = int(input())
print(_team_name(n_name, n_ct))
시간 복잡도
for _ in range(n_ct) : 이름 갯수만큼 순회 ( 선형 시간 복잡도 )
name = input().rstrip()
now_score = _score(team_ct_dict, name) : 각 이름의 점수 계산 함수 ( 선형 시간 복잡도 )
해당 알고리즘 시간 복잡도 : 이차형 시간 복잡도 ( O(n**2) )
