Leetcode 17번 문제 풀이

개요

Leetcode 에서 알고리즘 문제를 풀고 배운 내용을 정리하기 위해 작성하였습니다.

 

문제 : 17. Letter Combinations of a Phone Number

주어진 번호에 해당하는 문자들을 조합해서 나올 수 있는 모든 문자들을 출력하기
https://leetcode.com/problems/letter-combinations-of-a-phone-number/

 

풀이

이 문제는 생각보다 간단한 풀이로 풀 수 있다.

 

문자열이 두개 주어지는 다음 경우를 보자.

 

위 그림처럼 abc, def 2개의 문자열을 조합해 결과를 출력하면 ad, ae, af ... cf 까지 총 9개가 나온다. 이는 두 문자열을 이중 for loop 로 조합해서 만들 수 있는데 이를 응용하여 다른 문자열들도 조합하는 것이 포인트다.

 

만약 abc, def, ghi 3개의 문자열이 주어지면 몇 개의 조합이 나오는지 보자.

 

위 그림처럼 총 27개의 문자열의 조합이 나온다. 어떻게 하면 매번 달라지는 입력값에 따라 알맞은 문자열을 출력할 수 있을까?

 

우리가 맨 처음 계산했던 문자열 2개를 조합한 결과를 보자. 만약 여기에 ghi 를 쪼개서 각각 더해준다면?

 

ad + g = adg,

ad + h = adh,

ad + i = adi,

....

cf + i = cfi

 

총 27개의 조합이 위 결과와 같이 나온다, 즉

 

과 같이 되는 것이고 이렇게 앞서 계산된 결과와 이후 문자열을 조합해주면 우리가 원하는 결과를 얻을 수 있다. 그럼 이것을 코드로 옮기면 어떻게 할 수 있는가?

 

abc, def 를 조합한 문자열을 얻으려면 이중 루프를 돌면 된다.

 

ad, ae, af ... cf 와 def 를 조합한 문자열을 얻으려면 이중 루프를 돌면 된다.

 

즉 [앞서 구한 결과] 와 [새로운 문자열] 을 이중 루프를 통해 정답을 구할 수 있다.

이렇게 되면 이중 루프를 수행하는 서브 루틴 함수를 따로 만들고, 여기에 배열들을 인자로 넣어주어 결과값을 받도록 만들면 된다.

 

만약 "234" 와 같이 3개의 숫자가 주어지면 2개를 조합한 기존 결과 (ad, ae, af...) 에 누적되도록 이중 for loop를 돌면 된다.

코드

 

• 이중 루프 작업을 하는 함수를 twoDigitAdd 서브 루틴으로 만들었다. (자주 반복되는 로직을 함수로 만든 것을 서브 루틴이라고도 부름)
  
  • twoDigitAdd 서브루틴은 두개의 배열을 인자로 받고, 이중 루프를 돌면서 두 문자열들을 조합한 새로운 문자열들을 digitArr 배열에 대입한다.
  • 루프가 끝나면 배열을 반환한다.
• 입력값이 "23" 과 같이 주어지므로 이를 phoneNumber 배열 인덱스와 일치시켜서 사용하기 위해 각각을 -2 하여 배열에 저장한다 
  • ex) digits : "23" -> digits2Idx : [0, 1]
• 입력값에 따른 특정 배열들만 사용하기 위해 임시 배열을 만들어 앞서 만든 배열을 이용해 초기화한다.
  • 만약 입력값이 "29" 면 [a,b,c] 와 [w,x,y,z] 배열만 사용함
• previousArr 배열을 editedPhoneNum 배열의 최초값으로 초기화해준다.
• 주어진 숫자만큼 루프를 돈다. 이 때 previousArr 최초값과 조합을 할 배열은 0번째 다음 인덱스인 1번째 배열이다. 그러므로 i는 1부터 시작한다.
  
  • 반환값을 받은 previousArr 배열은 이 값을 저장한다. 그리고 다시 twoDigitAdd 서브루틴을 호출하여 결과를 받는다.
  • 루프가 끝나면 모든 문자열에 대해서 조합한 것이므로 이를 출력한다.

 

소감

이중 루프로 값을 구하는 것은 "23" 같이 두개 숫자만 주어질 때 가능한 것이라고 착각하여 해당 풀이를 생각하지 못하였다. 대신 문자열이 나오는 형태가 논리 회로와 얼핏 비슷해 보여 carry 계산기를 만드는 데 착안하여 풀면 되지 않을까 라고 생각해서 약 3일간 고민을 하였는데, 인덱스 처리가 굉장히 복잡했다. 그래서 이렇게 설계해서 푸는 게 어찌보면 답이 안되는 것을 갖고 푼다고 생각하여 다른 사람들 풀이를 보고 해결했는데 굉장히 허무했다. 어찌보면 이렇게 쉬운 풀이를 생각지 못한 것이 어처구니 없기도 하고, 그 방법에 대해서 '당연히 안될거야' 는 식으로 얕게 생각하고 깊게 고민하지 않은 것이 몇일 간 풀지 못하게 한 원인이었다. 3*3= 9, 3*3*3 = 27 과 같이 수학적으로도 쉽게 증명이 되는 풀이인데 깊게 생각하지 않고 푼 것이 아쉬운 문제다. 다음부턴 한 가지 풀이에 몰두하지 말고 시간이 걸려도 안 풀리면 다른 풀이 방법으로 돌아가서 하나하나 주의깊게 생각하여 방법을 찾도록 하자.

 

출처

https://www.youtube.com/watch?v=deKgPoAHODE