[백준/Python] 비슷한 단어 2607

난이도: 실버2

분류: 구현, 문자열

 

key point

  - 비슷한 단어일 조건은, '한 단어를 바꿨을 때 같은 구성인 경우'와 '한 단어만을 추가하거나 제거했을 때 같은 구성인 경우' 이다

  - 두 문자열을 비교했을 때, 한쪽 구성에서 없는 문자의 수를 diff라고 정의 한다면, 양 쪽 둘 다 diff <=1 인 경우가 비슷한 단어인 경우다 

 

 

fst approach (o)

- list에서 in이나 remove를 사용하면 시간이 오래 걸릴까봐 dict를 사용

- 코드 길어짐

from collections import defaultdict
from sys import stdin
input = stdin.readline

def check(w: str):
    d = defaultdict(int)
    for s in w:
        d[s] +=1
    return d

def compare(f_d:defaultdict, w_d: defaultdict):
    # f_d의 원소 수를 w_d에서 빼기
    for fs, fv in f_d.items():
        w_d[fs] -= fv
    # w_d에서 1과 -1의 개수를 파악, 1과 -1 밖의 값이 있다면 False를 return
    plus = 0
    minus = 0
    for wv in w_d.values():
        if wv < -1 or wv > 1:
            return False
        elif wv == 1:
            plus +=1
        elif wv == -1:
            minus +=1
    # plus와 minus가 둘 다 1 이하라면 True
    return True if plus <= 1 and minus <=1 else False

def main():
    n = int(input())
    f = input().strip()
    f_d = check(f)
    # 첫 번째 단어와 비교
    cnt = 0
    for _ in range(n-1):
        w_d = check(input().strip())
        # 비슷한 단어를 체크
        if compare(f_d, w_d):
            cnt +=1
    return cnt

print(main())

 

 

 

sec approach (o)

- 그냥 리스트로 간단하게 풀이

- 오히려 시간복잡도와 코드량에서 훨씬 이득

- time: 40ms, 코드길이: 422B

from sys import stdin
input = stdin.readline

def check(fst:list, word:str):
    fst = fst[:]
    no = 0
    for s in word:
        if s in fst: fst.remove(s)
        else: no +=1
    return True if len(fst) <= 1 and no <=1 else False

def main():
    n = int(input())
    fst = list(input().strip())
    cnt = 0
    for _ in range(n-1):
        cnt += 1 if check(fst, input().strip()) else 0
    return cnt

print(main())