섞고 섞고 돌리고 섞고 (백준 2470 : 두 용액)

2470번: 두 용액 (acmicpc.net)

2470번: 두 용액

 - 대전략:

요소를 오른차순으로 나열하고, 제일 작은 것은 min, 큰 것을 max로 하자. (min과 max는 인덱스 값이다.)

그리고 두개를 더했을 때, 음수면은 min을 한칸 위로 옮기고 양수면 max를 한칸 밑으로 내린다. 

min과 max를 더한 절대값 ( abs(sol[min] + sol[max]))이 제일 낮았을 때, min과 max을 저장하고, 양 합의 절댓값이 더 낮은 값을 경신하면 min max값을 갱신한다.

 

물론 0이 나오면 break한다.

 

시간초과날려나?

 

 

우선 값을 받고 sort한 후, 최소-최대 값을 뽑아내자.

n = int(sys.stdin.readline())
sol = list(map(int,sys.stdin.readline().split()))
sol.sort()
 
min_idx = 0
max_idx = n-1
new = abs(sol[0] + sol[n-1])
best_min = sol[min_idx]
best_max = sol[max_idx]
best_new = new

그리고 위의 절차를 실행할 함수를 만들자.

import sys
 
n = int(sys.stdin.readline())
sol = list(map(int,sys.stdin.readline().split()))
sol.sort()
 
min_idx = 0
max_idx = n-1
new = abs(sol[0] + sol[n-1])
best_min = sol[min_idx]
best_max = sol[max_idx]
best_new = new
 
 
def search():
    global min_idx, max_idx, best_min, best_max, new, best_new
    
    
    while abs(new) != 0:
        new = sol[min_idx] + sol[max_idx]
        if abs(new) < abs(best_new):
            best_min = sol[min_idx]
            best_max = sol[max_idx]
            best_new = new
            
        if new < 0:
            min_idx += 1
        else:
            max_idx -= 1
        
        
        
        if max_idx == min_idx:
            break
 
search() 
print(best_min, best_max)

이번엔 아주 깔끔하게 나왔다. 역시 쉽고 빠른 길을 택하는 것이 맞는가보다.