파이썬으로 K와 -K가 동시에 존재하는 최댓값 찾기

문제 개요

숫자로 이루어진 리스트 nums가 주어졌을 때, 어떤 수 k와 그 음수인 -k가 모두 리스트 안에 존재하는 경우 중 가장 큰 k를 찾는 것이 이번 문제의 목표입니다. 만약 그러한 조건을 만족하는 원소가 하나도 없다면 -1을 반환해야 합니다.

예를 들어, 입력이 [-5, 2, 9, -6, 5, -9]라면 9와 -9가 모두 존재하므로 정답은 9가 됩니다.

해결 접근 방법

이 문제는 양수와 음수를 분리한 뒤 정렬하여 비교하는 방식으로 효율적으로 풀 수 있습니다. 구체적인 풀이 단계는 다음과 같습니다.

• L1 := nums에서 0과 양수만 담은 리스트
• L2 := nums에서 0과 음수만 담은 리스트
• L1을 내림차순으로 정렬
• L2를 오름차순으로 정렬
• L1의 각 원소 i에 대해:
  • L2의 각 원소 j에 대해:
    • i + j == 0이면 i를 반환 (조건을 만족하는 최댓값)
  • i + j > 0이면 내부 반복문을 종료하고 다음 i로 진행
• 모든 탐색 후에도 조건을 만족하는 값이 없으면 -1 반환

양수 리스트는 내림차순, 음수 리스트는 오름차순으로 정렬했기 때문에 각 양수에 대해 합이 0이 되는 짝을 빠르게 찾을 수 있으며, 합이 양수가 되는 순간 더 이상 탐색할 필요가 없으므로 불필요한 연산을 줄일 수 있습니다.

구현 예제

위 로직을 파이썬 코드로 구현하면 다음과 같습니다.

class Solution:
   def solve(self, nums):
      L1=[i for i in nums if i>=0]
      L2=[i for i in nums if i<=0]
      L1.sort(reverse=True)
      L2.sort()
      for i in L1:
         for j in L2:
            if i+j==0:
               return i
            elif i+j>0:
               break
      return -1
ob = Solution()
nums = [-5, 2, 9, -6, 5, -9]
print(ob.solve(nums))

입력

[-5, 2, 9, -6, 5, -9]

출력

9

마무리

이 풀이는 리스트를 두 번 순회하며 짝을 찾는 방식으로, 최악의 경우 시간 복잡도는 O(n²)입니다. 참고로 집합(set)을 활용하면 각 양수 x에 대해 -x의 존재 여부를 O(1)에 확인할 수 있어 O(n) 시간에 해결할 수 있는 더 효율적인 대안도 있습니다. 하지만 정렬 기반 접근법은 정렬된 데이터를 활용하는 사고방식을 연습하기에 좋은 예제입니다.