[python_파이썬Pass]백준_11728번_배열 합치기_투포인터 개념 설명_풀이

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

일단 투포인터 말고 sorted로 풀었다. 

<첫번째 시도 : 맞았습니다. %가 늦게 넘어가길래 안되는줄...>

import sys

input = sys.stdin.readline

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

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

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

answer = A + B

print(*sorted(answer))

 

<두번째 시도 : 맞았습니다. sort()활용>

answer.sort()와 sorted(answer)의 시간복잡도는 동일하나, 메모리 효율성 측면에서는 answer.sort()가 원본 데이터를 수정하기 때문에 더 좋다.

import sys

input = sys.stdin.readline

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

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

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

answer = A + B

answer.sort()

print(*answer)

 

sort()와 sorted()는 모두 평균적으로 **시간 복잡도가 O(N log N)**입니다. 여기서 N은 정렬할 원소의 개수를 의미합니다. 따라서 시간 복잡도 측면에서는 두 함수 사이에 차이가 없습니다.

하지만 성능과 메모리 사용 측면에서 차이가 있을 수 있습니다.

차이점

1. sort() (in-place 정렬):
   • 원본 리스트를 직접 수정합니다.
   • 추가 메모리를 거의 사용하지 않습니다.
   • 동일한 리스트에서 정렬을 수행하므로, 메모리 효율성이 더 좋습니다.
   • 파이썬은 TimSort 알고리즘을 사용하며, 시간 복잡도는 **O(N log N)**입니다.
   • 단, 이 과정에서 원본 데이터를 보존하지 않기 때문에 원본 리스트가 필요하다면 미리 복사해야 합니다.
2. sorted() (새로운 리스트 반환):
   • 새로운 리스트를 생성하여 정렬된 결과를 반환합니다.
   • 추가 메모리가 필요합니다. 즉, 원본 리스트의 크기만큼의 추가 공간을 사용하게 됩니다.
   • 원본 리스트를 수정하지 않고 보존할 수 있습니다.
   • 마찬가지로 TimSort를 사용하며, 시간 복잡도는 **O(N log N)**입니다.

시간 복잡도 측면에서는 차이가 없지만:

• 메모리 사용량: sorted()는 새로운 리스트를 생성하기 때문에 추가 메모리가 필요합니다.
• 원본 데이터 보호: sort()는 원본 리스트를 변경하고, sorted()는 원본을 변경하지 않으며, 새로운 리스트를 반환합니다.

결론

시간 복잡도는 둘 다 O(N log N)로 동일합니다. 그러나 메모리 효율성 측면에서는 sort()가 더 유리하며, 원본 데이터 보존 측면에서는 sorted()가 더 유리합니다.

 

<다른 사람 풀이 참고 : 투포인터 활용>

비교

알고리즘시간 복잡도메모리 효율성정렬 상황

투 포인터	O(N + M)	O(N + M)	이미 정렬된 두 리스트를 병합
sort() 사용	O((N + M) log(N + M))	O(N + M)	리스트를 합친 후 전체 정렬

※ while a != N or b != M으로 조건을 걸었을때 

N = 2, M = 2

A = [3, 5]

B = [2, 9]의 조건으로 실행된다면,

1. 첫번째 else구분에서

 A[0] = 3 > B[0] = 2  => answer = [2]이고, b = 1

2. 두번째 else구분에서

A[0] = 3   < B[1] = 9  => answer = [2, 3]이고, a = 1

3. 세번째 else구분에서

A[1] = 5   > B[1] == 9 => answer = [2, 3, 5]이고, a = 2

※여기서 A = 2이니까 while조건에 걸리는데, a != N이 거짓이지만, b != M은 아직 참이므로 while문은 계속 간다.

4. 네번째 if구분에서

a == N이니까 => answer = [2, 3, 5, 9]이고, b = 2a != N 거짓, b != M거짓이므로 while탈출※나의 and or 정립이 조금 잘못되었다.■ and는 두 조건이 모두 참일 경우에만 참인거다.   즉, a == N 또는 b == M의 조건이 1개라도 맞는 순간 while의 조건은 거짓이 됨으로 탈출한다.■or는 두 조건중에서 1개만 참이어도 참인거다.   a == N이지만 b != M이므로 일단 1개만 참이니까 while전체는 참인거고 실행된다.   a == N과 b == M이 동시에 된다면 둘다 거짓이므로 while 전체는 거짓이 되어 탈출한다.

import sys

input = sys.stdin.readline

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

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

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

a, b = 0, 0

answer = []

while a != N or b != M:

#while a < N or b < M: 조건 가능

    if a == N:

        answer.append(B[b])

        b += 1

    elif b == M:

        answer.append(A[a])

        a += 1

    else:

        if A[a] < B[b]:

            answer.append(A[a])

            a += 1

        else:

            answer.append(B[b])

            b += 1

       

print(*answer)

"""

예제 2오류

while a <= N and b <= M:

    if a == N:

        answer.append(B[b])

        a += 1

    elif b == M:

        answer.append(A[a])

        b += 1

    else:

        if A[a] < B[b]:

            answer.append(A[a])

            a += 1

        else:

            answer.append(B[b])

            b += 1

       

print(*answer)

"""