목록Algorithm/Two Pointers (4)
우노
문제 링크 https://www.acmicpc.net/problem/2230 풀이 투 포인터 알고리즘을 사용해 해결할 수 있습니다. 우선, 투 포인터 알고리즘을 사용하기 위해 입력 수열을 오름차순으로 정렬해야합니다. 이후, 두 포인터에 위치한 수의 차이에 따라 왼쪽 또는 오른쪽 포인터를 오른쪽으로 한 칸씩 이동하면 됩니다. 참고 m의 최대값은 2,000,000,000이기 때문에 result의 초기값은 int(2e9) 또는 sys.maxsize로 설정해야합니다. 코드 import sys n, m = map(int, sys.stdin.readline().split()) # 수열 저장 arr = [] for _ in range(n): arr.append(int(sys.stdin.readline())) # 수열..
문제 링크 https://www.acmicpc.net/problem/2003 풀이 투 포인터 알고리즘을 사용해 해결할 수 있습니다. 구간의 시작 idx와 끝 idx를 0과 1로 초기화합니다. 구간의 합을 계산합니다. 구간의 합이 목푯값보다 작다면, 끝 idx를 오른쪽으로 한 칸 이동합니다. 구간의 합이 목푯값보다 크다면, 시작 idx를 오른쪽으로 한 칸 이동합니다. 구간의 합이 목푯값과 같다면, 경우의 수를 증가시키고, 끝 idx를 오른쪽으로 한 칸 이동합니다. 참고로, 1개의 수가 m이 되는 경우도 생각해야합니다. 코드 import sys n, m = map(int, sys.stdin.readline().split()) arr = list(map(int, sys.stdin.readline().split..
문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/42885 풀이 투 포인터 알고리즘을 사용해 해결할 수 있습니다. 구명보트에 태울 수 있는 사람은 최대 2명입니다. 따라서, 사람들의 몸무게를 오름차순 정렬한 뒤, 두 명(몸무게가 가장 적은 사람, 몸무게가 가장 많은 사람)을 태우거나 한 명(몸무게가 가장 많은 사람)을 태웁니다. 코드 def solution(people, limit): # 몸무게를 오름차순 정렬 people.sort() # 시작, 끝 인덱스 start, end = 0, len(people)-1 # 보트의 수 count = 0 while start
문제 링크 https://www.acmicpc.net/problem/14719 풀이 투 포인터 알고리즘을 사용해 해결할 수 있으며, 세부 알고리즘은 아래 예제 코드를 읽으며 이해하시면 도움이 될 것 같습니다. 코드 import sys n, m = map(int, sys.stdin.readline().split()) height = list(map(int, sys.stdin.readline().split())) # 가장 왼쪽 블록과 오른쪽 블록의 인덱스 저장 left, right = 0, len(height) - 1 # 가장 왼쪽 블록의 개수와 가장 오른쪽 블록의 개수로 초기화 left_max, right_max = height[left], height[right] # 고인 물의 개수 result = 0 ..