[브론즈 1] 백준 1524 - 세준세비 (파이썬)

https://www.acmicpc.net/problem/1524

 

세준(S)과 세비(B)가 각각 병사를 가지고 있다. 병사들끼리 전투를 하는데, 가장 약한 병사들끼리 싸운다.

전투 규칙은 다음과 같다.

1. 세준의 최약체 ≥ 세비의 최약체 → 세비의 병사가 죽는다.

2. 세준의 최약체 < 세비의 최약체 → 세준의 병사가 죽는다.

둘 중 한 쪽의 병사가 전멸할 때까지 반복한다.

이 문제에서 조건에 따라서 양쪽 진영의 최약체만 비교하면 된다. 파이썬 리스트 기본 함수인 pop을 사용했으며 O(1)의 시간복잡도를 가진다.

또한 정렬을 미리 해주었기 떄문에 -1 번 인덱스의 값이 항상 최약체의 값이다.

아래 코드는 내가 작성하였지만 사실 이 문제는 시뮬레이션을 다 돌릴 필요가 없는 문제이다. 규칙상 세준이의 최약제 >= 세비의 최약체 라면 세비만 계속 죽기 때문이다.

즉, 양 진영의 최강 병사 중 더 강한 쪽이 반드시 승리한다고 생각 할 수 있다.

T = int(input())
for _ in range(T) :
    input()  # 공백 줄 처리
    N, M = map(int, input().split())  # 세준, 세비 병사 수
    sejuns = list(map(int, input().split()))  # 세준 병사 힘
    sebis = list(map(int, input().split()))   # 세비 병사 힘

    # 강한 순서로 정렬
    sejuns.sort(reverse = True)
    sebis.sort(reverse = True)
    
    # 전투 시뮬레이션
    while sejuns and sebis :
        if sejuns[-1] >= sebis[-1] :  # 세준의 최약체가 세비의 최약체보다 강하거나 같음
            sebis.pop()  # 세비 병사 제거
        else :
            sejuns.pop()  # 세준 병사 제거
    
    # 결과 판별
    if sejuns : 
        print("S")
    elif sebis :
        print("B")
    else :
        print("C")

 

T = int(input())
for _ in range(T):
    input()
    N, M = map(int, input().split())
    sejuns = max(map(int, input().split()))
    sebis = max(map(int, input().split()))

    if sejuns >= sebis:
        print("S")
    else:
        print("B")