시간 제한 | 메모리 제한 | 제출 | 정답 | 맞은 사람 | 정답 비율 |
---|---|---|---|---|---|
4 초 | 128 MB | 321 | 79 | 60 | 30.612% |
Elly는 예상치 못하게 프로그래밍 대회를 준비하는 학생들을 가르칠 위기에 처했다. 대회는 정확히 3명으로 구성된 팀만 참가가 가능하다. 그러나 그녀가 가르칠 학생들에게는 큰 문제가 있었다. 코딩 실력이 좋으면 팀워크가 떨어지고, 팀워크가 좋을수록 코딩 실력이 떨어진다. 그리고 출전하고자 하는 대회는 코딩 실력과 팀워크 모두가 중요하다.
Elly는 그녀가 가르칠 수 있는 모든 학생들의 코딩 실력을 알고 있다. 각각의 코딩 실력 (Ai)는 -10000부터 10000 사이의 정수로 표시되어 있다. 그녀는 팀워크와 코딩 실력이 모두 적절한 팀을 만들기 위해, 세 팀원의 코딩 실력의 합이 0이 되는 팀을 만들고자 한다. 이러한 조건 하에, 그녀가 대회에 출전할 수 있는 팀을 얼마나 많이 만들 수 있는지를 계산하여라.
문제 요약: N명의 학생들의 코딩 실력 Ai가 -10000부터 10000사이의 정수로 주어질 때, 합이 0이 되는 3인조를 만들 수 있는 경우의 수를 구하여라.
입력은 표준 입력으로 주어진다.
첫 번째 줄에 학생의 수 N이 입력된다. 두 번째 줄에 N개의 그녀가 가르칠 학생들의 코딩 실력인 Ai가 주어진다.
(1 ≤ N ≤ 10000, -10000 ≤ Ai ≤ 10000)
표준 출력으로 그녀가 고를 수 있는 팀의 수를 하나의 정수로 출력한다.
정렬된 리스트에 투포인트 알고리즘을 적용하면 쉽게 풀릴거라 생각했다.
주어진 예시인 10 개의 숫자 2 -5 2 3 -4 7 -4 0 1 -6 를 오름차순 정렬하여 리스트에 넣으면 [-6, -5, -4, -4, 0, 1, 2, 2, 3, 7] 이 되고 이 리스트에서 3가지의 숫자의 합이 0이 되는 경우의 수를 구하는 것이다.
하나의 숫자를 고정으로 두고, 두 가지 값을 변경하면서 찾는 방식으로 풀었다.
하나의 숫자는 for i in range(N-2)
를 통해 왼쪽부터 하나씩 정해두고, 두가지 값은 left, right를 i+1, N-1 로 각각 두고 투포인터로 갱신하면서 추가 했다.
예시의 값은 통과 했지만 제출 했을 때 시간초과
틀렸습니다
가 뜨길래 다시한번 문제점을 발견하기 위한 예시를 작성해 보았다.
left 와 right 를 가지고 갱신할때 합이 0 이 되는 순간 left의 값을 이동하는 것, 하나 씩 이동하기 때문에 모든 경우를 확인하는 것 두가지가 잘못 되었다.
투포인터로 값을 갱신하다가 합이 0이 되는 순간 두가지의 경우를 조심해야 하는데
1. left, right 인덱스의 값이 일치하는 경우
ex) [0,0,0,0,0], [-2, 1, 1, 1, 1, 1 ]
2. left, right 인덱스의 값이 일치하지 않는 경우
ex) [-4, -2, -2, 6, 6, 6, 6]
첫 번째 예시에서 2를 선택 했을 때 -2 1(left) 1 1 1 1(right) 같은 상황이라면 합이 0 이고 left,right 인덱스가 가리키는 값이 일치하므로 정렬의 효과로 left, right 사이에서는 모두 같은 숫자를 가리킨다.
따라서 해당 값의 개수 (right-left+1) 콤비네이션 2를 해주면 모든 경우를 셀 수 있다.
두 번째 예시에서 -4를 선택 했을 때 -4 -2(left) -2 6 6 6 6(right) 같은 상황이라면 합이 0 이고 두개의 인덱스가 가리키는 값이 다르기 때문에 left 와 right 를 동시에 이동해서 개수를 한번에 구할 수 있다.
따라서 -4 -2 -2(left) 6(right) 6 6 6 으로 이동시키고 left 이동개수 2, right 이동개수 4를 통해 2*4 가지의 경우를 셀 수 있다.
import sys
N = int(sys.stdin.readline())
coding = sorted(list(map(int, sys.stdin.readline().split())))
answer = 0
for i in range(N-2):
choice_value = coding[i] # 선택값
if choice_value > 0: # 정렬되어 있기 때문에 선택값이 최소이고 0보다 클 수 없음
break
left = i + 1
right = N - 1
while left < right:
value = choice_value + coding[left] + coding[right]
if value == 0:
if coding[left] == coding[right]:
answer += (right-left+1)*(right-left)//2 #nC2 적용
break
else:
is_right = coding[right]
r = 0
while True: # right 값 달라질때까지 이동
if coding[right] != is_right:
break
else:
right -= 1
r += 1
is_left = coding[left]
l = 0
while True: # left 값 달라질때까지 이동
if coding[left] != is_left:
break
else:
left += 1
l += 1
answer += l*r # 이동값*이동값 경우의수
elif value > 0: # 0보다 크면 right 감소 (투포인터)
right -= 1
else:
left += 1 # 0보다 크면 left 증가 (투포인터)
print(answer)