백준) 유사 라임 게임

문제) https://www.acmicpc.net/problem/24431

이 문제는 팀내 코드 리뷰를 듣고 난 후 잘 못 된 접근을 하게 된 경우라 포스팅을 하게 되었다.

 

해당 문제 테스트 케이스를 T만 큼 준 후 n, L, F와 n개의 L 크기만의 문자열 준 후 뒤에서 F 만큼 같은 쌍이 몇개인지를 출력하는 문제 였다

 

처음 문제를 접하고 진행 방향을 모든 가짓 수를 통하여 최대 쌍을 구해야 되는 것으로 파악 후 DFS 방식으로 문제를 접근 하게 되었다

# 유사 라임 게임
# https://www.acmicpc.net/problem/24431
import sys
from collections import Counter
T = int(sys.stdin.readline().strip())
for _ in range(T):
    n, L, F = map(int, sys.stdin.readline().split())
    W = list(map(str, sys.stdin.readline().split()))
    max_v = 0
    check_dict = {}
    visited = [-1] * n

    def dfs(idx, count=0 ,check=[]):
        global max_v
        if idx > n or max_v == n // 2:
            return

        if len(check) > 1:
            w1, w2 = check[-2], check[-1]
            if check_dict.get(w1 + w2):
                count += check_dict[w1 + w2]
            else:
                add_count = 0
                b = Counter(w1)
                c = b - Counter(w2)
                if sum(c.values()) <= L - F:
                    count += 1
                    add_count = 1
                check_dict[w1 + w2] = add_count
                check_dict[w2 + w1] = add_count
                max_v = max(count, max_v)
            if len(check) == n: return


        for i, word in enumerate(W):
            if visited[i] == -1:
                visited[i] = 0
                check.append(word)
                dfs(idx + 1, count, check)
                check.pop()
                visited[i] = -1

    dfs(0)
    sys.stdout.write(f'{max_v}\n')

위의 코드는 DFS 방식으로 풀었는데 문제는 이것을 사용 했을 때 시간초과가 난다

 

그렇다면 DFS 방식이 아닌 다른 방식이 있다는 건데 이 방식을 찾기가 어려웠고 결국은 현재 실력으로는 문제를 풀지 못하게 되었다.

 

팀내 숙제로 주어졌던 문제였고 팀내 인원 중 한명이 풀었는데 풀이 방식이 나랑은 다른 방식이였다.

 

풀이 방식을 전체 문자를 Counter 함수를 이용하여 뒤에서 F만큼의 문자열 가져와 그 문자들의 수를 체크 한 후 쌍이 되어 야 하므로 2로 나눈 값을 변수 누적 시킨 후 누적값을 출려 해주면 되는 풀리게 되는 문제였다

 

정답 코드!!

# 재일님 코드
import sys
from collections import Counter

T = int(sys.stdin.readline())

for _ in range(T):
    n, L, F = map(int, sys.stdin.readline().split())
    W = list(sys.stdin.readline().split())
    F_list = []
    answer = 0
    for w in W:
        F_list.append(w[-F:])
    c_list = Counter(F_list)
    for v in c_list.values():
        answer += v//2
    print(result)

 

해당 코드는 분석이 가능하며 이해도 같이 된 상태이지만 아직 나의 코드는 아닌 거 같아 다실 풀 문제 리스트에 추가 후 다시 풀어야 할 거 같다.