BOJ(백준) 7795[먹을 것인가 먹힐 것인가]

1. 문제 설명

안녕하세요! 오늘은 백준 온라인 저지의 문제 번호 7795번을 풀어보겠습니다. 이 문제는 주어진 두 리스트에서 특정 조건을 만족하는 쌍의 개수를 찾는 문제입니다. 

 

문제 URL: https://www.acmicpc.net/problem/7795

 

2. 접근법

1. 각 테스트 케이스마다 두 개의 리스트 A와 B가 주어집니다.

2. A의 원소 중 하나와 B의 원소 중 하나를 선택했을 때, A의 원소가 B의 원소보다 클 때 해당 쌍을 세어야 합니다.

3. 리스트 A와 B를 정렬합니다.

4. A의 각 원소에 대해 B의 원소들과 비교하여 몇 개의 원소가 조건을 만족하는지 카운트합니다.

5. 투 포인터 기법을 사용하여 효율적으로 쌍의 개수를 셉니다:

• A 리스트와 B 리스트의 포인터를 각각 시작점에 둡니다.

• A 리스트의 현재 원소가 B 리스트의 현재 원소보다 크면, 조건을 만족하는 쌍의 개수를 세고 B 리스트의 포인터를 증가시킵니다.

• 그렇지 않으면 A 리스트의 포인터를 증가시킵니다.

• 이 과정을 리스트 A의 모든 원소에 대해 반복합니다.

3. 정답 코드

import sys
input = sys.stdin.readline

# 각 테스트 케이스 수를 입력받음
T = int(input())
# 각 테스트 케이스의 결과를 저장할 리스트
ans = [0] * T

for i in range(T):
    # 각 테스트 케이스에서 N과 M을 입력받음
    N, M = map(int, input().split())
    # A와 B 리스트를 입력받고 정렬함
    A = sorted(list(map(int, input().split())))
    B = sorted(list(map(int, input().split())))
    
    cnt = 0     # 큰 쌍의 개수를 세기 위한 변수
    a = 0       # A 리스트의 인덱스
    b = 0       # B 리스트의 인덱스

    # A 리스트의 모든 원소를 확인할 때까지 반복
    while a < N:
        if b == M:    # B 리스트의 끝에 도달한 경우
            cnt += b  # 현재까지의 b 값을 cnt에 더함
            a += 1    # A 리스트의 다음 원소로 이동
        else:
            if A[a] <= B[b]:  # A의 현재 원소가 B의 현재 원소보다 작거나 같은 경우
                cnt += b  # 현재까지의 b 값을 cnt에 더함
                a += 1    # A 리스트의 다음 원소로 이동
            else:
                b += 1  # A의 현재 원소가 B의 현재 원소보다 큰 경우, B의 다음 원소로 이동

    # 현재 테스트 케이스의 결과를 저장
    ans[i] = cnt

# 각 테스트 케이스의 결과를 출력
for i in range(len(ans)):
    print(ans[i])

 

4. 코드 설명

1. 먼저 테스트 케이스 수를 입력받고, 각 테스트 케이스의 결과를 저장할 리스트를 초기화합니다.

2. 각 테스트 케이스에 대해 다음의 과정을 수행합니다:

• N과 M을 입력받고, A와 B 리스트를 입력받아 정렬합니다.

• 두 리스트에서 조건을 만족하는 쌍의 개수를 세기 위해 변수들을 초기화합니다.

• A 리스트의 모든 원소를 확인하면서, B 리스트의 원소와 비교하여 조건을 만족하는 쌍의 개수를 셉니다.

• 각 테스트 케이스의 결과를 저장합니다.

3. 모든 테스트 케이스의 결과를 출력합니다.

 

[주요 로직 - while 문]

• while a < N: A 리스트의 모든 원소를 확인할 때까지 반복합니다.

• if b == M: B 리스트의 끝에 도달한 경우, 현재까지의 b 값을 cnt에 더하고 A 리스트의 다음 원소로 이동합니다.

• if A[a] <= B[b]: A의 현재 원소가 B의 현재 원소보다 작거나 같은 경우, 현재까지의 b 값을 cnt에 더하고 A 리스트의 다음 원소로 이동합니다.

• else: A의 현재 원소가 B의 현재 원소보다 큰 경우, B 리스트의 다음 원소로 이동합니다.

 

5. Github으로 확인

coTest/BOJ/BOJ01_02_05_7795.py at main · pcy4196/coTest