파이썬으로 한 번만 등장하는 가장 큰 숫자 찾기

문제 개요

숫자로 이루어진 리스트가 주어졌을 때, 딱 한 번만 등장하는 숫자 중 가장 큰 값을 반환하는 문제입니다. 만약 한 번만 등장하는 요소가 존재하지 않는다면 -1을 반환해야 합니다.

예를 들어, 리스트가 [5, 2, 3, 6, 5, 2, 9, 6, 3]이라면 각 숫자의 등장 횟수를 세었을 때 9만 한 번 나타나므로, 결과값은 9가 됩니다.

해결 접근 방법

이 문제는 해시맵(파이썬의 딕셔너리)을 활용하면 효율적으로 해결할 수 있습니다. 절차는 다음과 같습니다.

• 리스트의 각 요소를 하나씩 확인하면서 딕셔너리에 저장합니다. 해당 요소가 아직 없다면 새 항목을 추가하고, 이미 존재한다면 등장 횟수를 1씩 증가시킵니다.
• 모든 요소를 처리한 후, 딕셔너리를 순회하면서 값(등장 횟수)이 1인 키(숫자)를 찾아 그중 가장 큰 값을 정답으로 반환합니다.

예제 코드 (Python)

더 잘 이해할 수 있도록 다음 구현 예제를 살펴보겠습니다.

class Solution(object):
   def largestUniqueNumber(self, A):
      d = {}
      ans = -1
      for i in A:
         if i not in d:
            d[i] = 1
         else:
            d[i] += 1
      for a, b in d.items():
         if b == 1:
            ans = max(a, ans)
      return ans

ob1 = Solution()
print(ob1.largestUniqueNumber([5, 2, 3, 6, 5, 2, 9, 6, 3]))

입력

[5, 2, 3, 6, 5, 2, 9, 6, 3]

출력

9

복잡도 분석

위 알고리즘은 리스트를 한 번 순회하며 빈도를 계산하고(O(n)), 딕셔너리를 다시 순회하여 조건에 맞는 최댓값을 찾으므로 전체 시간 복잡도는 O(n)입니다. 공간 복잡도 역시 최악의 경우 모든 요소가 서로 다를 수 있으므로 O(n)입니다.