onlybooks/python-algorithm-interview

'33. 전화 번호 문자 조합' 문제 풀이 문의 (p.338 ~ 340)

opwe37 opened this issue · 1 comments

해당 문제의 코드 중 dfs 부분을 보면 아래와 같은 코드가 있습니다.


# 입력값 자릿수 단위 반복
for i in range(index, len(digits)):
	# 숫자에 해당하는 모든 문자열 반복
	for j in dic[digits[i]]:
		dfs(i+1, path+j)

이 부분에서 가장 바깥에 있는 for문이 왜 필요한지에 대해 문의드립니다.

의문이 드는 사항에 대해 간단하게 예를 들자면 주어지는 입력 digits = '23'이라고 한다면, dfs(0, "")이 호출이 되면, 가장 바깥의 for문 i의 범위는 0 ~ 1입니다. i가 0일 때는 dfs 동작 방식에 따라 len(path) == len(digits)인 상황에 도착하지만, i가 1일 때는 len(path) == len(digits)인 상황에 도착하지 않습니다.

제 생각으로는 가장 바깥의 for문을 없애고 나머지 부분만 아래와 같이 남겨야 한다고 생각됩니다.


# 숫자에 해당하는 모든 문자열 반복
for i in dic[digits[index]]:
	dfs(index+1, path+i)

말씀하신대로 저 부분만 남기면 훨씬 더 효율적인 풀이가 가능하겠네요. 중요한 사항을 지적해주셔서 감사합니다. 그러나 기존의 풀이가 틀린 것은 아니므로 책의 정오표에는 반영하지 않도록 하겠습니다. 다만, 더 효율적인 풀이인 만큼 지적해주신 사항은 이 곳 풀이에 별도로 표기하도록 하겠습니다. 다시 한 번 알려주셔서 감사합니다.