[Week 6] DICTIONARY self review - ChaeheeKang-GitHub

[chaeheekang]

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. 막힌 점 및 개선 사항

출력이 의도대로 나오지 않습니다.. 다시 시도해봐야할 것 같습니다.