BOJ | 2607 - 비슷한 단어 (python)

🪞 비슷한 단어

문자열 문제

 

 

---

✏️ 문제

영문 알파벳 대문자로 이루어진 두 단어가 다음의 두 가지 조건을 만족하면 같은 구성을 갖는다고 말한다.

1. 두 개의 단어가 같은 종류의 문자로 이루어져 있다.
2. 같은 문자는 같은 개수 만큼 있다.

예를 들어 "DOG"와 "GOD"은 둘 다 'D', 'G', 'O' 세 종류의 문자로 이루어져 있으며 양쪽 모두 'D', 'G', 'O' 가 하나씩 있으므로 이 둘은 같은 구성을 갖는다. 하지만 "GOD"과 "GOOD"의 경우 "GOD"에는 'O'가 하나, "GOOD"에는 'O'가 두 개 있으므로 이 둘은 다른 구성을 갖는다.

두 단어가 같은 구성을 갖는 경우, 또는 한 단어에서 한 문자를 더하거나, 빼거나, 하나의 문자를 다른 문자로 바꾸어 나머지 한 단어와 같은 구성을 갖게 되는 경우에 이들 두 단어를 서로 비슷한 단어라고 한다.

예를 들어 "DOG"와 "GOD"은 같은 구성을 가지므로 이 둘은 비슷한 단어이다. 또한 "GOD"에서 'O'를 하나 추가하면 "GOOD" 과 같은 구성을 갖게 되므로 이 둘 또한 비슷한 단어이다. 하지만 "DOG"에서 하나의 문자를 더하거나, 빼거나, 바꾸어도 "DOLL"과 같은 구성이 되지는 않으므로 "DOG"과 "DOLL"은 비슷한 단어가 아니다.

입력으로 여러 개의 서로 다른 단어가 주어질 때, 첫 번째 단어와 비슷한 단어가 모두 몇 개인지 찾아 출력하는 프로그램을 작성하시오.

 

 

입력

첫째 줄에는 단어의 개수가 주어지고 둘째 줄부터는 한 줄에 하나씩 단어가 주어진다. 모든 단어는 영문 알파벳 대문자로 이루어져 있다. 단어의 개수는 100개 이하이며, 각 단어의 길이는 10 이하이다.

 

출력

입력으로 주어진 첫 번째 단어와 비슷한 단어가 몇 개인지 첫째 줄에 출력한다.

 

 

---

💡 해결방법

12%에서 계속 틀려서 의문이었던 문제••• 맞왜틀? 이라고 계속 생각했다.

문제를 이해하기가 조금 어려울 수 있다고 생각한다.

 

문제를 간단하게 정리해보면 다음과 같다.

1. 같은 구성을 갖는 경우 - 같은 종류 + 같은 개수
2. 한 문자를 더하거나, 빼거나, 하나의 문자를 다른 문자로 바꾸어서 같은 구성

일 때 비슷한 문자라고 하므로, 첫번째 문자와 나머지 문자를 비교해서 비슷한 문자를 찾는 문제이다.

 

문제를 해석해서 생각한건 비교하는 문자열의 길이는 첫번째 문자의 길이와 같거나, 1보다 작거나 커야한다.

이후 비교해서 비교하는 문자열에서 첫번째 문자에 있는 것을 다 삭제하고 남은 문자를 비교하는 것이다.

 

예시로 입력에서 첫번째 문자열이 'DOG'이고 비교할 문자열이 'GOOD' 일 때,

비교할 문자열에서 'D', 'O', 'G'를 지우면 'O'만 남게된다.

'O'를 빼면 'DOG'와 같은 구성을 갖게 되므로 비슷한 문자라고 할 수 있다.

 

즉 남은 문자가 1개이거나 0개 일때 비슷한 문자열이 되는 것이다.

 

⭐️ 질문 게시판에 반례가 많으니 참고해보자!

나의 경우 질문 게시판에 있는 반례가 전부 다 맞았는데 계속 안되서 헤맸다..

나처럼 12%에서 틀리는 사람들은 아래 반례를 돌려보도록 하자

#출력
2
DOG
OL

#답
0

 

계속 틀렸던 이유는 비교할 문자의 길이가 첫번째 문자의 길이보다 1 작을 때 반례를 고려하지 않았다.

만약 첫번째 문자의 길이보다 1 작을때는 남아있는 문자의 길이가 없어야 한다.

 

첫번째 문자가 'DOG' 이고 비교할 문자가 'DO' 일 때 D와 O가 모두 삭제되어야 한다.

위와 같은 반례는 L은 삭제되지 않고 남아있기 때문에 남아있는 문자열의 길이가 1이 될것이다.

 

 

👩🏻‍💻 소스코드

# 2607 : 비슷한 단어

import sys
input = sys.stdin.readline

N = int(input())
string = []
cnt = 0

for _ in range(N):
    string.append(input().strip())

s1 = string[0]
l = len(s1)

for i in range(1, N):
    s2 = list(string[i])

    if len(s2) == l-1:
        for s in s1:
            if s in s2:
                s2.remove(s)
        if len(s2) == 0:
            cnt += 1

    if l <= len(s2) <= l+1:
        for s in s1:
            if s in s2:
                s2.remove(s)
        if len(s2) == 0 or len(s2) == 1:
            cnt += 1

print(cnt)

 

---

 

 

2607번: 비슷한 단어