문제
로봇을 좋아하는 세희는 로봇동아리에서 카메라와 센서, 라즈베리 파이, 집게발을 이용해 로봇을 완성하였다. 이 로봇을 통해서 오셀로 재배치라는 작업을 하려고 한다. 오셀로 말은 앞면이 검정, 뒷면이 흰색으로 된 말이다. 세희의 목표는 로봇을 이용하여 처음 배치된 오셀로 말을 주어진 형태로 바꾸는 일을 하는 것이다. 아래의 예시를 참고하자.
| 초기 상태 | 목표 상태 |
|---|---|
| ○●●○○ | ○●○●○ |
세희는 로봇을 이용해 2가지 작업 중 하나를 골라 진행할 수 있다.
- 배치된 말 중 임의의 2개의 말을 골라 서로의 위치를 바꾼다.
- 말 1개를 들어 뒤집어 놓아 색상을 변경한다.
위의 예시에서, 3번째와 4번째 말을 2번 작업을 통해 각각 뒤집으면 2번의 작업으로 목표 상태를 만들 수 있다. 하지만 1번 작업을 통해 3번째와 4번째 말을 골라 서로의 위치를 바꾸어주면 1번 만에 목표 상태에 도달할 수 있다. 초기 상태의 말과 목표 상태의 말이 주어질 때, 목표 상태에 도달할 수 있는 최소 횟수를 구하는 프로그램을 작성하시오.
제한 조건
- 제한 시간 : 2초
- 풀이 시간 : 30분
입력
- 입력 데이터는 표준 입력을 사용한다.
- 입력은 T개의 테스트 데이터로 구성된다.
- 각 입력의 첫 번째 줄에는 오셀로 말의 개수 N(1 ≤ N ≤ 100,000)이 주어진다.
- 각 입력의 두 번째 줄과 세 번째 줄에는 각각 오셀로 말의 초기 상태와 목표 상태가 주어진다.
- 초기 상태와 목표 상태의 말의 개수는 항상 N과 일치한다.
- 흰색 면이 보이는 경우에는 W, 검은색 면이 보이는 경우에는 B로 주어진다.
출력
- 출력은 표준 출력을 사용한다.
- 입력받은 데이터에 대해, 한 줄에 1개씩 초기 상태에서 목표 상태를 만들기 위한 작업의 최소 횟수를 구한다.
예시
| 입력 | 출력 |
|---|---|
| 3 5 WBBWW WBWBW 7 BBBBBBB BWBWBWB 4 WWBB BBWB | 1 3 2 |
풀이
이 문제는 2가지에 초점을 잡고 풀이할 수 있다.
- 모든 말이 동일한 상태를 가지고 있는가?
- 목표하는 말의 배치와 다른 상태를 가진 말들은 얼마나 있는가?
우선 1번의 접근은 매우 간단하다. 모든 말들이 동일한 상태를 가질 경우 위치를 바꿀 수 있는 말이 존재하지 않기 때문에 작업 2번만 진행하면 된다.
2번의 경우도 생각보다 단순하게 해결된다. 먼저 목표하는 말과 다른 상태를 가진 말들 중에서 W, B 상태 각각 말의 개수를 파악한다.
예를 들어 W가 3개, B가 2개일 경우, B 2개와 W 2개는 서로 위치를 변경하는 1번 작업을 수행할 수 있다. 남은 W 1개는 위치를 변경할 대상이 없으므로 2번 작업을 수행하게 되므로 총 3번 작업하게 된다.
이 예시를 통해 알 수 있는 것은 상태 W, B를 가진 말들 중 개수가 더 많은 것이 최소 작업의 횟수가 된다는 것이다.
이 풀이는 시간 복잡도 O(N)을 가지며, 말의 최대 개수인 10만개를 가진 T가 1000을 넘지 않을 경우 풀이가 가능하다.
이슈
처음 코드를 작성하려고 했을 때, T번 입력을 받을 때마다 알고리즘을 처리하게 했다. 하지만 이렇게 하면 마지막 readLine에 \n이 입력되지 않은 상태이므로 마지막 연산의 결과에 enter를 한 번 더 입력해줘야 한다. 결과적으로 마지막 케이스의 결과가 한 줄 띄우고 출력하게 되므로 문제가 원하는 양식에 맞지 않게 된다.
여러번 입력받아야 할 경우에는 초기에 한 번에 다 입력받은 후에 알고리즘을 처리하도록 하자.
코드
