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

불냥이_ 2020. 12. 18. 20:00

2470번: 두 용액

첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00

www.acmicpc.net

- 대전략:

요소를 오른차순으로 나열하고, 제일 작은 것은 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)

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