226. 두 용액

1) 어떤 전략(알고리즘)으로 해결?

• 투투투 포인터

2) 코딩 설명

<내 풀이>

import sys
# 특성값이 0에 가장 가까운 용액을 
# 만들어내는 두 용액을 찾는 프로그램
# 산성은 양수, 알칼리는 음수
n = int(sys.stdin.readline().strip())
lis = list(map(int, sys.stdin.readline().rstrip().split()))
lis.sort() ; minim = 1000000000000001 ; result=[]

s,e = 0,n-1
while s<e : 
    #print(s,e,minim,result)
    cmp = lis[s] + lis[e]

    if lis[s]<0 and lis[e]<0 : # 음음 
        if abs(lis[e]+lis[s])<minim : 
            minim = abs(lis[e]+lis[s])
            result=[]; 
            result.append(lis[s]); 
            result.append(lis[e])
        s+=1

    elif lis[s]>0 and lis[e]>0 : # 양양
        if abs(lis[e]+lis[s])<minim : 
            minim = abs(lis[e]+lis[s])
            result=[]; 
            result.append(lis[s]); 
            result.append(lis[e])
        e-=1

    else : # 음양 
        if abs(lis[e]+lis[s])<minim : 
            minim = abs(lis[e]+lis[s])
            result=[]; 
            result.append(lis[s]); 
            result.append(lis[e])

        if cmp>0 : e-=1 # 더한 값이 양수였으면 좀 줄이자 
        else : s+=1 # 음수였다면 늘리자 

result.sort()
for i in result : 
    print(i, end=" ")

사실 나는 굳이굳이 쪼개가면서 경우 나눴는데 그럴 필요 ㄴㄴ

tmp 값이 음수 -> start += 1, tmp 값이 양수 -> end -=1

하면 되는 문제였지

<다른 분의 풀이>

출처 : [출처 블로그 링크 ]( https://jainn.tistory.com/47 [Dogfootruler Kim:티스토리])

import sys
input = sys.stdin.readline

n = int(input())
arr = sorted(list(map(int, input().split())))

start = 0
end = n-1
czero = abs(arr[start]+arr[end])
cstart = start
cend = end

while start<end:
    tmp = arr[start]+arr[end]
    if abs(tmp) < czero:
        cstart = start
        cend = end
        czero = abs(tmp)
        if czero == 0:
            break
    if tmp > 0:
        end -= 1
    else:
        start += 1

print(arr[cstart], arr[cend])

<내 틀렸던 풀이, 문제점>

시간초과

import sys
# 특성값이 0에 가장 가까운 용액을 
# 만들어내는 두 용액을 찾는 프로그램
# 산성은 양수, 알칼리는 음수
n = int(sys.stdin.readline().strip())
lis = list(map(int, sys.stdin.readline().rstrip().split()))
lis.sort()
minim = 10000001
result=[]

for i in range(n) : 
    s,e = i,n-1
    while s<e : 
        if lis[s]<0 and lis[e]>0 and abs(lis[s]+lis[e]) < minim :
                minim = lis[s]+lis[e] 
                result=[]
                result.append(lis[s])
                result.append(lis[e])
                e-=1
        elif lis[s] > 0 : break
        elif lis[e] < 0 : break
        else : e-=1

result.sort()
for i in result : 
    print(i, end=" ")

3프로 틀림

import sys
# 특성값이 0에 가장 가까운 용액을 
# 만들어내는 두 용액을 찾는 프로그램
# 산성은 양수, 알칼리는 음수
n = int(sys.stdin.readline().strip())
lis = list(map(int, sys.stdin.readline().rstrip().split()))
lis.sort() ; minim = 10000001 ; result=[]

s,e = 0,n-1
while s<e : 
    #print(s,e,minim,result)
    cmp = lis[s] + lis[e]

    if lis[s]<0 and lis[e]<0 :
        if abs(lis[e]-lis[s])<minim : 
            minim = abs(lis[e]-lis[s])
            result=[]; 
            result.append(lis[s]); 
            result.append(lis[e])
        s+=1

    elif lis[s]>0 and lis[e]>0 :
        if abs(lis[e]-lis[s])<minim : 
            minim = abs(lis[e]-lis[s])
            result=[]; 
            result.append(lis[s]); 
            result.append(lis[e])
        e-=1

    else : # 음 양 
        if abs(1-lis[e]+lis[s])<minim : 
            minim = abs(lis[e]+lis[s])
            result=[]; 
            result.append(lis[s]); 
            result.append(lis[e])

        if lis[e-1] > 0 : 
            e-=1
        elif lis[s+1] < 0 :
            s+=1
        else : break

result.sort()
for i in result : 
    print(i, end=" ")

32 프로에서 틀려

=> 32프로 부근에서 틀리면 차의 최댓값 잘 못 잡은 것

1부터 1,000,000,000까지의 양의 정수로 나타내고, 알칼리성 용액의 특성값은 -1부터 -1,000,000,000까지의 음의 정수

• 최댓값은 2000000000 이상으로 잡아야됨

import sys
# 특성값이 0에 가장 가까운 용액을 
# 만들어내는 두 용액을 찾는 프로그램
# 산성은 양수, 알칼리는 음수
n = int(sys.stdin.readline().strip())
lis = list(map(int, sys.stdin.readline().rstrip().split()))
lis.sort() ; minim = 10000001 ; result=[]

s,e = 0,n-1
while s<e :
#print(s,e,minim,result)
cmp = lis[s] + lis[e]

if lis[s]<0 and lis[e]<0 :
    if abs(lis[e]+lis[s])<minim : 
        minim = abs(lis[e]+lis[s])
        result=[]; 
        result.append(lis[s]); 
        result.append(lis[e])
    s+=1

elif lis[s]>0 and lis[e]>0 :
    if abs(lis[e]+lis[s])<minim : 
        minim = abs(lis[e]+lis[s])
        result=[]; 
        result.append(lis[s]); 
        result.append(lis[e])
    e-=1

else : # 음 양 
    if abs(lis[e]+lis[s])<minim : 
        minim = abs(lis[e]+lis[s])
        result=[]; 
        result.append(lis[s]); 
        result.append(lis[e])

    if cmp>0 : e-=1
    else : s+=1

result.sort()
for i in result :
print(i, end=" ")

### <반성 점>

### <배운 점>