Python을 이용한 3151번 : 합이 0 에 대해서 포스팅하겠습니다. 3151번은 브루트포스 알고리즘, 정렬, 이분 탐색, 두 포인터의 알고리즘으로 분류되는 문제입니다.
1. 3151번 문제설명
- 목표: 3명의 학생으로 구성된 팀을 만들어야 하며, 팀원들의 코딩 실력 합이 0이 되어야 함.
- 학생 코딩 실력 범위: -10000부터 10000까지의 정수.
- 입력:
- 학생 수 N
- N명 학생들의 코딩 실력 Ai
- 출력: 코딩 실력 합이 0이 되는 3인조 팀의 수
2. 3151번 접근방법
- 정렬: 입력받은 학생들의 코딩 실력을 오름차순으로 정렬. 이는 이후 작업에서 합을 쉽게 찾기 위함.
- 투 포인터 사용: 한 명의 학생을 고정시키고, 나머지 두 명의 학생을 찾는 방법을 사용. 이때, 두 명의 학생을 찾기 위해 투 포인터 알고리즘 사용.
left포인터는 고정된 학생 다음 위치에서 시작.right포인터는 배열의 가장 마지막에서 시작.- 두 포인터가 만나거나 교차하기 전까지 반복.
- 합 계산 및 조건 비교:
- 세 학생의 코딩 실력 합 계산.
- 합이 0보다 크면
right포인터를 왼쪽으로 이동하여 합을 감소. - 합이 0보다 작으면
left포인터를 오른쪽으로 이동하여 합을 증가. - 합이 0일 경우, 가능한 팀의 수 증가.
- 중복 처리: 코딩 실력이 같은 학생들로 인해 중복된 팀이 발생할 수 있으므로, 이를 적절히 처리해야 함.
- 최적화: 이중 루프(하나는 고정된 학생을 위한 루프, 다른 하나는 투 포인터를 위한 루프)를 통해 N^2에 가까운 시간 복잡도로 문제를 해결할 수 있음. 대량의 데이터에서도 효율적으로 작동할 수 있도록 최적화 고려.
- 이진탐색 :
- 이진 탐색의 목적: 이진 탐색은
arr[right]와 같거나 큰 첫 번째 원소의 위치를 찾습니다. 이때arr[right]는 고정되어 있고,arr[left]와의 조합으로 합이 0이 되는 경우를 찾고 있습니다. 이진 탐색으로 찾는idx는arr[right]와 같은 값을 가진 원소 중 가장 왼쪽에 있는 원소의 인덱스를 의미합니다. right - idx + 1의 의미: 여기서idx는arr[right]와 같은 값을 가진 원소 중 가장 왼쪽 인덱스를 가리키고,right는 같은 값을 가진 원소 중 가장 오른쪽 인덱스를 가리킵니다. 따라서,right - idx + 1은arr[right]의 값과 동일한 모든 원소의 수를 계산합니다. 이는arr[i] + arr[left] + arr[right] == 0이 성립할 때,arr[left]와arr[right]사이에 있는 동일한 값들을 모두 포함하여 조합을 만들 수 있다는 것을 의미합니다.- 0이 아닌 조합에 대한 고려: 이 부분에서 혼란이 있을 수 있는데,
right - idx + 1을 더하는 로직은arr[i] + arr[left]와arr[right]의 값이 같을 때만 적용됩니다. 즉,arr[left]와arr[right]사이에 0이 아닌 다른 조합이 가능하다 하더라도, 이 로직에서는arr[right]와 같은 값을 가진 원소들만을 대상으로 조합의 수를 세고 있으며, 그 범위 내에서의 조합만을 계산하는 것입니다.
- 이진 탐색의 목적: 이진 탐색은
3. 3151번 코드
Python
#https://www.acmicpc.net/problem/3151
# 주어진 배열에서 target보다 크거나 같은 첫 번째 원소의 위치를 찾는 이진 탐색 함수
def binary(arr, target):
left, right = 0, len(arr) - 1 # 탐색 시작과 끝을 설정
while left < right: # left가 right 이하일 때까지 탐색을 계속
mid = (left + right) // 2 # 중간점을 기준으로 탐색 범위를 반으로 나눔
if arr[mid] < target: # 중간점의 값이 타겟보다 작은 경우
left = mid + 1 # 타겟은 중간점의 오른쪽에 있으므로, left를 조정하여 탐색 범위를 줄임
else: # 중간점의 값이 타겟보다 크거나 같은 경우
right = mid # 타겟은 중간점 또는 그 왼쪽에 있으므로, right를 조정하여 탐색 범위를 줄임
return left # 탐색 종료 후, left 위치는 target값보다 크거나 같은 첫 번째 원소를 가리킴
from sys import stdin
input = stdin.readline # 입력 빠르게 받기
N = int(input()) # 원소의 개수 입력받기
arr = list(map(int, input().split())) # 배열 입력받기
arr.sort() # 배열 오름차순 정렬
answer = 0 # 조건에 맞는 경우의 수를 저장할 변수
# 세 수의 합이 0을 찾는 메인 로직
for i in range(N-2): # 배열의 모든 원소를 순회하며, 마지막 두 원소는 제외(세 원소의 조합을 찾기 위함)
left, right = i+1, N - 1 # 두 번째 원소와 세 번째 원소를 가리킬 포인터 초기화
while left < right: # left가 right보다 작을 때까지 반복 (두 포인터가 교차하지 않는 상태)
hap = arr[left] + arr[right] + arr[i] # 현재 선택한 세 원소의 합 계산
if hap > 0: # 합이 0보다 큰 경우
right -= 1 # 합을 줄이기 위해 right 포인터를 왼쪽으로 이동
else: # 합이 0보다 작거나 같은 경우
if hap == 0: # 합이 정확히 0인 경우, 조건에 부합하는 경우의 수를 찾음
if arr[left] == arr[right]: # left와 right가 가리키는 값이 같다면, 중복된 값들 사이의 조합을 찾은 것
answer += right - left # 가능한 모든 조합의 수를 결과에 추가
else: # left와 right가 가리키는 값이 다르다면, 더 복잡한 조건을 만족하는 경우
idx = binary(arr, arr[right]) # arr[right] 값과 같거나 큰 첫 번째 원소의 위치를 이진 탐색으로 찾음
answer += right - idx + 1 # 찾은 위치부터 right까지의 조합 수를 결과에 추가
left += 1 # left 포인터를 오른쪽으로 이동하여 다음 조합 탐색 준비
print(answer) # 최종 계산된 조합의 수 출력