[BOJ] 2473번 : 세 용액(투 포인터)

목차

접근

!! 이 문제를 풀기전에 조금 더 쉬운 버젼인 아래의 문제를 먼저 해결해보고 오는 것을 추천한다.
[BOJ - 2467번: 용액]

 

위의 용액 문제 또한 투포인터로 해결할 수 있다. 정렬이 되어 있는 용액 리스트에서 두 용액을 합쳤을 때 특성값이 0에 가장 가까운 두 용액을 구하는 문제이다.

정렬 또한 되어있기 때문에, 그냥 투포인터로 0에 가장 가까운 방향으로 업데이트를 진행하면서 정답을 구하면 되는 문제이다.

 

그럼 이제 이 문제는 어떻게 해결할 것인가?

이번엔 세개의 용액을 합쳐서 특성값이 0에 가장 가까운 세 용액을 구하는 문제이다.

일단 위의 그냥 용액과는 다르게 전체 용액의 수 `N` 은 5,000 이하다.

 

쓰리포인터..? 뭐라고 말해야할지 모르겠지만,

하나는 고정해두고 나머지 두개에 대한 투포인터 연산을 통해 최적값을 찾아나가는 과정을 진행할 수 있을 것 같다.

그랬을 때 시간복잡도를 생각해보면,

• 고정해두는 포인터의 순회 -> `N`
• 나머지 투포인터의 순회 -> `N`

그렇다면, `O(N^2)`으로 해결할 수 있을 것 같았다.

 

해결

위와 같은 접근으로 결국 해결했다.

고정해두기 위한 포인터를 순회하면서, 나머지의 투포인터는 고정 포인터 다음(시작), 마지막 인덱스(끝)을 처음으로 하여, 0에 가깝게 업데이트를 진행했다.

---

문제풀이와 별개로 제출방식에 따른 시간차이가 발생한다는 것을 조금 정리해둘 필요가 있다는 생각이 들었다.

처음 위의 접근방식을 Python3로 제출했을 땐, 시간초과가 났다. 하지만 PyPy3로 제출했을 땐 시간초과가 나지 않았다. 이건 다들 아는 차이라고 생각한다.

그렇지만 Python3로 제출해서 통과를 할 수 없는건 아니다.

해결한 로직을 함수로 만들어 Local Code로 바꿔주고, main에서 호출 하는 방법으로 시간이 줄어들 수 있다.

실제로 그렇게 제출하니 통과가 되었다.

 

그 이유는 아래의 Stack Overflow 질문에서 볼 수 있었다.

https://stackoverflow.com/questions/11241523/why-does-python-code-run-faster-in-a-function

Why does Python code run faster in a function?

아래 답변에 보면, 함수가 컴파일 될 때 Local 변수는 고정된 크기의 배열에 저장되고, Global 변수는 dict에 저장해서, Local변수가 읽기/쓰기에 있어서 더 빠르게 접근할 수 있다고 한다.

 

또 발생한 다른 신기한 문제는 위와 같이 Local Code로 변환한 로직을 PyPy3로 제출하게 되면 오히려 시간이 소폭 늘어난다는 것이다.

이건 아래의 Stack Overflow 질문에서 찾을 수 있었다.

https://stackoverflow.com/questions/61144206/writing-codes-in-local-namespace-is-slower-than-in-global-in-pypy3

Writing codes in local namespace is slower than in global in PyPy3

PyPy3는 JIT Compiler가 프로그램을 실행하는 시점에 필요한 부분을 컴파일 하는 방식과 자주 쓰이는 코드는 캐싱해둬서 실행속도를 빠르게 개선했는데, Local Code에서는 상수처럼 사용되는 변수도 변할 수 있을 것으로 생각하여 JIT가 해당 변수가 일정하도록 최적화를 진행하지 않는다고 한다.

그렇지만 Global Code에서 선언된 변수들은 일반적으로 상수로 사용되기 때문에 JIT가 상수로써의 최적화를 진행하여(변경여부를 기억하여, 변경되지 않았다면 일정하다고 가정하여) Local Code에 비해서 더 빠른 속도를 낸다고 한다. 

 

일단은 이 정도로만 이해하고 넘어가는게 좋을 것 같다.

여튼 정리하자면, 백준 기준 코드 제출전략을 아래와 같이 세울 수 있을 것 같다.(로직이 맞다는 전제하에)

• 로직을 Local로 변환하여 제출
• Python3 -> PyPy3로 제출

코드

import sys

input = sys.stdin.readline

def solution():
    nums_list = []
    ans = float('inf')
    for i in range(N-2):
        st = i+1
        ed = N-1
        while st < ed:
            if ans > abs(nums[i] + nums[st] + nums[ed]):
                ans = abs(nums[i] + nums[st] + nums[ed])
                nums_list = [nums[i], nums[st], nums[ed]]
            if nums[i] + nums[st] + nums[ed] < 0:
                st += 1
            else:
                ed -= 1
    return nums_list

if __name__ == '__main__':
    N = int(input())
    nums = list(map(int, input().split()))
    nums = sorted(nums)
    
    res = solution()
    print(*res)