2607. 비슷한 단어

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

2607번: 비슷한 단어

이해

• 문자열 탐색을 통한 완전탐색 구현 문제
• 해당 단어를 탐색하여 개수를 센 후, 이를 비교해도 시간이 충분하다.(O(1,000,000))

구현

1.  각 단어별 구성하고 있는 단어와 그 개수를 저장할 dictionary 생성(편의를 위한 defaultdict 사용)
2.  단어별 구성 단어와 개수를 저장
3.  단어별 구성 단어 개수에서 기준 단어 구성 단어의 개수를 빼서 개수를 재구성(아래와 같이 표현)
   
   1. 해당 단어가 n개 존재 →  n
   2. 기준 단어와 비교 시 단어가 m개 없음 →  -m
4.  기준 단어와의 차이가 절댓값이 2보다 크지 않고, 그 합이 1보다 작을 때만 개수 Check!

코드

# 2607 비슷한 단어
import sys
from collections import defaultdict
input = sys.stdin.readline


def solution(N:int, words:list) -> int:
    cnt = 0
    # 단어 개수를 저장할 dict 리스트 생성
    word = [defaultdict(int) for _ in range(N)]
    
    # 단어 정보 저장
    for i in range(N):
        for w in words[i]:
            word[i][w] += 1
    # 1. 해당 단어에서 기준 단어를 개수만큼 뺌
    # 2. 해당 단어의 개수가 2보다 작으면서, 개수를 모두 더 했을 때 절댓값이
    # 1보다 작으면 카운트
    for i in range(1, N):
        inw = 0
        absi = 0
        for j in word[0].keys():
            word[i][j] -= word[0][j]
        for j in word[i].values():
            inw += j
            absi += abs(j)
            if absi > 2:
                break
        else:
            if abs(inw) <= 1:
                cnt += 1

    return cnt 



if __name__ == "__main__":
    N = int(input())
    print(solution(N, [input().strip() for _ in range(N)]))