백준 / python / 1897. 토달기

https://www.acmicpc.net/problem/1897

 

문제 요약

다수의 문자열이 주어졌을 때 처음 주어진 문자열에서 임의의 문자를 한 글자씩 섞어서 만들 수 있는 최장 문자열을 구하시오.

 

 

풀이 요약

1. 문자열 배열을 정렬한다.

2. 문자열 배열을 순환하면서 문자열(A)에서 한 글자를 뺀 문자열이 path 배열에 있는지 확인 후 path 에 그 문자열(A)을 기록한다.

3. 그 문자열(A) 가 ans 보다 길면 ans 에 그 문자열(A)을 입력한다.

4. 문자열을 다 순환하면 ans 를 출력한다.

 

주의사항

brute force 로는 느리다.

for 문 자체가 있으면 아무리 skip 로직을 넣는다 해도 느리다.

만약 6개의 item 이 있다면 그냥 full scan 하는게 3/3 으로 나눠서 for 문 2개 돌면서 skip 로직 넣는 것 보다 빠르다.

예로 아래 두 코드는 각각 56ms / 332ms 이다.

from sys import stdin

input = stdin.readline

d, word = input().split()

words = []

for _ in range(int(d)):
    words.append(input().rstrip())

words.sort(key=lambda x: len(x))

ans = word
path = {word: True}

for word in words:
    l = len(word)
    for i in range(l):
        new_word = word[:i] + word[i + 1 :]

        if new_word in path:
            path[word] = True
            if len(word) > len(ans):
                ans = word

print(ans)

 

from sys import stdin
from collections import deque, defaultdict

input = stdin.readline

d, word = input().split()

words = defaultdict(dict)

for _ in range(int(d)):
    new_word = input().rstrip()
    words[len(new_word)][new_word] = False

q = deque([word])

while q:
    word = q.popleft()
    word_len = len(word)

    try:
        for next_word in words[word_len + 1]:
            if words[word_len + 1][next_word]:
                continue

            for i in range(word_len + 1):
                new_word = next_word[:i] + next_word[i + 1 :]

                if word == new_word:
                    q.append(next_word)
                    words[word_len + 1][next_word] = True
                    break

    except KeyError:
        break

print(word)