[백준 / BOJ] 17615 볼 모으기

문제

출처 : https://www.acmicpc.net/problem/17615

17615번: 볼 모으기

빨간색과 파란색으로 이루어진 N개의 연속된 공이 주어진다.

자신의 옆에 다른색의 공이 있다면, 바로 옆에있는 다른색의 공과 같은 색으로 이루어진 공의 집단을 한번에 뛰어넘을수있을때, 최소한의 이동횟수로 같은색 공끼리 모으는 문제다. 단, 공은 처음으로 움직인 공과 같은색의 공만 조작할 수 있다.

---

풀이

그리디 문제였다. N이 500,000이라서 어려워 보이지만, 잘 생각해보면 다음과 같은 논리가 성립함을 알수있다.

 

"뛰어넘는 다른색 공의 갯수를 최대로 하는것이 항상 이득임"

 

예를 들어, 빨간색 공을 모두 맨 뒤로 움직일려고 하는경우, 가장 뒤에있는 빨간색 공부터 맨 뒤로 움직이면, 현재 움직일려는 빨간색 공 뒤에있는 파란색공은 모두 한번에 모여져 있게 되고 각각의 빨간색공은 1의 이동횟수로 가장 뒤로 이동시킬 수 있다.

즉, 다음과 같은 식을 생각할 수 있다.

 

"모든 빨간색공을 맨 뒤로 이동시키는 횟수" = "맨 뒤에 모여져있지않은 빨간색 공의 갯수"

 

이 과정을 총 4번 반복해서 최솟값을 구한 후 출력하면 된다.

1. 빨간색 공을 맨 앞으로 이동시키는 횟수

2. 빨간색 공을 맨 뒤로 이동시키는 횟수

3. 파란색 공을 맨 앞으로 이동시키는 횟수

4. 파란색 공을 맨 뒤로 이동시키는 횟수

 

따라서, 총 O(N)의 시간복잡도로 문제를 풀 수 있다.

 

주요 소스코드

private int getBallMoveCount(char color){
    return Math.min(moveBallToFront(color), moveBallToBack(color));
}

---

전체 소스코드

https://github.com/devxb/JJUNalgo/blob/master/17615%20볼%20모으기/Main.java

GitHub - devxb/JJUNalgo: 백준 알고리즘 소스코드🙃