[코딩테스트 공부] 먹을 것인가, 먹힐 것인가

출처 : https://www.acmicpc.net/problem/7795

문제 풀이에 앞서 생각해야할 내용들

일단 문제 풀이에 앞서서, 문제의 조건을 분석할 필요가 있다. 문제의 조건을 보면,

• N, M은 20000까지의 자연수이다
• 시간 제한은 1초이다

인데, 그러면 알고리즘 복잡도는 N^2을 가서는 안 된다는 결론이 나온다.

그러나, 두 리스트를 비교해야하는 문제인데, N^2의 복잡도를 피해서 구현하기란 참 쉽지가 않은데, 나의 결론은 다음과 같았다!

투포인터 기법을 이용하자!

일단 코드부터 확인해볼까요?

import sys

input = sys.stdin.readline

repeat_number = int(input()) # 총 반복횟수

for _ in range(repeat_number):
    sum = 0
    A_len, B_len = map(int, input().split())
    input_A = list(map(int, input().split()))
    input_B = list(map(int, input().split()))
    
    # 정렬
    input_A, input_B = sorted(input_A, reverse=True), sorted(input_B, reverse=True)
    
    # 투포인터 기법을 이용한 비교 시작
    a_index, b_index, count = 0, 0, 0
    
    while a_index < A_len and b_index < B_len:
        if input_A[a_index] > input_B[b_index]:
            count += (B_len - b_index)
            a_index += 1
            
        else:
            b_index += 1
            
    print(count)

코드를 분석해볼까요?

일단 입력받은 리스트를 역순으로 정렬을 해야합니다. 그래야 시작점으로 부터 투 포인터 기법으로 비교 수행이 가능하기 때문입니다.

input_A, input_B = sorted(input_A, reverse=True), sorted(input_B, reverse=True)

그 다음부터는 투 포인터 기법으로 비교를 시행합니다. 투 포인터 비교 방법은 다음과 같습니다 :

• A의 인덱스에 해당하는 수가 B의 인덱스에 해당하는 수보다 큰 경우에는, 어차피 B의 다음 인덱스들의 값보다 클것이기 때문에, A의 인덱스를 다음으로 넘기고, count를 더해줍니다.
• 반대의 경우에는, B의 인덱스를 1만큼 넘겨주면 됩니다. 넘겨줘야만 A와 비교가 가능해지기 때문입니다.

    while a_index < A_len and b_index < B_len:
        if input_A[a_index] > input_B[b_index]:
            count += (B_len - b_index)
            a_index += 1
            
        else:
            b_index += 1

그리고 마무리로, count를 출력하고 끝냅니다.