문제
입력
출력
예제
- 입력1
8
1 2 3 4 -1 -2 -3 -5- 출력1
-1- 입력2
8
-1 1 2 -2 3 -3 4 5- 출력2
9풀이
Hash 기반 자료구조
Hash Fuction을 이용해 Key 값들을 정수로 변환한 뒤, 변환한 각 정수에 고유한 메모리 주소를 할당해서 O(1)의 시간 복잡도에 저장된 값들에 접근할 수 있게끔 하는 자료구조(Python의 dict)
절댓값의 개수를 이용
절댓값들이 몇 번 등장하는지 센 후, 점수의 절댓값이 한 번만 등장하는 경우 다시 배열을 순회하면서 그 절댓값에 해당하는 사람의 점수를 답에 더해준다.
창의력
소개팅을 진행하지 않은 두 사람의 점수의 합은 전체 점수의 합에서 소개팅을 진행한 사람들의 점수의 합을 뺀 값과 같다. 그런데 소개팅을 진행한 사람들의 점수의 합은 항상 0이므로 문제의 답은 항상 전체 접수의 합이다.
파이썬 코드
# -*- coding: utf-8 -*-
# UTF-8 encoding when using korean
import sys
input = sys.stdin.readline
from collections import defaultdict
n = int(input())
dic = defaultdict() # dict에서 키-값 생성 시 값 디폴트가 공백으로 설정됨
score = list(map(int, input().split()))
for i in score:
if abs(i) in dic: # abs(i)가 dic에 있으면 pop
dic.pop(abs(i))
else: # abs(i)가 dic에 없으면 dic에 추가
dic[i] = 1
print(sum(dic.keys()))나는 map으로 받은 score를 정렬하고 앞뒤로 하나씩 더해서 0이 아니면 합했다... 되게 이상하게 풀었구나..?
