[문자열/백준] 2607번 : 비슷한 단어

- 문제 : https://www.acmicpc.net/problem/2607

 

문제 이해 

- 단어 구성이 첫 번째 단어와 완전히 일치하거나 아니면 하나씩만 차이나는 단어의 개수를 반환하는 문제다.

 

- 딕셔너리를 이용해 첫 번째 단어와의 각 알파벳 개수 차이를 구한 뒤 딕셔너리 값이 0, 1, -1인 알파벳의 정보를 기록한다.

  1. 만약 딕셔너리 값이 모두 0이라면 두 단어의 구성이 일치(알파벳 종류, 개수)하는 것이므로 바로 정답 케이스에 포함된다.

  2. 여기서 주의해야하는데, 딕셔너리 값이 -1, 1인 알파벳의 개수를 세는데 각 숫자(1, -1) 합이 2개 이하이거나 각 숫자 값이 2이하인 경우도 연산 한번(알파벳 바꾸기 or 빼기 or 추가하기)을 통해서 첫 번째 단어로 바꿀 수 있으므로 정답 케이스에 포함된다.

 

- 풀이에서는 위 2번의 케이스를 만족하지 않는 것들을 거르는 방식으로 진행했다. 1번까지는 생각했는데 2번 케이스가 잘 되지 않아서 꽤 헤맸던 문제다. 

 

- 추가로 주의해야할 것은 첫 번째 단어와의 길이 차이가 2 이상이 나는 경우는 답이 될 수 없으므로 바로 넘겨줘야 한다. 

 

풀이 로직

- 입력 값 중에 첫번째 값은 따로 first, first_length, dic으로 입력 받는다

- 나머지 n - 1 개의 입력값을 받은 후, 단어의 길이(length)와 단어 구성을 딕셔너리(temp)에 저장한다.

- 길이 차이가 2 이상인 경우는 그냥 넘어가도록 한다. 

if first_length > length + 1 or first_length < length - 1:
        continue

 

- 두 단어의 딕셔너리를 subtract 해준 뒤 결과를 temp에 저장한다. (temp.subtrac(dic)하면 temp에 결과가 저장된다)

  이제 temp는 {'A' : 0, 'B': -1, ,,,}의 형태를 띤다 

- temp를 탐색하면서 값이 0, 1, -1인 key의 개수를 zero, one, minus_one에 저장한다. 이렇게 저장한 변수값으로 정답여부를 판별할 것이다.

- 만약 0, -1, 1 이 아닌 다른 값이 딕셔너리에 존재한다면 조건을 만족하지 않는 단어이므로 flag = False 처리를 해준 뒤 탐색을 break 한다.

    temp.subtract(dic)
    zero, one, minus_one = 0, 0, 0
    flag = True
    for each in temp.keys():
        # 다 0으로 이루어져 있거나, 나머지 0이고, 1이나 -1이 하나만 있으면 정답
        if temp[each] == 0:
            zero += 1
        elif temp[each] == 1:
            one += 1
        elif temp[each] == -1:
            minus_one += 1
        else:
            flag = False
            break

 

- 탐색이 끝난 후에는 one과 minus_one 변수 값을 기준으로 만족하지 않는 경우에 flag = False 처리를 한다.

    if one + minus_one > 2:
        flag = False
    if one > 2 or minus_one > 2:
        flag = False

 

- flag == True인 경우에만 개수를 센 후 마지막에 출력 해주면 된다.

    if flag :
        answer += 1

 

정답 풀이 

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

n = int(input())
first = input()
first_length = len(first)
dic = Counter(first) # 첫 번째 단어 구성

answer = 0
for _ in range(n - 1):
    name = input()
    length = len(name)
    temp = Counter(name)
    
    if first_length > length + 1 or first_length < length - 1:
        continue
    
    temp.subtract(dic)
    zero, one, minus_one = 0, 0, 0
    flag = True
    for each in temp.keys():
        # 다 0으로 이루어져 있거나, 나머지 0이고, 1이나 -1이 하나만 있으면 정답
        if temp[each] == 0:
            zero += 1
        elif temp[each] == 1:
            one += 1
        elif temp[each] == -1:
            minus_one += 1
        else:
            flag = False
            break
            
    if one + minus_one > 2:
        flag = False
    if one > 2 or minus_one > 2:
        flag = False
        
    if flag :
        answer += 1
        
print(answer)

 

- 참고한 블로그 : 백준 2608 비슷한 단어 - 파이썬