[Week 6] DICTIONARY self review - ChaeheeKang-GitHub
Opened this issue · 0 comments
chaeheekang commented
DICTIONARY self review
1. 해결 시도 과정
그래프를 만들어 어느 알파벳이 선행되어야 하는지 해결하고자 하였습니다.
2. 작성한 코드와 설명
def makegraph(word,p):
for j in range(1,N):
i=j-1
l=min(len(word[i]),len(word[j]))
for k in range(l):
if word[i][k]==word[j][k]:
continue
a=ord(word[i][k])-ord('a')
b=ord(word[j][k])-ord('a')
p[a][b]=1
break
def dfs(x):
check[x]=True
for nx in range(26):
if p[x][nx]==1 and not check[nx]:
dfs(nx)
ans.append(x)
def makeResult():
ans.reverse()
for i in range(26):
for j in range(i+1,26):
if p[ans[j]][ans[i]]:
return False
return ans
C=int(input())
for _ in range(C):
N=int(input())
word=[]
ans=[]
p=[[0]*27 for _ in range(27)]
check=[False]*27
for x in range(N):
word.append(input().rstrip())
makegraph(word,p)
for i in range(26):
if check[i]==False:
dfs(i)
if makeResult()==False:
print("INVALID HYPOTHESIS")
else:
ans=list(map(lambda x : chr(ord('a')+x),ans))
ans.reverse()
print(''.join(ans))
3. 막힌 점 및 개선 사항
출력이 의도대로 나오지 않습니다.. 다시 시도해봐야할 것 같습니다.