[백준] #20365 블로그 2 (python)

20365번: 블로그2 (acmicpc.net)

20365번: 블로그2

 

문제

neighbor 블로그를 운영하는 일우는 매일 아침 풀고 싶은 문제를 미리 정해놓고 글을 올린다. 그리고 매일 밤 각각의 문제에 대하여, 해결한 경우 파란색, 해결하지 못한 경우 빨간색으로 칠한다. 일우는 각 문제를 칠할 때 아래와 같은 과정을 한 번의 작업으로 수행한다.

1. 연속된 임의의 문제들을 선택한다.
2. 선택된 문제들을 전부 원하는 같은 색으로 칠한다.

예를 들어, 각 문제를 위와 같은 색으로 칠하려고 할 때, 1~2번 문제를 파란색, 3번을 빨간색, 4번을 파란색, 5번을 빨간색, 6~7번을 파란색, 8번을 빨간색으로 칠하는 작업을 순서대로 수행하면 6번의 작업을 거쳐야 한다. 하지만, 1~7번 문제를 파란색, 3번을 빨간색, 5번을 빨간색, 8번을 빨간색으로 순서대로 칠한다면 작업 횟수는 4번으로 가장 적다.

일우는 매일 500,000문제까지 시도하기 때문에, 이 작업이 꽤나 귀찮아지기 시작했다. 그래서 가장 효율적인 방법으로 위 작업을 수행하기를 원한다. 일우를 도와 각 문제를 주어진 색으로 칠할 때 필요한 최소한의 작업 횟수를 구하는 프로그램을 작성하라.

입력

첫째 줄에 색을 칠해야 하는 문제의 수 N (1 ≤ N ≤ 500,000)이 주어진다.

둘째 줄에 N개의 문자가 공백 없이 순서대로 주어진다. 각 문자는 i번째 문제를 어떤 색으로 칠해야 하는지를 의미하며, R은 빨간색, B는 파란색을 나타낸다. 그 외에 다른 문자는 주어지지 않는다.

출력

첫째 줄에 일우가 주어진 모든 문제를 원하는 색으로 칠할 때까지 필요한 작업 횟수의 최솟값을 출력하라.

 

예제 입력1

8
BBRBRBBR

예제 출력1

4

---

# Code

import sys
input = sys.stdin.readline

n = int(input())
s = input()

colors = { 'B' : 0, 'R' : 0 } #딕셔너리
colors[s[0]] +=1 #처음 색깔 칠하기
for i in range(1, n): #다른 색이 나오면 해당 색깔 칠하는 횟수 +1
    if s[i] != s[i-1]:
        colors[s[i]]+=1

result = min(colors['B'], colors['R'])+1 #칠할 횟수가 더 많은 것을 먼저 전체 칠하고(1) 칠할 횟수가 더 적은 것의 횟수 값(min)을 더한다.
print(result)

# Comment

처음에 내가 너무 어렵게 생각했다.
1. 연속한거 칠해나가기 리스트 하나씩 세면서 더하기
2. 전부 하나로 칠하고 (b) 리스트 수 -1 만큼 더하기

이렇게 두가지를 계산해서 min 값을 출력하는 식으로 하려고 했는데.. 음 이렇게 할 필요가 없었다.

우선, 딕셔너리를 사용하는 코드를 참고했는데 확실히 훨씬 간편하고 깔끔하다. 앞으로 딕셔너리를 애용해야겠다.
colors : B를 칠할 횟수와 R을 칠할 횟수를 저장하는 딕셔너리

BBRBRBBR 을 입력받고 나서 처음 값인 'B' 를 칠해야 하므로 colors의 'B' 의 횟수를 하나 증가시킨다. ( 'B' : 1 ) 
그리고 for문을 통해 i가 1일때부터 n-1일 때 까지 s[i] 값을 확인해서 만약 이전 값과 다르다면! 해당 색깔의 횟수를 하나씩 증가시켜준다. 
처음에 'B' 인 것을 확인했는데 다음에 또 'B'가 나온다면 굳이 또 칠할 필요없으므로 'B' : 1로 유지될 것이다. 
그러나 세번째에 'R'이 나오므로 이 때는 'R' : 1 이 될 것이다.

마지막으로 colors['B'] 의 값과 colors['R'] 의 값 중 최솟값을 구해서 +1 해준다.
둘 중 최솟값이라는 뜻은, 해당 색깔의 갯수가 더 적다는 뜻이므로 총 색깔을 칠하는 횟수가 최소가 되기 위해서는 색깔의 갯수가 더 많은 것으로 전체를 칠해주고 색깔의 갯수가 더 적은 것을 따로 칠해주면 된다.
즉, +1을 해주는 이유는 전체를 칠해준다는 의미이다.