★[python_파이썬_pass]백준_2798번_블랙잭_풀이_삼중for문 비교

공부하는허딩크 : https://www.youtube.com/live/7NjVRfUec38?feature=shared

 

<내가 작성한 삼중 for문>

N, M = map(int, input().split())

A = list(map(int, input().split()))

answer = []

for i in range(N):

    for j in range(N):

        for k in range(N):

            print("i = ", i, "j = ", j, "k = ", k)

            if i == j or j == k or i == k or (A[i] + A[j] + A[k] > M) :

                continue

            else:

                answer.append(A[i] + A[j] + A[k])

 

<효율적인 삼중 for문>

n,m = map(int, input().split())

li = list(map(int, input().split()))

num = 0

for i in range(0, n-2 ):

    for j in range(i+1, n -1):

        for k in range(j+1, n):

            if li[i] + li[j] + li[k] > m:

                continue

            if li[i] + li[j] + li[k] > num:

                num = li[i] + li[j] + li[k]

               

print(num)

 

 

첫번째로 내가 작성한 3중 for문은 모든 인덱스를 매칭시키는 방법이다. 즉, range(5)가 3번 반복되면 총 125개의 경우의 수가 나온다. 

문제의 블랙잭은 중복된 카드는 선택할 수가 없기 때문에 중복인 것들을 제외하면 총 60개의 경우의 수가 나오고

순서도 신경쓸 필요 없기 때문에 총 10개의 경우의 수만 고려하면 된다.

 

내 코드는 이러한 제외할 필요가 있는 115개의 인덱스까지 전부 고려한 후 if조건문에서 중복되는 경우의 수를 제외한 경우이다.

 

아래 노란색으로 표기한 부분이 중복되는 부분이고 최종적으로 초록색 배열만 남는다.

 

효율적인 코드는 이러한 비효율을 제외하고 딱 필요한 인덱싱 조합을 구성한다.

 

내가 작성한 코드와 효율적인 코드의 차이점을 분석해서 머리속에 집어 넣어야 겠다.

 

현재 삼중 for문 구성은 아래와 같다. N = 5와 10일경우 모두 N -2, N-1, N의 조건과 0, i + 1, j +1 의 조건이 있다.

for i in range(N - 2):

    for j in range(i + 1, N - 1):

        for k in range(j + 1, N):

 

N의 개수가 달라지더라도 해당 조건은 유지하고 있으니까 일단 유지. 그런데 만약 4개를 뽑아야 하는 상황이라면??

for문이 1개 추가되면서 조건은 N - 3, N - 2, N - 1, N => 각각 i + 1, j + 1, k + 1 이렇게 나와야 한다.

일단 암기.

 

이렇게 계속 for를 증가시키면 시간복잡도가 증가하여 O(N4)가 됨으로 성능이 저하된다.

아래의 코드는 chat GPT가 제공한 코드이다. 시간 복잡도가 O(N2logN) 로 삼중for문보다는 효율적이다. 

그런데 보기에 쉽지 않다. 일단 정리해두고 나중에 시간되면 챙겨보자.

import sys

input = sys.stdin.readline

N, M = map(int, input().split())

A = list(map(int, input().split()))

A.sort()  # 리스트를 정렬

answer = 0

for i in range(N - 2):

    for j in range(i + 1, N - 1):

        left, right = j + 1, N - 1

        while left <= right:  # 투 포인터 활용

            mid = (left + right) // 2

            if A[i] + A[j] + A[mid] <= M:

                answer = max(answer, A[i] + A[j] + A[mid])

                left = mid + 1

            else:

                right = mid - 1

print(answer)

 

 

또 itertools에 순열과 조합에 자주 쓰이는 combinations와 permutations를 추가 공부해야겠다.