문제 4)

자연수가 중복 없이 들어있는 리스트가 있습니다. 이 리스트에서 합이 K의 배수가 되도록 서로 다른 숫자 세개를 고르는 방법은 몇 가지인지 세려고 합니다.

자연수가 들어있는 리스트 arr가 매개변수로 주어질 때, 이 리스트에서 합이 K의 배수가 되도록 서로 다른 숫자 세개를 고르는 방법의 가짓수를 return 하도록 solution 함수를 완성해주세요.

---

매개변수 설명

자연수가 들어있는 리스트 arr가 solution 함수의 매개변수로 주어집니다.

• arr의 길이는 3 이상 100 이하입니다.
• arr에는 1 이상 1,000 이하의 자연수가 중복 없이 들어있습니다.
• K는 1 이상 10 이하의 자연수입니다.

---

return 값 설명

리스트에서 합이 K의 배수가 되도록 서로 다른 숫자 세개를 고르는 방법의 가짓수를 return 해주세요.

• 그러한 방법이 없다면 0을 return 하면 됩니다.

---

예시

arr	K	return
[1, 2, 3, 4, 5]	3	4

예시 설명

다음과 같이 4가지 방법이 있습니다.

• 1 + 2 + 3 = 6
• 1 + 3 + 5 = 9
• 2 + 3 + 4 = 9
• 3 + 4 + 5 = 12

주어진 문제 4) 코드

#다음과 같이 import를 사용할 수 있습니다.
#import math

def solution(arr, K):
    #여기에 코드를 작성해주세요.
    answer = 0
    return answer

#아래는 테스트케이스 출력을 해보기 위한 코드입니다.
arr = [1, 2, 3, 4, 5]
K = 3
ret = solution(arr, K)

#[실행] 버튼을 누르면 출력 값을 볼 수 있습니다.
print("solution 함수의 반환 값은 ", ret, " 입니다.")

Solution

주어진 문제 4) Solution 코드

이번엔 빈칸 채우기 문제가 아니라 함수 전체를 작성하는 문제이다.

#다음과 같이 import를 사용할 수 있습니다.
#import math

def solution(arr, K):
    #여기에 코드를 작성해주세요.
    answer = 0
    # 브루트 포스(Brute-Force 방식) : 모든 경우를 무조건 대입하는 방식
    for p in range(len(arr) - 2):
        for q in range(p + 1, len(arr) - 1):
            for r in range(q + 1, len(arr)):
                if (arr[p] + arr[q] + arr[r]) % K == 0:
                    answer += 1
    return answer

#아래는 테스트케이스 출력을 해보기 위한 코드입니다.
arr = [1, 2, 3, 4, 5]
K = 3
ret = solution(arr, K)

#[실행] 버튼을 누르면 출력 값을 볼 수 있습니다.
print("solution 함수의 반환 값은 ", ret, " 입니다.")

다른 문제 풀이 방식

1. 브루트 포스 (Brute-Force) 방식 : $O(n³)$

브루트 포스(Brute-Force 방식) : 모든 경우를 무조건 대입하는 방식 (시간 복잡도 : $O(n³)$)

#세 개의 수의 합이 K 인 것 - n의 3제곱 시간

def solution(arr, K):
    answer = 0
    n = len(arr)

    for p in range(0, n-2):
        for q in range(p + 1, n-1):
            for r in range(q + 1, n):
                if (arr[p] + arr[q] + arr[r])  == K:
                    answer += 1
                    print(arr[p], arr[q], arr[r])
    return answer

#아래는 테스트케이스 출력을 해보기 위한 코드입니다.
arr = [1, 5, 3, 8, 2, 4]
K = 9
ret = solution(arr, K)

#[실행] 버튼을 누르면 출력 값을 볼 수 있습니다.
print("solution 함수의 반환 값은 ", ret, " 입니다.")

• 제시된 문제와 동일하게 세 개의 중첩 for 문을 사용하여 리스트에 저장되어 있는 모든 수의 조합이 조건에 만족하는지 확인하며 답을 구하는 방식이다.

2. 투 포인터 (Two Pointer) 방식 : $O(n²)$

#세 개의 수의 합이 K 인 것 - n의 2제곱 시간

def solution(arr, K):
    answer = 0; sum = 0;
    arr.sort() # 1. 리스트 arr의 항목들을 오름차순 정렬
    
    for p in range(len(arr) - 2):
    # 2. for 문을 이용하여 변수 p에 리스트의 인덱스 0부터 차례대로 값을 받아오고, left 는 p가 나타내는 항목의 다음 인덱스 값을, right에는 리스트의 마지막 항목 인덱스를 할당
    left, right= p+1, len(arr)-1 
    
    while left < right:
    	sum = arr[p] + arr[left] + arr[right] # 3. 세개의 수 합산
        
        if sum < K:
        	left += 1
        elif sum > K:
        	right -= 1
        else:
        	answer += 1
            left += 1
            right -= 1
    
    return answer

#아래는 테스트케이스 출력을 해보기 위한 코드입니다.
arr = [1, 5, 3, 8, 2, 4,6,7,9]
K = 10
ret = solution(arr, K)

#[실행] 버튼을 누르면 출력 값을 볼 수 있습니다.
print("solution 함수의 반환 값은 ", ret, " 입니다.")

투 포인트 방식은 다음과 같이 진행된다.

1. 리스트 arr의 항목들을 순서대로 정렬하는 작업이 선행되어야 한다.

2. for문을 이용하여 변수 p에 리스트의 인덱스 0부터 차례대로 값을 받아오고, left는 p가 나타내는 항목의 다음 인덱스 값을, right에는 리스트의 마지막 항목 인덱스를 할당한다.

3. left 값이 right 보다 작은 동안 반복한다.
   3-1. sum에 arr[p] + arr[left] + arr[right]을 할당한다.
   3-2. 만일 sum 값이 K보다 작으면 left를 1만큼 증가시켜 현재 가리키는 항목의 바로 다음 항목을 가리키도록 조정한다.
   3-3. 만일 sum 값이 K보다 크면 right를 1만큼 감소시켜 현재 가리키는 항목의 바로 앞 항목을 가리키도록 조정한다.
   3-4. 그렇지 않다면 K와 같은 경우이므로 answer를 1 만큼 증가시키고 arr[p]를 선택한 상태에서 세 수의 합이 K와 같아지는 다른 경우가 없는지 탐색하기 위해 left를 1만큼 증가시키고 right를 1만큼 감소시킨다.