[99클럽] 비기너 코딩테스트 스터디 TIL - 백준, 1524

 

1. 문제풀이

1) 문제, 세준세비 (백준 1524)

세준이와 세비는 온라인 게임을 즐겨한다. 이 온라인 게임에서는 군대를 서로 키울 수 있다.

세준이는 N명의 병사를 키웠고, 세비는 M명의 병사를 키웠다. 이제 서로 전쟁을 하려고 한다.

전쟁은 여러 번의 전투로 이루어진다. 각 전투에서 살아있는 병사중 제일 약한 병사가 죽는다.

만약 제일 약한 병사가 여러 명이고, 제일 약한 병사가 모두 같은 편에 있다면, 그 중에 한 명이 임의로 선택되어 죽는다.

하지만, 제일 약한 병사가 여러 명이고, 양 편에 모두 있다면, 세비의 제일 약한 병사 중 한 명이 임의로 선택되어 죽는다.

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

 

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. T는 100보다 작거나 같다. 각 테스트 케이스는 다음과 같이 이루어져 있다.

첫째 줄에 N과 M이 들어오고, 둘째 줄에는 세준이의 병사들의 힘이 들어오고, 셋째 줄에는 세비의 병사들의 힘이 들어온다.

힘은 정수이고, 이 값이 클수록 강하고, 작을수록 약하다.

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

 

출력

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

2) 해석

• 각 테스트 케이스에 대해서 한 줄에 하나씩 차례로 승자 출력
• 세준이 win = "S", 세비 win = "B", 둘다x = "C"
• 전쟁 = 여러 번
• 살아 있는 병사 중 제일 약한 병사가 죽음
• 제일 약한 병사 여러 명 > 그 중 하나가 죽음
• 둘 힘이 같음 > 세비의 약한 병사가 죽음
• 한 명의 병사가 남아 있을 때까지
• 첫 줄 = 테스트 케이스 개수
• 테스트 케이스
• 첫 줄 = 세준이 병사 수 / 세비 병사 수
• 둘째 줄 = 세준이 병사 힘
• 셋째 줄 = 세비 병사 힘

 

 

• 세빈, 세준 병사 힘 내림차순 정렬
• 맨 뒤에 있는 것(가장 약한 병사)들끼리 싸움
• 더 약한 병사 > pop()
• 같으면 세비 병사 pop()
• 둘 중 하나의 병사가 남아 있을 때까지 반복

 

 

3) 풀이

const fs = require("fs");
const input = fs
  .readFileSync(0, "utf-8")
  .toString()
  .trim()
  .split("\n\n")
  .map((item) => item.split("\n"));

const T = Number(input[0][0]); //반복 횟수
const win = []; //승자, 출력

for (let i = 1; i < T + 1; i++) {
  const testCase = input[i];

  const soldierPower1 = testCase[1]
    .split(" ")
    .map(Number)
    .sort((a, b) => b - a); // 세준

  const soldierPower2 = testCase[2]
    .split(" ")
    .map(Number)
    .sort((a, b) => b - a); // 세비

  while (soldierPower1.length > 0 && soldierPower2.length > 0) {
    const weakest1 = soldierPower1[soldierPower1.length - 1];
    const weakest2 = soldierPower2[soldierPower2.length - 1];

    if (weakest1 < weakest2) soldierPower1.pop();
    else soldierPower2.pop();
  }

  if (soldierPower1.length === 0) win.push("B");
  else if (soldierPower2.length === 0) win.push("S");
  else win.push("C");
}

console.log(win.join("\n"));

 

const input = fs
  .readFileSync(0, "utf-8")
  .toString()
  .trim()
  .split("\n\n")
  .map((item) => item.split("\n"));

const T = Number(input[0][0]); //반복 횟수
const win = []; //승자, 출력

for (let i = 1; i <= T; i++) {
 ...
}

 

우선 입력을 묶음단위로 받아오기 위해서 split()와 map을 사용해줬다.

입력에서 \n\n 로 나눠준 다음, 각 배열에서 \n로 다시 나눠줬다.

그리고 가장 첫 번째 입력 값을 T 변수에 담아줬다.

 

win은 이긴 사람을 담아줄 배열이다. 

그 후 T만큼 코드를 반복해줬다. 

 

 

const testCase = input[i];

const soldierPower1 = testCase[1]
  .split(" ")
  .map(Number)
  .sort((a, b) => b - a); // 세준

const soldierPower2 = testCase[2]
  .split(" ")
  .map(Number)
  .sort((a, b) => b - a); // 세비

 

이제 반복문 안에서는 세빈, 세준이의 싸움을 구현할 것이다.

 

우선 testCase 변수를 생성해 현재 반복문에서의 테스트 케이스르 넣어준다.

그리고 세준, 세비의 병사들을 힘 기준, 내림차순 배열로 만들어준다.

내림차순을 사용한 이유는, pop()으로 제거하는 것이 시간복잡도 상 좋기 때문이다.

가장 약한 병사부터 비교해서 더 약한 병사를 pop으로 제거해 줄 것이다. 

 

처음에 map(Number)을 안해서 에러가 발생했다.

testCase에 있는 숫자들을 문자열로 되어 있기 때문에 모두 숫자로 바꿔준 후 정렬해줘야 한다.

그렇지 않으면 숫자 비교와는 다른 값이 출력된다. 

 

 

while (soldierPower1.length > 0 && soldierPower2.length > 0) {
  const weakest1 = soldierPower1[soldierPower1.length - 1];
  const weakest2 = soldierPower2[soldierPower2.length - 1];

  if (weakest1 < weakest2) soldierPower1.pop();
  else soldierPower2.pop();
}

 

이제 while문으로 세준이와 세비의 병사 중 하나의 병사가 남을때까지 싸워준다.

각 병사들의 마지막을 비교해서 세비의 병사 힘이 더 크다면 세준이 병사를 pop(), 그렇지 않다면 세비 병사를 pop() 해준다.

조건에 세준이와 세비 병사의 힘이 같을 경우, 세비가 졌다고 판단하므로 else if가 아닌 else를 사용해줬다. 

 

 

if (soldierPower1.length === 0) win.push("B");
else win.push("S");

 

마지막으로 배열에 값이 남아있는 사람을 기준으로 win에 우승자를 넣어준다.

 

사실 문제에는 둘 다 아닌 경우 C를 출력하라는 말이 있었지만,

세준이와 세비의 힘이 같을 경우 세비가 졌다고 판단하므로 C가 출력되는 일은 없다. 

따라서 세비가 이긴게 아닌 경우, S(세준이 승)를 넣어주도록 만들었다. 

 

 

- 걸린 시간

 

2. 리팩토링

다른 방법이 없을까하고 맞힌 사람 정답지를 훑어봤다.

그러던 중 훨씬 성능을 좋게 코드를 개선할 수 있는 방법이 있어서 수정해봤다. 

 

for (let i = 1; i <= T; i++) {
  const [_, sejunSoldier, sebiSoldier] = input[i];

  const sejunMax = Math.max(...sejunSoldier.split(" ").map(Number));
  const sebiMax = Math.max(...sebiSoldier.split(" ").map(Number));

  if (sejunMax < sebiMax) win.push("B");
  else win.push("S");
}

console.log(win.join("\n"));

 

기존의 코드는 직접 시뮬레이션을 돌려서, 마지막에 남은 병사를 가지고 판단하는 것이었다.

그런데 가장 힘이 센 병사만 체크해도 같은 결과를 낼 수 있다.

 

병력은 가장 약한 병사부터 차례로 제거된다. 따라서 최종적으로 가장 강한 병사가 남게된다.

최후에 남는 병사만 비교해도 값은 같기 때문에 가장 강한 병사만 비교해도 되는 것이다. 

이렇게하면 굳이 while문을 써서 반복문을 또 돌리지 않아도 된다.

 

위처럼 max를 이용해 각 병사들 중 가장 강한 병사만 체크하고, 해당 병사들의 힘을 비교해서 출력하면 된다. 

 

 

코드 양도 줄고, 공간복잡도, 시간복잡도 둘 다 줄어든다.