[JS][백준]17615_볼 모으기

문제 번호

17615번: 볼 모으기

 

 

 

알고리즘 분류

• 그리디 알고리즘

 

문제 풀이

 문제의 조건을 읽어보면 '한번 움직인공과 같은 색의 공만 옮길 수 있다' 라는것을 알 수 있다. 그래서 왼쪽이나 오른쪽에서 시작해서 반대방향으로 가면서 '내가 움직일공과 다른색'의 공이 나오면 그 이후에 등장하는 '내가 움직일 공과 같은색'의 공의 갯수를 세어주면된다.

 RRBRRR이 주어진다고하면 왼쪽부터 살펴보는경우, 빨간색공을 옮긴다고 하면 R , R , 'B'  이후에 나오는 3개의 'R'을 카운트 해준다. 이때 파란색공을 옮길때 역시 같은 방법으로 카운트해준다. 마찬가지로 오른쪽에서부터 살펴보는 경우도 살펴본다. 이렇게 살펴본 4가지 방법중에 가장 적은수가 나오는 방법이 문제의 답이다.

 처음에는 예제만보고 공을 오른쪽으로만 옮길 수 있는줄 알았는데 공을 방향에는 제한이 없다.

 

전체코드

function sol(balls) {
   let answer = Infinity;

   // 빨간공을 움직일 경우.
   let check = false;
   let cnt = 0;
   for (let i = balls.length - 1; i >= 0; i--) {
      if (balls[i] === 'B') {
         check = true;
      }
      if (check && balls[i] === 'R') {
         cnt++;
      }
   }
   if (cnt < answer) answer = cnt;
   check = false;
   cnt = 0;
   for (let i = 0; i < balls.length; i++) {
      if (balls[i] === 'B') {
         check = true;
      }
      if (check && balls[i] === 'R') {
         cnt++;
      }
   }
   if (cnt < answer) answer = cnt;

   // 파란공을 움직일 경우.
   check = false;
   cnt = 0;
   for (let i = balls.length - 1; i >= 0; i--) {
      if (balls[i] === 'R') {
         check = true;
      }
      if (check && balls[i] === 'B') {
         cnt++;
      }
   }
   if (cnt < answer) answer = cnt;
   check = false;
   cnt = 0;
   for (let i = 0; i < balls.length; i++) {
      if (balls[i] === 'R') {
         check = true;
      }
      if (check && balls[i] === 'B') {
         cnt++;
      }
   }
   if (cnt < answer) answer = cnt;
   
   return answer;
}
function main() {
   const input = require('fs').readFileSync('input.txt').toString().trim().split('\n');
   let balls = input[1].split('');
   console.log(sol(balls));
}
main();

특이사항

 문제의 조건을 잘 확인하자.