3주차 | 문제 1. 0커플
문제
구름이는 다가오는 크리스마스에 커플이 아닌 지인들을 서로 소개해 주기로 한다. 구름이는 최대한 많은 커플들이 생기기 바라는 마음으로 아래의 기준으로 지인들에게 점수를 부여한다.
- 구름이의 지인의 수는 항상 짝수이다.
- 모든 점수는 0점을 제외한 정수이다.
- 지인들 중 같은 점수를 가지고 있는 경우는 없다.
- 만약에 n점이 있다면 -n이 항상 존재한다.
구름이는 지인들 중 점수의 합한 값이 0이 되는 두 명을 짝지어서 소개팅을 진행하기로 한다. 구름이는 위와 같은 규칙으로 지인의 점수를 부여하다가 실수로, 4번째 규칙을 지키지 못했다. 그래서 두 사람이 소개팅을 받지 못하게 되었다. 구름이가 이 문제를 해결하기 위해서 소개팅을 진행하지 못한 두 사람의 점수를 합한 값을 출력하시오.
입력
첫째 줄에 구름이 지인의 수 N(2≤N≤100,000, N%2=0)가 주어진다.둘째 줄에 구름이가 부여한 지인들의 점수가 공백을 두고 주어집니다. 모든 점수는 -200,000 이상 200,000 이하의 0을 제외한 정수이다.
출력
구름이의 실수로 소개팅을 받지 못한 두 사람의 점수를 합한 값을 출력하시오.
풀이 1 - 타임아웃 발생
import sys
n=int(sys.stdin.readline()) # 지인의 수
score=list(map(int,sys.stdin.readline().split())) # n명의 지인들의 점수
num=[]
for i in score:
if i>0: # 양수인 값을 num에 저장
num.append(i)
score.remove(i)
for i in score:
for j in num:
if (-i)==j: # 마이너스 붙인 값이 존재하면 각 리스트에서 값을 삭제
score.remove(i)
num.remove(j)
print(sum(score)+sum(num)) # 남은 값들의 합첫 시도 때는 서로 절댓값의 관계를 가지는 값들을 찾아야 한다고 생각해서 양수값과 음수값으로 구분하려고 하였다.
그러다 보니 새로운 리스트를 만들어야 했고, 절댓값이 존재하는지 파악하기 위해 두 개의 리스트를 for문으로 돌리게 되는데, 이때 지인의 수(n)가 많아지면 타임아웃이 발생한다.
풀이 2 - 타임아웃 발생
위 방법에서는 n이 커질수록 반복 횟수가 많아지는 것이 타임아웃의 원인임으로 두 개의 리스트를 가지고 비교하는 것이 아닌, 처음 입력받는 score 리스트안에서 절댓값이 존재하는 요소들을 삭제하는 방법이 떠올랐다.
import sys
n=int(sys.stdin.readline()) # 지인의 수
score=list(map(int,sys.stdin.readline().split())) # n명의 지인들의 점수
num=[]
for i in score:
if (-i) in score: # 절댓값이 존재하면 해당 요소와 절댓값 요소 모두 삭제
score.remove(-i)
score.remove(i)
print(sum(score))하지만 이 방법 역시 for문에서 score의 모든 요소를 방문해야 하므로 n이 커지면 타임아웃이 발생한다.
풀이 3 - 정답
어떻게하면 타임아웃에서 벗어날 수 있을 지 다시 생각해보니 절댓값이 존재하는 요소를 굳이 지울 필요가 없음을 깨닫게 되었다.
문제에서 만약에 n점이 있다면 -n이 항상 존재한다. 는 조건을 제시했으므로, 입력으로 서로의 절댓값이 주어졌다면 n명의 지인들의 점수인 리스트 score의 전체 합을 구하면 절댓값을 가지는 요소들의 합은 0이므로 자동으로 제거되는 것이나 마찬가지이다.
n=int(input()) # 지인의 수
score=map(int,input().split()) # n명의 지인들의 점수
print(sum(score))따라서, n의 크기에 상관없이 리스트의 전체 합을 구하는 방법으로 간단하게 해결할 수 있었다.
구름에서 제시한 해설 코드는 defaultdict를 활용하였는데, defaultdict를 처음 들어봐서 활용하기 위해서는 시간내어 공부해보아야 할 것 같다.