2607. [Python]비슷한 단어

1. 문제

 

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

2607번: 비슷한 단어

 

2. 접근 방법

 

• 시간 제한: 1초
• 메모리 제한: 128MB
• 구현

 

3. 파이썬 코드

 

import copy

N = int(input())

word_list = []
answer = 0
# 단어들을 리스트에 저장
for _ in range(N):
    word_list.append(input())
# 첫번째 단어의 갯수를 세기위한 딕셔너리
word_dict = {}
# 단어의 길이
word_length = len(word_list[0])
# 첫번째 단어를 딕셔너리에 갯수 저장
for i in word_list[0]:
    if i in word_dict:
        word_dict[i] += 1
    else:
        word_dict[i] = 1
# 첫번째 이후 단어들 반복
for j in word_list[1:]:
    # 각 단어를 반복할때마다 deepcopy를 이용해 딕셔너리 복사
    check_dict = copy.deepcopy(word_dict)
    # 각 단어의 길이
    check_length = len(j)
    # 딕셔너리랑 단어가 몇개나 다른지 확인
    check_cnt = 0
    # value 값에서 단어가 있으면 몇개가 남았는지 혹은 더 많은지 체크하기 위한 변수
    check_num = 0
    # 단어의 갯수 합
    total = 0
    # 최대 1개까지 많거나 적어야 하지만 1개가 넘어가면 체크해줄 변수
    flag = False
    # 각 단어의 값들을 반복하며 딕셔너리에 존재하면 -1 아니면 check_cnt 증가
    for k in j:
        if k in check_dict:
            check_dict[k] -= 1
        else:
            check_cnt += 1
    # 계산이 끝난 딕셔너리의 value 값들을 반복하며 v 값이 0 미만 초과 인 경우 체크
    # 또 -1 미만 1 초과인 경우 flag 를 True로 변경
    # 그리고 계산하며 total 값을 구해준다.
    for v in check_dict.values():
        if v < 0 or v > 0:
            check_num += 1
        if v < -1 or v > 1:
            flag = True
        total += v
    # 기준 단어와 순회하는 단어의 길이가 같은 경우 1개 작은 경우 1개 많은 경우 각각 나눠서 조건식
    if check_length == word_length:
        # 같은 경우는 조건이 많이 붙는데 단어를 바꿀 수 있기 때문에 조건을 많이 설정했다.
        # 길이가 같으므로 모든 값이 딕셔너리에 존재하는 경우, 딕셔너리에 모든 값이 존재하지만 한개가 다른 경우, 딕셔너리에 값이 있지만 1개의 값만 없는 경우로 나눠서 조건을 설정했다.
        if (check_num == 1 and check_cnt == 1) or (check_num == 0 and check_cnt == 0) or (check_num == 2 and check_cnt == 0 and total == 0 and flag == False):
            answer += 1
    # 반복하는 단어의 길이가 기준이 되는 단어보다 한개 더 긴 경우
    elif check_length - 1 == word_length:
        # 딕셔너리 값을 모두 0으로 만들고 딕셔너리에 없는 단어가 1개 존재하는 경우와 딕셔너리에 값이 모두 존재하여 value 값이 -1이 되고 딕셔너리 외의 값이 존재하지 않는 경우 두개 이다.
        if (check_num == 0 and check_cnt == 1) or (check_num == 1 and check_cnt == 0):
            answer += 1
    # 반복하는 단어의 길이가 기준이 되는 단어보다 한개 더 작은 경우
    elif check_length + 1 == word_length:
        # 딕셔너리에 모든 단어가 존재하고 딕셔너리 값이 남아있는 경우 
        if check_num == 1 and check_cnt == 0:
            answer += 1
print(answer)

 

4. 문제를 풀고난 후 생각

 

• 기준이 되는 문자를 가지고 여러 조건을 거쳐서 비슷한 단어를 찾는 문제이다.
• 반복문 마다 딕셔너리를 deepcopy를 통해서 깊은 복사를 진행해서 딕셔너리 간의 주소값을 변경해줬다.
• 기준이 되는 문자와 길이가 같은경우, 기준 문자보다 1개가 많은 경우, 기준 문자보다 1개가 적은 경우 세가지로 나눠서 생각해야한다.
• 기준 문자보다 1개가 적은 경우는 기존의 문자를 딕셔너리로 생성하여 개수를 파악한 후 1개 적은 문자를 딕셔너리에 넣어서 값이 있으면 -1 을 해주는 식으로 합이 1이 나오면 정답이라고 체크하면 되서 매우 간단하게 조건을 설정했다.
• 기준 문자보대 1개가 많은 경우는 조건을 2개 생각했으며 위에서 구한 방식과 동일하게 딕셔너리에 존재할 경우 값을 빼주고 대신 GOD 와 GOOD 의 경우 GOD 와 GODL 등을 생각하여 딕셔너리에 값이 -1 이 된 경우와 기준 문자는 모두 들어있고 그 외의 문자가 한개 존재할 경우를 조건식으로 설정해줬다.
• 길이가 같은경우는 조건이 제일 까다로웠다.
  
  1. ABBA 와 AABB 등 모든 값이 같은 경우 딕셔너리 값이 0이 되고 다른 조건변수가 0인 경우를 설정했다.
  2. ABBA 와 AAAB 의 경우를 생각해서 딕셔너리 내부에 값들이 다있어서 A : -1 / B : 1 이 되어 한개의 단어만 바꿔줘도 되는 경우에 조건을 두개를 선언해줬다.
  위와 같은 경우가 되기 위해서는 딕셔너리 값을 계속 빼주고 다른 단어가 있는지 체크해주는 변수를 통해서 value 값이 -1 or 1 인지 체크한 check_num과 check_cnt 값을 통해서 같은 단어인지 판단했다. 여기서 ABBA 와 AAAA 같은 경우를 걸러줘야 하기 때문에 딕셔너리 값이 -1을 넘거나 1을 넘는 경우 flag 라는 변수를 통해서 다른 문자라는 것을 표시해줬다.
  
  
• 이 문제를 풀기 위해서 많은 생각을 진행했으며, 실제로 여러 방식으로 구현을 진행해 봤지만 현재로써 구현할 수 있는 방법은 위의 방법 밖에 없다. 좀 더 시간이 지나고 지식을 쌓고 다시 구현을 해볼 예정이다.

5. 문제를 푸는데 도움이 되는 지식

 

• 구현