Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

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

Open
opwe37 opened this issue Feb 25, 2021 · 1 comment
Open

Comments

@opwe37
Copy link

opwe37 commented Feb 25, 2021

해당 문제의 코드 중 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)

@likejazz
Copy link
Collaborator

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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

2 participants