-
[BOJ/python]2473번 세 용액알고리즘/BOJ 2022. 7. 4. 22:35
백준 2473번 세 용액 파이썬 투포인터
문제 링크 - https://www.acmicpc.net/problem/2473
다양한 방법으로 풀 수 있다. 2470번 두 용액 문제의 풀이를 활용했다. 다른 테크닉 없이 모든 용액을 하나씩 고정해두고 해당 용액 다음으로 등장하는 용액들만 사용하여 투 포인터를 사용해서 풀면 된다.
1. 풀이
우선 주어진 A 리스트를 오름차순으로 정렬한다. 투 포인터를 처음과 끝에서 시작하여 중간에서 만나면 탐색을 종료하는 방식을 사용한다. 이를 통해 0보다 합이 크면 큰 값을 빼주고, 0보다 합이 작으면 작은 값을 빼준다.
- 정렬된 A 리스트에 있는 용액을 하나씩 고정한다.
- 고정된 용액의 인덱스가 i라면 i+1번 인덱스부터 N-1번 구간에서 고정된 용액과의 합의 크기가 0에 가까운 두 용액을 찾는다.
- 만약 세 용액의 합의 절대값 크기가 tmp보다 작다면 sol 배열에 정답으로 갱신한다.
- 이후에 세 용액의 합이 0이라면 해당 고정 구간의 탐색을 중지한다.
- 세 용액의 합이 0보다 작다면 투 포인터 구간에서 시작값을 1 늘린다. (0에 가깝게 만들기 위해 작은 값을 뺀다.)
- 세 용액의 합이 0보다 크다면 투 포인터 구간에서 종료값을 1 줄인다. (0에 가깝게 만들기 위해 큰 값을 하나 뺀다.)
2. 코드
#세용액 two pointer N= int(input()) A=list(map(int, input().split())) A.sort() tmp=float('inf') sol=[] for i in range(N-2): fix = A[i] s,e = i+1, N-1 while s!=e: if abs(A[s]+A[e]+fix) < tmp: tmp = abs(A[s]+A[e]+fix) sol = [ fix, A[s], A[e] ] if A[s]+A[e]+fix == 0 : break elif A[s]+A[e]+fix < 0 : s+=1 else: e-=1 print(*sol)
N개의 주어진 용액을 모두 탐색한다. i번째 용액을 고정시킨 경우 N-i개의 용액에 대하여 투 포인터를 사용한다. 즉 시간복잡도는 O(N*(N-i)) = O(N^2)
새로운 풀이
좀 더 시간을 줄일 수 있는 코드를 찾아야할 것 같다.
'알고리즘 > BOJ' 카테고리의 다른 글
[BOJ/python]1504번 특정한 최단 경로 (0) 2022.07.06 [BOJ/python]13549번 숨바꼭질 3 (0) 2022.07.06 [BOJ/python]21757번 나누기 (0) 2022.07.04 [BOJ/python]3020번 개똥벌레 (0) 2022.07.04 [BOJ/python]1092번 배 (0) 2022.07.04