[Python] 2470번 : 두 용액

 

문제 3줄 요약

1. 알칼리성 용액(음의 정수), 산성 용액(양의 정수)이 있다.

2. 같은 종류든 서로 다른 종류든 두 용액을 섞어서 0과 가깝게 만든다.

3. 0에 가장 가까운 경우가 두 개 이상일 경우, 그 중 아무것이나 하나 출력

 

 

 

 

 

스페셜 저지 딱지가 붙어있는 것을 보고

등골이 쎄했다.

 

이 딱지는 도대체 뭘 의미할까...

 

내가 생각한 방법은

두 종류의 용액을 나눠

절댓값을 최소값으로 갱신해주는 방법이었다.

 

근데 하나씩 비교해주니,

첫 번째 관문

"시간 초과"

 

최솟값인 0인 경우는

빠르게 break를 해주었다.

 

그 결과,

 

응 그냥 틀렸다.

자세히 생각해보니

문제 요약 두 번째 줄..

최소가 같은 용액일 때를 고려해주지 않았다..

 

결국 질문게시판에 있는

투포인터 코드를 활용하여

개선해주었다.

 

 

from sys import stdin

if __name__ == "__main__":
    N = int(stdin.readline())
    num_list = []

    for num in stdin.readline().strip().split():    
        num_list.append(int(num))
    num_list = sorted(num_list)
    
    # 투포인터
    Left = 0
    Right = len(num_list)-1

	# 최소일 경우, 용액의 정보를 담는다.
    answer = [0,0,abs(num_list[0]+num_list[-1])]
    while(Left<Right):
    	# 최소 비교
        if abs(num_list[Left] + num_list[Right]) <= answer[2]:
            answer[0] = num_list[Left]
            answer[1] = num_list[Right]
            answer[2] = abs(num_list[Left] + num_list[Right])
		# 최솟값인 0 일 경우, break
        if answer[2] == 0:
            break

		# 절댓값이 커진 경우, 좀 더 작은 용액을 담는다.
        if num_list[Left]+num_list[Right] > 0:
            Right -=1
        # 절댓값이 작아진 경우, 좀 더 큰 용액을 담는다. 
        else:
            Left += 1
        
    print(answer[0], answer[1])

 

스페셜 저지...

스페셜한 생각이 필요한 문제다.

 

끝!