BOJ 1524 - 세준세비

문제

BOJ 1524 - 세준세비

세준이와 세비의 병사들이 전투한다. 양측에서 가장 약한 병사끼리 싸우며, 약한 쪽이 죽는다. 전투력이 같으면 세비의 병사가 죽는다. 어느 쪽이 이기는지 구하라.

입력

첫째 줄에 테스트 케이스 수 T, 각 케이스마다 N, M과 각 군대의 전투력이 주어진다.

출력

세준이가 이기면 S, 세비가 이기면 B, 비기면 D를 출력한다.

예제

풀이

양측의 최대 전투력만 비교하면 승자를 결정할 수 있다. 가장 강한 병사가 모든 상대 병사를 이기기 때문이다.

1. 각 군대의 전투력 배열에서 최대값을 구한다
2. 세준이의 최대 전투력이 세비의 최대 전투력 이상이면 S (같을 때도 세준이 승리)
3. 세비의 최대 전투력이 더 크면 B

핵심 아이디어: 가장 약한 병사부터 싸우므로, 최대 전투력이 높은 쪽의 최강 병사가 상대를 모두 이긴다. 같을 때 세비가 불리하므로 세준이 유리하다.

코드

n = int(input())
for i in range(n):
  tmp = input()
  n, m = map(int,input().split())
  n = max(list(map(int,input().split())))
  m = max(list(map(int,input().split())))
  if n >= m:
    print("S")
  else:
    print("B")

복잡도

• 시간: O(T × (N + M))
• 공간: O(N + M)