코딩 테스트를 위한 파이썬 문법-투 포인터

1. 특정한 합을 가지는 부분 연속 수열 찾기

• 리스트에 담긴 데이터에 순차적으로 접근할 때 '시작점'과 '끝점' 2개의 점으로 접근할 데이터의 범위를 표현할 수 있다.
• 특정한 합을 가지는 부분 연속 수열 찾기
• 만약 리스트 내 원소에 음수 데이터가 포함되어 있는 경우에는 투 포인터 알고리즘으로 문제를 해결할 수 없다.

n = 5 # 데이터의 개수 N
m = 5 # 찾고자 하는 부분 합 M
data = [1,2,3,2,5] # 전체 수열

count = 0
interval_sum = 0
end = 0

# start를 차례대로 증가시키며 반복
for start in range(n):
    # end를 가능한 만큼 이동시키기
    while interval_sum < m and end < n:
        interval_sum += data[end]
        end += 1

    # 부분합이 m일 때 카운트 증가
    if interval_sum == m:
        count += 1

    interval_sum -= data[start]

print(count)

2. 정렬되어 있는 두 리스트의 합집합

#사전에 정렬된 리스트 A와 B 선언
n,m = 3,4
a = [1,3,5]
b = [2,4,6,8]

result = [0] * (n+m) # 리스트 A와 B의 모든 원소를 담을 수 있는 크기의 결과 리스트 초기화
i = 0 # a의 인덱스
j = 0 # b의 인덱스
k = 0 # result의 인덱스

# a나 b가 끝날 때까지
while i < n or j < m:
    if j>=m or (i<n and a[i] <= b[j]): # i가 n보다 클 경우 에러나기 때문에 i<n이 먼저 와야 함. 
        result[k] = a[i] # 리스트 A의 값을 result에 담을 때
        i += 1
    else: # 리스트 B의 값을 result에 담을 때
        result[k] = b[j]
        j += 1
    k += 1

for i in result:
    print(i, end=' ')

3. 구간 합 계산

n = 5
data = [10,20,30,40,50]

sum_value = 0
prefix_sum = [0]

# 접두사 합(prefix_sum) 배열 계산
for i in data:
    sum_value += i
    prefix_sum.append(sum_value) 

left = 3
right = 4

# 구간 합 계산(세 번째 수부터 네 번째 수까지)
print(prefix_sum[right]-prefix_sum[left-1])

4. 순열과 조합

순열

서로 다른 n개에서 r개를 선택하여 일렬로 나열하는 것

import itertools

data = [1,2]

for x in itertools.permutations(data, 2):
    print(list(x))

조합

서로 다른 n개에서 순서에 상관없이 서로다른 r개를 선택하는 것

import itertools

data = [1,2,3]

for x in itertools.combinations(data, 2):
    print(list(x), end=' ')