[백준 2470번] 두 용액 - Python

https://www.acmicpc.net/problem/2470

2470번: 두 용액

풀이

사용한 알고리즘 : 풀이1_ 라인 스위핑, 풀이2_투 포인터

 

※풀이 전략

2가지 전략으로 풀이를 해보았다.

 

풀이1. (라인 스위핑)

1. 입력받은 각각의 수를 튜플 형식으로 리스트에 추가한다.

    만약 음수면 (abs(수), -1)로, 양수면 (수, 1) 형식으로 리스트에 추가한다.  (abs는 절댓값 의미)

2. 리스트에 저장된 튜플들을 튜플의 첫 번째 원소로 오름차순 정렬한다.

3. 인접한 튜플들의 합을 list[i][0]*list[i][1] + list[i+1][0]*list[i+1][1] 방식으로 구하고(결국 원래 두 수의 합)

   인접한 튜플들의 합 중 가장 0에 가까운 원소 2개를 저장한다.

4. 인접한 튜플들의 합 중 가장 0에 가까웠던 원소 2개를 오름차순으로 출력한다.

import sys

input=sys.stdin.readline


N=int(input())
tempList=list(map(int,input().split()))

list=[]
for i in tempList:
    if i<0:
       list.append((abs(i),-1))
    else:
        list.append((i,1))

list.sort()

minGap=int(1e10+1)
resultVal=[int(1e10+1),int(1e10+1)]

for i in range(N-1):
    start=list[i]
    end=list[i+1]
    if minGap>abs(start[0]*start[1]+end[0]*end[1]):
        minGap=abs(start[0]*start[1]+end[0]*end[1])
        resultVal[0]=start[0]*start[1]
        resultVal[1]=end[0]*end[1]

resultVal.sort()
for i in resultVal:
    print(i,end=' ')

 

풀이2. (투 포인터)

1. 입력받은 수들을 오름차순으로 정렬한다.

2. 리스트의 가장 왼쪽 인덱스를 가리키는 start와, 가장 오른쪽 인덱스를 가리키는 end를 정의한다.

3. 리스트 변수인 arr에서 arr[start]+arr[end]=0이면 종료한다.

    arr[start]+arr[end]<0 이면, start를 1 증가시키고

    arr[start]+arr[end]>0이면 end를 1 뺀다.

    근데 와중 구한 합산 값이 0에 가장 가까운 경우, 그 합산 값과 각 원소들을 저장한다.

    arr[start]+arr[end]=0이면 break

4. 합산 값이 0에 가장 가까운 원소들을 오름차순으로 정렬하여 출력한다.

import sys

input=sys.stdin.readline

N=int(input())
arr=list(map(int,input().split()))
arr.sort()

start=0
end=N-1
min=int(1e10)
result1=arr[0]
result2=arr[N-1]

while(start<end):
    sum=arr[start]+arr[end]

    if abs(sum)<min:
        min=abs(sum)
        result1=arr[start]
        result2=arr[end]
        if sum==0:
            break

    if sum<0:
        start+=1
    else:
        end-=1

print(result1,result2)