-
카테고리
-
세부 분야
알고리즘 · 자료구조
-
해결 여부
미해결
선생님! (알파코드 DFS)
22.05.06 15:52 작성 조회수 120
0
import sys
input = sys.stdin.readline
# 아스키 : chr(x)
# 0 입력되면 입력 종료
def DFS(L):
global cnt, res
if L == len(num):
if len(res) > len(num):
res = res[2:] # pop, slicing 둘 다 O(N). pop(0)을 2번 하면, 2N이니까 슬라이싱 사용. pop(0)을 O(1)로 하려면 deque사용하면 됨
print("".join(res))
# print(res)
cnt += 1
return
a = int(num[L])
b = int("".join(num[L:L+2]))
if a == 0:
return
if 0 < a < 10:
res.append(chr(a+64))
# res.append(a)
DFS(L+1)
res.pop()
if 9 < b < 27:
res.append(chr(b+64))
# res.append(b)
DFS(L+2)
res.pop()
if __name__ == "__main__":
num = list(str(input()).rstrip())
res = []
cnt = 0
DFS(0)
print(cnt)
- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요! - 먼저 유사한 질문이 있었는지 검색해보세요.
- 서로 예의를 지키며 존중하는 문화를 만들어가요.
- 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요.
강의에 나온 방법 외에
숫자를 1글자, 2글자로 나눠서 트리를 만드는 방법으로 코드를 구현해봤는데 어떤가요...?! 괜찮은가요??!
for문을 이용하지 않고 거의다 조건문으로 굴러가는 코드인데, 시간복잡도 등 차이가 많이 있을까요??
처음으로 정답코드 안보고 구현해본 DFS코드라 선생님이 보시기엔 어떤지가 궁금합니다..!! ㅎㅎ
답변을 작성해보세요.
1
답변 1