문제 개요
숫자로 이루어진 리스트 nums가 주어졌다고 가정해 보겠습니다. 우리가 구해야 할 것은 리스트 안의 모든 숫자 쌍을 이어 붙인(concatenation) 값들의 총합입니다. 이때 쌍 (i, j)와 쌍 (j, i)는 순서가 다르므로 서로 다른 조합으로 간주합니다.
예를 들어 입력이 nums = [5, 3]이라면 결과는 176이 됩니다. 만들 수 있는 모든 연결 조합은 다음과 같습니다.
- (nums[0], nums[0]) → 5와 5를 이어붙임 → 55
- (nums[0], nums[1]) → 5와 3을 이어붙임 → 53
- (nums[1], nums[0]) → 3과 5를 이어붙임 → 35
- (nums[1], nums[1]) → 3과 3을 이어붙임 → 33
따라서 최종 합은 55 + 53 + 35 + 33 = 176입니다.
풀이 접근 방법
이 문제는 모든 쌍에 대해 문자열로 변환한 뒤 이어붙이고 다시 정수로 바꾸는 방식으로 해결할 수 있습니다. 다만 동일한 숫자가 여러 번 등장할 경우 같은 계산을 반복하게 되므로, 메모이제이션(memoization)을 활용해 이미 계산한 값을 저장하고 재사용하면 효율성을 크게 높일 수 있습니다.
전체 로직을 의사코드로 표현하면 다음과 같습니다.
memo := 새로운 맵(딕셔너리)
nums1 := nums
temp := 0
c := nums1의 모든 요소의 합
a := nums의 크기
for i in range 0 to a:
if nums[i] == 0:
temp := temp + c
else:
if nums[i]가 memo에 존재하면:
temp := temp + memo[nums[i]]
else:
b := 0
for j in range 0 to a:
b := b + int(nums[i]를 nums1[j]에 이어붙인 값)
memo[nums[i]] := b
temp := temp + memo[nums[i]]
return temp여기서 한 가지 눈여겨볼 부분은 nums[i]가 0일 때의 처리입니다. 0은 어떤 숫자 뒤에 이어 붙여도 자릿수에 영향을 주지 않으므로, 리스트 전체 합 c를 그대로 더하는 방식으로 간단히 처리할 수 있습니다.
파이썬 구현 예제
위 로직을 실제 파이썬 코드로 구현하면 다음과 같습니다.
class Solution:
def solve(self, nums):
memo = {}
nums1 = nums
temp = 0
c = sum(nums1)
a = len(nums)
for i in range(a):
if nums[i] == 0:
temp += c
else:
if nums[i] in memo:
temp += memo[nums[i]]
else:
b = 0
for j in range(a):
b += int(str(nums[i]) + str(nums1[j]))
memo[nums[i]] = b
temp += memo[nums[i]]
return temp
ob = Solution()
nums = [5, 3]
print(ob.solve(nums))실행 결과
입력:
[5, 3]
출력:
176
정리
이 풀이의 시간 복잡도는 중복 값이 없을 경우 O(n²)이며, 메모이제이션 덕분에 동일한 숫자가 반복적으로 등장하는 리스트에서도 불필요한 재계산 없이 빠르게 결과를 얻을 수 있습니다. 문자열 결합과 딕셔너리 캐싱을 함께 활용하면 이처럼 직관적이면서도 효율적인 해결이 가능합니다.