[python/파이썬] 백준 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

위의 예시와 같다.

 

[소스 코드 1 - 틀렸습니다]

 

기본적으로는 한 색깔로 다 칠한 다음에 나머지를 칠하는 것이 가장 효율적인 방법이다.

처음에 생각하기를 개수가 많은 색깔로 다 칠하는 것이 항상 더 적은 횟수로 칠할 수 있을 거라고 생각했다.

그래서 각 색깔의 개수를 세서 파란색이 많은 경우는 파란색으로, 빨간색이 많은 경우는 빨간색으로 칠하는 것으로 가정했다.

빨간색이 많은 경우 빨간색으로 칠해졌기에 파란색만 골라서 칠하면 된다

그래서 파란색만 남기기 위해서 

re.split('R+', data)를 해주었다. -> 'R+'는 정규표현식, R이 한 개 이상 포함된 문자열로 split() 하기 위해서 사용

반대의 경우도 마찬가지다.

 

주어진 데이터가 

BBRBRBBR

일 경우에는 

 

파란색이 더 많기에 파란색을 기준으로 하여 나눠준다.

그 결과는(''가 제거된 상태)

['R', 'R', 'R']

이 된다.

그러면 처음에 파란색으로 칠하는 횟수 1과 결과 리스트의 길이인 3을 더해서 최소 횟수인 4를 구할 수 있다.

 

하지만 항상 개수가 더 많은 색으로 칠하는 것이 최소 횟수가 되는게 아니므로 소스 코드 2로 수정하였다.

import re #re.split() 사용하기 위해

n = int(input()) #칠해야 할 문제의 수

data = input() 
colors = list(data) 

count_b = colors.count('B') #파란색의 개수
count_r = colors.count('R') #빨간색의 개수

if count_b >= count_r: #파란색이 더 많을 경우 파란색으로 전체를 칠한다
    tmp = re.split('B+',data) 
elif count_b < count_r: #빨간색이 더 많을 경우 빨간색으로 전체를 칠한다
    tmp = re.split('R+',data)
for item in tmp: #re.split()을 하고 나면 '' 원소가 생겨서 제거해 줌
    if item == '': 
        tmp.remove('')
if count_b == 0 or count_r == 0: #하나의 색으로만 이루어진 경우는 1번만 색칠해준다
    print(1)
else: #그 이외의 경우 전체를 칠한 1번을 더해 출력
    print(len(tmp)+1)

 

 

[소스 코드2 - 맞았습니다!]

 

소스 코드 1과 기본적인 풀이 방법은 동일하나

빨간색으로 먼저 칠하는 경우와 파란색으로 먼저 칠하는 경우 모두 구하여서 그중에 최솟값을 고르도록 했다.

 

한 가지 색으로 구성된게 아니라면 두 가지를 모두 고려해야 하는데

else 구문 아래를 보면

 

파란색을 기준으로 나눈 split_B와 빨간색을 기준으로 나눈 split_R을 구한다.

split_B -> 빨간색만 남김 split_R -> 파란색만 남김

 

예를 들어 

RBBRRBBRBR 이라면

split_B -> ['R', 'RR', 'R', 'R]

split_R -> ['BB', 'BB', B']

 

이 되고 split_R의 길이가 더 짧은 것을 알 수 있다.

따라서 적은 횟수로 칠하기 위해서는 전체를 빨간색으로 칠하고, 

파란색 2개를 2번, 파란색 1개를 1번 칠하여 

총 4번으로 칠할 수 있다. 

import re #re.split() 사용하기 위해

n = int(input())
data = input()
colors = list(data)
count_b = colors.count('B') #파란색의 개수
count_r = colors.count('R') #빨간색의 개수

if count_b == 0 or count_r == 0: #파란색이나 빨간색으로만 이루어진 경우 1출력
    print(1)
else: #파란색으로 split한 경우와 빨간색으로 split한 경우로 나눔
    split_B = re.split('B+',data)
    split_R = re.split('R+',data)
    
    for item in split_B: #split후에 생기는 '' 제거
        if item == '':
            split_B.remove('')
    for item in split_R:
        if item == '':
            split_R.remove('')
        
    print(min(len(split_B), len(split_R))+1) #두 경우중에 더 작은 수에 1을 더해서 출력