[백준-3151] 합이 0

박제구·2021년 4월 14일
1

Algorithm

목록 보기
1/3
post-thumbnail
시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
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]

  1. 첫 번째 예시에서 2를 선택 했을 때 -2 1(left) 1 1 1 1(right) 같은 상황이라면 합이 0 이고 left,right 인덱스가 가리키는 값이 일치하므로 정렬의 효과로 left, right 사이에서는 모두 같은 숫자를 가리킨다.
    따라서 해당 값의 개수 (right-left+1) 콤비네이션 2를 해주면 모든 경우를 셀 수 있다.

  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 가지의 경우를 셀 수 있다.


python3 코드

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)


회고

중간에 달라질 때 까지 값을 반복해서 찾는 부분을 이분탐색 으로 하면 효율적일 것 같다. 투포인터는 매번 새롭다....
profile
안녕하세요!

0개의 댓글