문제
Elly는 예상치 못하게 프로그래밍 대회를 준비하는 학생들을 가르칠 위기에 처했다. 대회는 정확히 3명으로 구성된 팀만 참가가 가능하다. 그러나 그녀가 가르칠 학생들에게는 큰 문제가 있었다. 코딩 실력이 좋으면 팀워크가 떨어지고, 팀워크가 좋을수록 코딩 실력이 떨어진다. 그리고 출전하고자 하는 대회는 코딩 실력과 팀워크 모두가 중요하다.
Elly는 그녀가 가르칠 수 있는 모든 학생들의 코딩 실력을 알고 있다. 각각의 코딩 실력 Ai는 -10000부터 10000 사이의 정수로 표시되어 있다. 그녀는 팀워크와 코딩 실력이 모두 적절한 팀을 만들기 위해, 세 팀원의 코딩 실력의 합이 0이 되는 팀을 만들고자 한다. 이러한 조건 하에, 그녀가 대회에 출전할 수 있는 팀을 얼마나 많이 만들 수 있는지를 계산하여라.
N명의 학생들의 코딩 실력 Ai가 -10000부터 10000사이의 정수로 주어질 때, 합이 0이 되는 3인조를 만들 수 있는 경우의 수를 구하여라.
입력
입력은 표준 입력으로 주어진다.
첫 번째 줄에 학생의 수 N이 입력된다. 두 번째 줄에 N개의 그녀가 가르칠 학생들의 코딩 실력인 Ai가 주어진다.
출력
표준 출력으로 그녀가 고를 수 있는 팀의 수를 하나의 정수로 출력한다.
제한
- 1 ≤ N ≤ 10000
- -10000 ≤ Ai ≤ 10000
예제 입력 1
10
2 -5 2 3 -4 7 -4 0 1 -6
예제 출력 1
6
문제 해결 과정
N의 길이가 최대 10000이라 이중 포문이나 while문 안에 for 문을 쓰는 것까지 고려를 해봤다.
나는 처음에 left와 right를 0과 l-1(리스트의 길이)로 지정해서 해당하는 것을 찾으려고 노력했다.
N = int(input())
li = list(map(int, input().split()))
l = len(li)
li.sort()
# print(li)
left, right = 0, l-1
cnt = 0
if li[left] >= 0 :
print(cnt)
if li[right] <= 0 :
print(cnt)
chk = []
while(1) :
if li[right] <= 0 :
left += 1
right = l-1
if li[left] >= 0 :
break
sum = li[left] + li[right]
if (0-sum) in li :
chk_cnt = 0
for i in range(l) :
if li[i] == 0-sum :
chk_cnt += 1
if chk_cnt == 1 :
right -= 1
continue
if li[right] < 0-sum :
right -=1
elif li[right] == 0-sum :
chk.append((0-sum, li[left],li[right]))
cnt += 1
right -= 1
continue
else :
chk.append((0-sum, li[left],li[right]))
cnt += chk_cnt
right -= 1
else :
right -= 1
# print(li)
print(cnt)
# print(chk)일단 먼저 오름차순 정렬을 하고 가장 작은 것과 가장 큰 것부터 비교를 한다.
left, right를 합하고 sum으로 정의한다.
0-sum에 해당하는 값이 리스트 내에 있으면 카운트를 하는 방식인데, 사실 이 방식은 애로 사항이 많았다.
left를 증가시킬지, right를 감소시킬지에 대하 조건도 불분명했고, 해결(?)을 하긴 했지만 시간 초과가 떴다.
한 시간 동안, 더 찾아봤지만 해결 방법은 못 찾았고 한 블로그를 참고했다.
이 방법은 일단 숫자들을 딕셔너리에 (숫자, 숫자 갯수)로 넣는다.
맨 첫 번째 값(나의 경우는 left)을 고정시켜놓고, 그 뒤에 left와 right를 왔다갔다하면서 더한 뒤 0이 되는 것을 찾는다.
첫 번째 값은 for 문으로 돌리고 두 번째 값은 첫 번째 값 바로 뒤(i+1), 세 번째 값은 가장 뒤에 값으로 한다.
그래서 모두 더해보고 0일 때 두 번째 값과 세 번째 값이 같으면, 세 번째 인덱스에 두 번째 인덱스 뺀 값을 넣는다. 왜냐하면 오름차순 정렬을 했기 때문에 그 중간의 값은 모두 같은 값이다.
만약에 리스트에 (-6, 0, 1, 3, 3) 있다고 가정할 때 처음에는 (-6, 3, 3)을 만들 수 있다.
이 때 세 번째 값인 3의 개수를 딕셔너리를 통해 2개로 찾아서 cnt에 넣으면 틀린 답이 된다.
왜냐하면 5 번째 인덱스의 3과 4 번째 인덱스의 3은 다른 값인데 이 모든 3은 (-6, 3, 3)을 구성하는데 모두 사용되었기 때문이다.
따라서 두 번째 값과 세 번째 값이 같으면, 세 번째 인덱스에 두 번째 인덱스 뺀 값을 넣는다.
만약 두 번째 값과 세 번째 값이 다르면, 그 때는 세 번째 값의 개수를 딕셔너리에서 찾아서 카운트한다.
최종 코드
N = int(input())
A = list(map(int, input().split()))
A.sort()
S = N-2
for i in range(N):
if A[i] > 0:
S = i
break
dict = {}
for a in A:
if a in dict:
dict[a] += 1
else:
dict[a] = 1
ans = 0
for i in range(0,S):
tmp = A[i]
start,end = i+1, N-1
while start < end:
s = tmp + A[start] + A[end]
if s==0:
if A[start] == A[end]:
ans += end - start
else:
ans += dict[A[end]]
start += 1
elif s < 0: # s가 0보다 작다면 값을 키워야함
start += 1
else: # s가 0보다 크다면 값을 작게 해야됨
end -= 1
print(ans)참고 블로그
https://velog.io/@pp8817/BOJ-Python-%EB%B0%B1%EC%A4%80-3151%EB%B2%88%ED%95%A9%EC%9D%B4-0
