[백준] 세준세비 (Python)

문제

세준이와 세비는 온라인 게임을 즐겨한다. 이 온라인 게임에서는 군대를 서로 키울 수 있다. 세준이는 N명의 병사를 키웠고, 세비는 M명의 병사를 키웠다.

이제 서로 전쟁을 하려고 한다.

전쟁은 여러 번의 전투로 이루어진다. 각 전투에서 살아있는 병사중 제일 약한 병사가 죽는다. 만약 제일 약한 병사가 여러 명이고, 제일 약한 병사가 모두 같은 편에 있다면, 그 중에 한 명이 임의로 선택되어 죽는다. 하지만, 제일 약한 병사가 여러 명이고, 양 편에 모두 있다면, 세비의 제일 약한 병사 중 한 명이 임의로 선택되어 죽는다.

전쟁은 한 명의 병사를 제외하고 모두 죽었을 때 끝난다. 전쟁의 승자를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. T는 100보다 작거나 같다. 각 테스트 케이스는 다음과 같이 이루어져 있다. 첫째 줄에 N과 M이 들어오고, 둘째 줄에는 세준이의 병사들의 힘이 들어오고, 셋째 줄에는 세비의 병사들의 힘이 들어온다. 힘은 정수이고, 이 값이 클수록 강하고, 작을수록 약하다.

각 테스트 케이스는 줄 바꿈으로 구분되어 있다.

출력

각 테스트 케이스에 대해서 한 줄에 하나씩 차례대로 승자를 출력한다. 세준이가 이기면 S를 세비가 이기면 B를 둘다 아닐 경우에는 C를 출력한다.

제한
1 ≤ N, M ≤ 1,000,000
병사들의 힘은 300,000,000보다 작거나 같은 자연수이다.

예제 입력 1

2

1 1
1
1

3 2
1 3 2
5 5

예제 출력 1

S
B

최종까지 가는 과정의 코드

# #N, M명의 병사
# # 양쪽 모두 약한 병사면 세비의 약한 병사중 한명 죽이기
# # 1명남을때까지 전쟁

# import sys

# input = sys.stdin.read
# data = input().strip().split()

# T = int(data[0])
# index = 1

# result = []

# for _ in range(T):
#   N = int(data[index])
#   M = int(data[index+1])
#   index += 2
  
#   S_army = list(map(int, data[index:index+N]))
#   B_army = list(map(int, data[index + N: index + N + M]))
#   index += N + M
  
#   # S_army.sort()
#   # B_army.sort()
#   # heapq.heapify(S_army)
#   # heapq.heapify(B_army)
  

#   # print(S_weak_army)
#   while len(S_army) > 0 and len(B_army) > 0:
#     S_weak_army = min(S_army)
#     B_weak_army = min(B_army)
    
#     if S_weak_army == B_weak_army:
#       B_army.remove(B_weak_army)
#     # heapq.heappop(B_weak_army)
#     elif S_weak_army > B_weak_army:
#       B_army.remove(B_weak_army)
#     else:
#       S_army.remove(S_weak_army)
    
# if len(S_army) >= 1:
#   print("S")
# elif len(B_army) >= 1:
#   print("B")
# else:
#   print("C")
#   # for i in range(N):
#   #   S_army_list = []
#   #   S_army_list.append(data[index])
#   #   index += 1
#   # for j in range(M):
#   #   B_army_list = []
#   #   B_army_list.append(data[index])
#   #   index += 1

#   # print(S_weak_army)
#   # print(B_weak_army)
# # S_army_list.sort(reverse=True)
# # B_army_list.sort(reverse=True)

# # if S_army_list[0]

• 일단 코드가 너무 길어서 가독성이 좋지도 않고, 데이터 흐름도 파악하기 어려울 뿐만 아니라 결과적으로 정답인 코드도 아니였다.
  heapq에 대해서도 처음 써봐서 그부분만 좀 체크하면 좋을 것 같은데

heapq이란?
최소 힙 자료 구조를 제공하는 모듈
1. 최소 힙

• 기본적으로 최소 힙을 제공
  (최소 힙의 특징)
• heapq.heappush(heap, item) : item을 heap에 추가
• heapq.heappop(heap) : heap에서 최소 값 제거하고 반환
• heapq.heapify(iterable) : iterable을 힙으로 변환
• heapq.heappushpop(heap, item) : item을 heap에 추가하고 최소 값제거한 후 반환
• heapq.heapreplace(heap, item): heap의 최소 값 제거, item 추가
  (왜 heapq를 사용하는가?)
• 빠른 최소값 추출 : 최소 힙은 O(log N) 시간 복잡도로 최소값을 삽입하거나 제거할 수 있음. 빠르게 최소값 추출하고 싶을 때 유용
• 우선순위 큐 구현 : 최소 힙을 기반으로 하여 구현
• 효율적인 연산 : 빈번한 최소값 삽입 및 제거할 때 성능 높일 수 있음

최종 코드

# 테스트 케이스 T
T = int(input())
# T만큼 반복하면서
for _ in range(T):
  #첫 공백
  input()
  #N과 M 
  N, M = map(int, input().split())
  #S의 병사 힘 목록 내림차순
  S_army_power = sorted(list(map(int, input().split())), reverse=True)
  #B의 병사 힘 목록 내림차순
  B_army_power = sorted(list(map(int, input().split())), reverse=True)
  
  # 둘다 요소가 남아있다면 계속 while문 실행
  while S_army_power and B_army_power:
    # S와 B가 같으면 B를 제거해야하므로, >=
    if S_army_power[-1] >= B_army_power[-1]:
      B_army_power.pop()
    #S가 더 작을 경우
    else:
      S_army_power.pop()
  
  # S만 남았으면
  if S_army_power:
    print("S")
  # B만 남았으면
  elif B_army_power:
    print("B")
  #둘 다 아닐 경우
  else:
    print("C")

• T로 테스트 케이스 개수 담기
• T만큼 반복하면서 첫 공백은 input()처리, N, M을 map처리해서 담기
• 병사 힘을 sorted(, reverse=True)를 활용하여 큰 수부터 내림차순으로 정렬
• 둘 다 요소가 1개라도 있다면 가장 끝에 있는 값을 비교해서 pop으로 제거