[알고리즘/문자열] 2607번 : 비슷한 단어 - python

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

2607번: 비슷한 단어

 

---

• 문제
• 소요시간: 27분 (실패)

---

• 설계하기(접근방법) 

1. 입력받기

비교할 첫 문자를 입력받는다

 

2. 구현하기

처음에는 전부 구현하다가 시간을 지나치게 많이 사용했다

딕셔너리를 만들어서 알파벳을 하나하나 전부 비교하고

키와 값을 활용해 만드려니 소요가 많이 들었다

 

 

다른 사람의 풀이를 봤다

입력받은 단어의 글자를 활용해서 첫 단어를 지워나가면 쉽게 풀 수 있다

 

즉 DOG가 첫 단어고

입력받은 단어가 GOD면

G 부터 시작해서

O

D를 remove() 메서드를 통해 지워보면 된다

 

만약 완벽하게 지워지면 같은 구성의 단어이다

 

그렇다면 문제의 요구사항인 한 글자를 빼거나 더할 수 있는 케이스는 어떻게 다룰까?

입력받은 단어가 DOG 내에 있는지 확인해보고 있다면

지운다

만약 없다면 cnt += 1을 해준다(이 cnt의 뜻은 첫 단어 내에 없는 글자의 개수로 해석할 수 있다)

만약 이 cnt가 2를 넘어간다면, 그 것은 같은 구성의 단어가 아니라는 점이다

 

입력받은 문자가

GODD혹은

GO인 경우다

 

입력받은 단어로 첫 단어를 다 지우지 못하는 경우가 있을 것이다.

첫 단어의 남은 길이가 1 이하라면

한 글자를 바꿨거나, 같은 알파벳으로 이루어졌지만 개수가 한 개 모자란 경우일 것이다

 

결국 남은 길이가 1 이하일 때와 cnt가 1 이하일 때만 정답이다

 

 

 

3. 출력하기

답 개수를 출력한다

---

• 코드(출력)

n = int(input())
main = list(input())
answer = 0

for i in range(n -1):
    main_compare = main[:]
    word = input()
    cnt = 0
    for j in word:
        if j in main_compare:
            main_compare.remove(j)
        else:
            cnt += 1

    if cnt < 2 and len(main_compare) < 2:
        answer += 1
 
print(answer)

---

• 얻어갈 부분

1. 케이스를 다 나누었을 때 요상하게 복잡해진다면 다른 접근법으로 생각해보자