•
문제 설명 : 0을 제외한 정수가 들어있는 리스트 중, 양수/음수가 쌍으로 존재하는 정수의 절대 값을 반환
•
풀이 방법
◦
중요한 점은 배열에 쌍을 이루기 위한 조건에 맞는 다른 요소가 존재하는지 어떤 식으로 확인해야하는지 점이다.
▪
EX) -2가 먼저 나온다면, 2가 존재하는지 확인이 필요
▪
EX) 2가 먼저 나온다면, -2가 존재하는지 확인이 필요
▪
하지만, 위 방식으로 접근하면 결국에는 나머지 요소를 모두 확인할 때까지는 쌍을 이룰 수 있는지 확인할 수 없다.
◦
그럼 살짝 바꿔 생각하면, 아래와 같이 접근이 가능하다.
▪
EX) -2가 나왔을 때, 이전 요소들 중에서 2가 존재하는지 확인이 필요
▪
EX) 2가 나왔을 때, 이전 요소들 중에서 -2가 존재하는지 확인이 필요
▪
이전 요소는 이미 순회한 데이터이기 때문에, 별도의 위치에 저장한다면 존재 여부는 빠르게 조회 가능하다.
•
이때 해시 테이블을 사용할 수 있는 것이다.
•
만약 존재 여부 뿐 아니라, 관련된 별도 데이터(인덱스 값 등)가 함께 필요하다면 dict 를 사용한다.
•
존재 여부만 파악해도 된다면, set 을 사용하면 된다. → 현 문제의 경우
▪
주어진 데이터 내 요소에서 데이터 쌍을 찾는 문제라면, 순회하는 방향이 아닌 이전에 이미 순회한 요소를 활용하는 방법으로 생각해보자
•
시간복잡도 :
•
성공 코드
class Solution:
def findMaxK(self, nums: List[int]) -> int:
# 조건에 맞는 데이터가 없다면 -1을 반환하기 위한 기본 값
max_num = -1
element_info = set()
# num 순회 -> O(N)
for num in nums:
# set 데이터에 추가
element_info.add(num)
# set은 해시테이블 기반의 자료형이기 때문에, in을 통한 데이터 존재 확인 시 O(1)
# 조건에 맞는 양/음 숫자가 반드시 한번씩 나온다.
# 조건에 맞는 숫자가 음수 먼저, 양수 나올 경우 -> 양수에서 조건 충족
# 조건에 맞는 숫자가 양수 먼저, 음수 나올 경우 -> 음수에서 조건 충족
if num * -1 in element_info:
max_num = max(max_num, abs(num))
return max_num
Python
복사