[Week 6] DICTIONARY self review - profitjean
Opened this issue · 0 comments
profitjean commented
DICTIONARY self review
1. 해결 시도 과정
그래프로 표현하고 위상정렬을 통해 문자들의 순서를 구할 수 있을 것이라 생각했습니다. 또한, b->a->b 처럼 사이클이 형성되는 경우도 고려해줘야겠다고 생각했습니다.
2. 작성한 코드와 설명
T = int(input().rstrip())
for _ in range(T):
graph = defaultdict(set)
N = int(input().rstrip())
words = []
visited = {}
for _ in range(N):
words.append(input().rstrip())
# 이전 문자열과 비교하면서 다르다면 그래프에 추가시켜주기
prev = ""
for word in words:
for i in range(min(len(prev), len(word))):
if prev[i] != word[i]:
graph[prev[i]].add(word[i])
visited[prev[i]] = None
visited[word[i]] = None
break
prev = word
3. 막힌 점 및 개선 사항
이후 dfs 구현 이후 역방향으로 reverse 시키는 부분을 구현하지 못했습니다