백준 34803번 - '문자열 로또' (PYTHON 풀이)

문제:

 

첫째 줄에 문자열의 길이와 문자열 개수를 입력받고, 두번째 줄부터 모든 문자열을 입력받는다.

그리고 마지막 줄에 뽑을 문자열의 개수를 입력받는다.

 

위의 예제로 설명하자면 마지막 줄은 2이다. 이는 문자열 전체를 두 자리씩 잘랐을 때의 모든 경우의 수를 계산해서 어떤 문자 2개를 뽑았을 때 가장 높은 점수를 받을 수 있는지 파악한 뒤 해당 문자열을 기준으로 점수를 계산하면 되는 문제이다.

 

풀이:

L, N = map(int,input().split())
li = []

for i in range(N):
    li.append(input())

K = int(input())

new_li = set()

for j in li:
    for q in range(L-K+1):
        new_li.add(j[q:q+K])

max_count = 0

for candi in new_li:
    total = 0

    for j in li:
        for q in range(L-K+1):
            if j[q:q+K] == candi:
                total += 1

    if total > max_count:
        max_count = total
print(max_count)

입력 예제에 맞춰 각 변수에 입력받고, 모든 문자열을 li에 넣는다.

그 후 자를 수의 기준인 K를 입력받고, 가능한 모든 길이 K의 부분 문자열을 후보 집합으로 만든다.

각 입력 문자열의 길이는 L이며, 길이 K의 부분 문자열은 시작 위치를 한 칸씩 이동하면서 만들 수 있다. 시작 위치는 0부터 L-K까지 가능하므로 총 L-K+1개의 부분 문자열이 생성된다.

파이썬에서는 s[i:i+K] 형태의 슬라이싱을 사용하면 i번째부터 K글자를 쉽게 추출할 수 있다. 이 과정을 모든 문자열에 대해 수행하고 set에 저장하면 중복을 제거한 후보 문자열 집합을 만들 수 있다.

 

다음 단계에서는 각 후보 문자열이 당첨 문자열이라고 가정했을 때의 점수를 계산한다. 후보 문자열 하나를 선택한 뒤, 모든 입력 문자열을 다시 순회하면서 길이 K의 부분 문자열을 하나씩 비교한다. 만약 현재 부분 문자열이 후보 문자열과 같다면 점수를 1 증가시킨다. 이렇게 모든 문자열에서의 등장 횟수를 합산하면 해당 후보가 당첨일 때의 총 점수가 된다.

 

이 과정을 모든 후보 문자열에 대해 반복하면서 최댓값을 갱신한다. 최종적으로 계산된 최대 등장 횟수가 문제에서 요구하는 답이 된다.