[백준] 1524 - 세준세비

 

문제 출처: https://www.acmicpc.net/problem/1524

 

문제

세준과 세비는 전쟁 게임을 한다.
세준은 N명의 병사가 있고, 세비는 M명의 병사가 있다.
전쟁은 여러번의 전투로 이루어진다.
전투에서는 살아있는 병사중 가장 약한 병사가 죽는다.
제일 약한 병사가 여러명이고 그들이 같은 편에 있으면 그 중 한 명이 임의로 죽는다.
제일 약한 병사가 여러명이고 그들이 양쪽 편에 모두 있으면 세비의 제일 약한 병사 중 한 명이 임의로 죽는다.
전쟁은 한 명의 병사를 제외하고 모두 죽었을 때 끝난다.

 

 

입력

• 첫째 줄에 테스트 케이스 개수 T가 주어진다.(T<=100)
• 각 테스트 케이스는 첫째 줄에 N과 M이 들어오고, (1<=N,M<=1,000,000)
• 둘째 줄에 세준이의 병사들의 힘이 들어오고
• 셋째 줄에 세비의 병사들의 힘이 들어온다.
• 힘은 정수이며 값이 클수록 강하다.

 

출력

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

 

처음 작성한 코드

import sys

T = int(sys.stdin.readline().strip())

for _ in range(T):
    sys.stdin.readline()
    N, M = map(int, sys.stdin.readline().strip().split())
    
    sejun = []
    sebie = []

    sejun = list(map(int,sys.stdin.readline().strip().split()))
    sebie = list(map(int,sys.stdin.readline().strip().split()))

    sejun.sort(reverse=True)
    sebie.sort(reverse=True)

    while True:
        if(len(sejun)==0 and len(sebie)>=1):
            print('B')
            break
        elif(len(sejun)>=1 and len(sebie)==0):
            print('S')
            break

        if(sejun[0]>=sebie[0]):
            sebie.pop()
        else:
            sejun.pop()

 

처음에 이 코드를 제출하고 나서 다시 봤을 때... 왜 이게 맞지??? 싶었다.

 

내가 의도한대로 작성하려면

if(sejun[0]>=sebie[0])이 if(sejun[-1]>=sebie[-1]이 되어야 하기 때문이다.

그래야 맨 마지막 요소를 비교하고 작은 값을 pop 할 수 있다.

 

게다가 C를 출력하는 경우는 처리하지도 않았다...

전쟁은 한 명의 병사를 제외하고 모두 죽었을 때 끝난다는 문장이 있어서

둘 중 한 명에게 병사가 2명 이상 남았으나 나머지 한 명에게 병사가 남아있지 않으면, C를 출력하는 거라고 생각했는데 아니었고

C를 출력하는 경우의 수를 포함하지 않아도 정답 처리가 되었다.

 

그런데 사실 이 문제는 세준과 세비가 가진 가장 큰 요소만 비교하면 결과를 알 수 있는 문제였다.😨

왜 맞았을지 몇번을 생각하다가 깨달았다. 왜 이걸 못 떠올렸을까...

 

세준이 가진 가장 큰 요소가 세비가 가진 가장 큰 요소보다 크거나 같으면,

결국 마지막에는 세준이 가진 가장 큰 요소가 남고 세비의 모든 요소들을 이기고 세준이 전투에서 승리하게 된다.

그래서 정렬할 필요도 없고 while문을 돌 필요도 없이 max 함수만 사용하면 바로 결과를 출력할 수 있다.

 

완성한 코드

import sys

T = int(sys.stdin.readline().strip())

for _ in range(T):
    sys.stdin.readline()
    N, M = sys.stdin.readline().strip().split()

    sejun = list(map(int,sys.stdin.readline().strip().split()))
    sebie = list(map(int,sys.stdin.readline().strip().split()))

    if(max(sejun)>=max(sebie)):
       print('S')
    else:
       print('B')

 

이 코드에서도 N, M을 어차피 사용하지 않기 때문에 저장할 필요가 없다.

한 줄 공백을 넘기기 위해 6번째 라인에 넣은 것처럼 sys.stdin.readline()만 하고 넘어가도 된다.

 

이렇게 하면 앞서 작성한 코드보다 100ms가량 빨라지며 코드 길이도 절반 이하로 줄어든다.

시간복잡도 역시 줄어든다.