값 n이 주어졌다고 가정해 보겠습니다. 이때 우리는 길이가 n인 모든 거꾸로 된 숫자(upside down number)를 찾아야 합니다. 거꾸로 된 숫자란 숫자를 180도 회전했을 때 원래 모양과 동일하게 보이는 수를 의미합니다.
예를 들어 입력이 n = 2라면 출력은 ['11', '69', '88', '96']이 됩니다.
거꾸로 된 숫자의 조건
180도 회전했을 때 유효한 숫자로 유지되는 숫자는 0, 1, 6, 8, 9뿐입니다. 각 숫자는 회전 시 다음과 같이 대응됩니다.
0 → 0
1 → 1
6 → 9
8 → 8
9 → 6
반면 2, 3, 4, 5, 7은 회전하면 유효한 숫자가 되지 않으므로 사용할 수 없습니다. 또한 일반적인 숫자 표기 규칙상 맨 앞자리에 0이 올 수 없기 때문에, 가장 바깥쪽 자리에는 0을 배치하지 않습니다.
문제 해결 접근 방법
이 문제는 재귀를 활용해 중앙에서부터 바깥쪽으로 대칭 쌍을 추가해 나가는 방식으로 해결할 수 있습니다. 단계별 과정은 다음과 같습니다.
x를 인자로 받는 함수 middle()을 정의합니다.
x가 0이면 빈 문자열 하나를 담은 리스트를 반환합니다.
x가 1이면 요소 0, 1, 8로 구성된 새 리스트를 반환합니다.
ret := 새 리스트로 초기화합니다.
mid := middle(x − 2)를 호출하여 안쪽 부분을 먼저 생성합니다.
mid의 각 요소 m에 대해 다음을 수행합니다.
x가 n과 같지 않으면, 즉 최외곽 자리가 아니면 ("0" + m + "0")을 ret 끝에 삽입합니다.
("1" + m + "1")을 ret 끝에 삽입합니다.
("6" + m + "9")를 ret 끝에 삽입합니다.
("8" + m + "8")을 ret 끝에 삽입합니다.
("9" + m + "6")을 ret 끝에 삽입합니다.
ret을 반환합니다.
메인 메서드에서는 다음과 같이 처리합니다.
n이 0이면 빈 리스트를 반환합니다.
그렇지 않으면 middle(n)의 결과를 정렬하여 반환합니다.
다음 구현을 통해 더 잘 이해해 보겠습니다.
예제 코드
class Solution:
def solve(self, n):
if not n:
return []
def middle(x=n):
if not x:
return [""]
if x == 1:
return list("018")
ret = []
mid = middle(x - 2)
for m in mid:
if x != n:
ret.append("0" + m + "0")
ret.append("1" + m + "1")
ret.append("6" + m + "9")
ret.append("8" + m + "8")
ret.append("9" + m + "6")
return ret
return sorted(middle())
ob = Solution()
print(ob.solve(2))
입력
2
출력
['11', '69', '88', '96']
동작 원리
위 코드는 중앙을 기준으로 재귀적으로 확장하는 구조입니다. n = 2일 경우 먼저 middle(0)이 [""]를 반환하고, 그 결과를 좌우 대칭 쌍으로 감싸면서 "11", "69", "88", "96"이 생성됩니다. 이때 x == n 조건 덕분에 "00"은 제외되어 맨 앞자리에 0이 오는 경우를 자연스럽게 걸러냅니다. 마지막으로 sorted()를 적용해 사전순으로 정렬된 결과를 반환합니다.