[알고리즘/투 포인터] 2467번 : 용액 - python

링크 : https://www.acmicpc.net/problem/2467

 

 

 

---

• 문제
• 소요시간: 34분 19초

---

• 설계하기(접근방법) 

1. 입력받기

입력에는 큰 문제가 없다

 

2. 구현하기

포인터의 위치를 어디에 둘지 생각하다 시간은 좀 썼다.

 

모든 수가 양수일때는 가장 앞의 2개의 수

모든 수가 음수일 때는 가장 뒤의 2개의 수 를 출력하면 된다

 

 

나머지의 경우에는 다음과 같은 방식으로 포인터를 조절할 수 있다

중간에 둘의 합이 0인 경우에는 바로 break하면 된다

 

-7 -5 -3 -2 -1 0 4 8

일 때, 처음에는 양 끝에서 출발한다 

 

1 단계)

o                         o

-7 -5 -3 -2 -1 0 4 8

 

둘의 합은 1, 즉 양수이니 양수의 크기를 줄여준다면 절대값이 작아지는 것을 기대할 수 있다

만약 음수의 크기를 늘려준다면 합이 3이 되면서 정답과 멀어진다.

즉 작아지는 기대를 하는 방향으로 둘의 차의 절대값은 진동을 하면서 최소값을 찾아가게 된다

 

그것을 위해서 중간중간 최소값과 최소값의 배열 포인터 위치 2개를 저장하는 변수를 두어야 한다

 

2 단계)

o                      o  

-7 -5 -3 -2 -1 0 4 8

 

둘의 합은 -3이다. 이번에는 음수를 움직여서 더해줄 필요가 있다

 

     o                 o  

-7 -5 -3 -2 -1 0 4 8

둘의 합은 -1이다. 폭이 줄었지만 여전히 음수를 움직여 더한다.

.......

이런 방식으로, 각 수에서 차이가 가장 작은 경우를 체크하면서 

리스트를 순회하면 리스트 전체의 최소합의 절대값을 구할 수 있다.

 

 

3. 출력하기

아까 저장해놓은 포인터의 위치를 통해 숫자 2개를 오름차순으로 출력한다

 

---

• 코드(출력)

n = int(input())

liquid = list(map(int, input().split()))

p1 = 0
p2 = n - 1

small = 10e20
small_p1 = -1
small_p2 = -1

if liquid[p2] <= 0:
    print(liquid[p2 - 1], liquid[p2])
elif liquid[p1] >= 0:
    print(liquid[p1], liquid[p1 + 1])
else:
    while True:
        now = liquid[p1] + liquid[p2]
        # 새로운 최소값 및 위치 저장
        if small > abs(now):
            small = abs(now)
            small_p1 = p1
            small_p2 = p2
        # 둘 숫자가 같아지면
        if p1 + 1 == p2:
            break
        # 합이 0이라면
        if now == 0:
            break
        # 0보다 크면 양수 줄이기
        elif now > 0:
            p2 -= 1
        # 0보다 작으면 음수 줄이기
        else:
            p1 += 1

    print(liquid[small_p1], liquid[small_p2])

---

• 얻어갈 부분

1. 투 포인터 문제를 오랜만에 풀어 포인터의 위치를 어디에 둘지 생각하느라 오래걸렸다. 다음에는 요구사항을 파악해서 위치를 확실하게 정하자