백준 23328 - 마을 구하기 (Javascript)

문제 링크

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

23328번: 마을 구하기

 

풀이

몇 번 끄적여보며 잘 관찰하면, '사전순으로 가장 앞서는 배치'라는 조건 때문에 폭탄을 연속으로 배치해야 한다는 사실을 알 수 있습니다.

예를 들면 다음처럼요.

'bBBbb' < 'bBbBb' 

 

위 사실을 전제로 폭탄을 배치해 봅시다. 확정적인 케이스부터 처리해 나가면 어렵지 않습니다.

터지는 폭탄을 bomb, 그에 맞는 쉴드를 shield, 터지지 않는 폭탄을 upper, 그 외 쉴드들을 lower라 하겠습니다.

 

1. bomb보다 사전적으로 앞서는 upper가 없음

폭탄 뭉치를 왼쪽 끝에 배치하면 피해를 최소화하며 사전순으로 가장 앞서는 배치가 됩니다.

 

2. 실드가 하나 이하

피해를 최소화하기 위해 폭탄을 왼쪽, 혹은 오른쪽 끝에 배치해야 합니다. ('BBxx' vs 'xBBx' vs 'xxBB')

이때 bomb보다 사전적으로 앞서는 upper가 없다면 왼쪽 끝, 있으면 오른쪽 끝에 배치하는 것이 사전순 최적입니다.

전자의 케이스는 1번에서 확인했으니 자연스럽게 오른쪽 끝에 배치할 수 있습니다.

 

3. 그외

폭탄과 실드의 조합에 대해서, 사전순으로 최적이 되려면 'bBBb(bb..)'와 같이 배치하여야 합니다.

저런 꼴의 배치를 하나의 뭉텅이로 생각해서 전체적으로 최적 사전순이 되게끔 배치합시다.

 

1) upper들을 우선적으로 앞에 배치합니다.

2) shield보다 앞서는 lower들을 배치합니다.

3) 쉴-폭-쉴을 배치합니다.

4) 남은 lower를 배치합니다.

 

 

 

정답 코드

// @BOJ ------------------------------------------
const read = (() => {
  const stdin = require('fs').readFileSync('/dev/stdin').toString().split('\n');
  let i = 0;
  return () => stdin[i++];
})();

// Solution -----------------------------------
const divide = r => s => [s.match(r) ?? [], s.replace(r, '').split('')];
const isEmpty = a => !a?.length;
const join = (...as) => as.map(a => a.join('')).join('');
const asc = (a, b) => a < b;

const solve = (uppers, lowers, bombs, shields) => {
  const isBombFirst = isEmpty(uppers) || asc(bombs[0], uppers[0]);

  const aShield = shields.slice(0, 1);
  const [, ...restShields] = shields;

  if (isBombFirst) {
    return join(bombs, aShield, uppers, lowers.concat(restShields).sort());
  } else if (shields.length <= 1) {
    return join(uppers, lowers, aShield, bombs);
  } else {
    const lowerF = lowers.filter(c => c < aShield[0]);
    const lowerB = lowers.filter(c => c > aShield[0]);
    return join(uppers, lowerF, aShield, bombs, restShields, lowerB);
  }
};

const solution = function () {
  const bomb = read().split(' ')[1];
  const s = read().split('').sort().join('');

  const shield = bomb.toLowerCase();

  const divideBomb = divide(new RegExp(`[${bomb}${shield}]`, 'g'));
  const divideUpper = divide(/[A-Z]/g);

  const [targets, rest] = divideBomb(s);
  const [uppers, lowers] = divideUpper(rest.join(''));
  const [bombs, shields] = divideUpper(targets.join(''));

  const ans = solve(uppers, lowers, bombs, shields);
  console.log(ans);
};

solution();