[코테 연습] 단어 변환 Python
오늘도 뜬뜬 위젼은 뜬뜬 코테 연습을 한다네~
오늘은 오후 내내 인공지능 공부를 쫌 했더니 뿌듯한 하루다 ^>^!
[코테 연습] 네트워크 Python
처음엔 아래와 같이 작성했다. 방문한 노드는 그래프상에서 지워버리고 재귀가 끝났다면 한 네트워크가 생성된 것이니까 +1 테스트 케이스를 무려 9개나 돌렸다 .... def cal(dic, idx, invited): value = di
weejw.tistory.com
저번에 dfs 실패했을 때, 다른 분 블로그에서 본 코드를 공부해서 참고해서 풀었다. 행운의 분~~!! 이 분덕분에 오늘 문제는 무려 30분도 안되서 코드가 작성이 되긴 했다!
문제 설명
두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다.
1. 한 번에 한 개의 알파벳만 바꿀 수 있습니다. 2. words에 있는 단어로만 변환할 수 있습니다.
예를 들어 begin이 hit, target가 cog, words가 [hot,dot,dog,lot,log,cog]라면 hit -> hot -> dot -> dog -> cog와 같이 4단계를 거쳐 변환할 수 있습니다.
두 개의 단어 begin, target과 단어의 집합 words가 매개변수로 주어질 때, 최소 몇 단계의 과정을 거쳐 begin을 target으로 변환할 수 있는지 return 하도록 solution 함수를 작성해주세요.
제한사항
- 각 단어는 알파벳 소문자로만 이루어져 있습니다.
- 각 단어의 길이는 3 이상 10 이하이며 모든 단어의 길이는 같습니다.
- words에는 3개 이상 50개 이하의 단어가 있으며 중복되는 단어는 없습니다.
- begin과 target은 같지 않습니다.
- 변환할 수 없는 경우에는 0를 return 합니다.
첫 번째 시도
minStep = 50
def dfs(currentWord, words, step, target):
if currentWord != target:
wordArr = copy.deepcopy(words)
wordArr.remove(currentWord)
step += 1
for word in wordArr:
if len(set(currentWord) - set(word)) == 1:
dfs(word, wordArr, step, target)
if currentWord == target:
global minStep
minStep = min(minStep, step)
def solution(begin, target, words):
if target not in words:
return 0
for word in words:
if len(set(begin) - set(word)) == 1:
dfs(word, words, 1, target)
return minStep| 테스트 1 〉 | 통과 (0.04ms, 10.9MB) |
| 테스트 2 〉 | 통과 (2.93ms, 10.8MB) |
| 테스트 3 〉 | 실패 (1.58ms, 10.8MB) |
| 테스트 4 〉 | 통과 (0.08ms, 10.7MB) |
| 테스트 5 〉 | 통과 (0.04ms, 10.8MB) |
음,, 그래 그래도!!!!! 으이 ! 4개나 통과하고!
질문 게시판에서 나와 같은 상황이 발생하는 사람을 발견했다. 문제는 단어의 순서를 고려치 않은 코딩이였다. 그 분도 나랑 똑같이 set을 썼다 ㅋㅋㅋ 생각이 다 거기서 거기군,,
그럼 순서를 고려해서 단어를 비교해야 한다.
import copy
minStep = 50
def dfs(currentWord, words, step, target):
if currentWord != target:
wordArr = copy.deepcopy(words)
wordArr.remove(currentWord)
step += 1
for word in wordArr:
compareWord = zip(currentWord, word)
cnt = 0
for twoWord in compareWord:
if twoWord[0] != twoWord[1]:
cnt += 1
if cnt == 1:
dfs(word, wordArr, step, target)
if currentWord == target:
global minStep
minStep = min(minStep, step)
def solution(begin, target, words):
if target not in words:
return 0
for word in words:
compareWord = zip(begin, word)
cnt = 0
for twoWord in compareWord:
if twoWord[0] != twoWord[1]:
cnt += 1
if cnt == 1:
dfs(word, words, 1, target)
return minStep| 테스트 1 〉 | 통과 (0.06ms, 10.8MB) |
| 테스트 2 〉 | 통과 (0.18ms, 10.8MB) |
| 테스트 3 〉 | 통과 (0.58ms, 10.9MB) |
| 테스트 4 〉 | 통과 (0.05ms, 10.8MB) |
| 테스트 5 〉 | 통과 (0.05ms, 10.8MB) |
네트워크를 거진 이틀 내내 풀어서 그런지 이건 30분만에 풀어서 기분 진짜 완전 좋고 막 파티해야하고 ㅠ
파티한다 오늘 광광운다 ㅠ 다른사람들이 보면 뭘 저거가지고 그러겠냐겠다..,, 수치사 꿱 그래도 지원이 잘했어요~
