[Python] 백준 20365번_블로그2

https://www.acmicpc.net/problem/20365

20365번: 블로그2

 

• neighbor 블로그를 운영하는 일우는 매일 아침 풀고 싶은 문제를 미리 정해놓고 글을 올림
• 그리고 매일 밤 각각의 문제에 대하여, 해결한 경우 파란색, 해결하지 못한 경우 빨간색으로 칠함
• 일우는 각 문제를 칠할 때 아래와 같은 과정을 한 번의 작업으로 수행
  • 1) 연속된 임의의 문제들을 선택
  • 2) 선택된 문제들을 전부 원하는 같은 색으로 칠함
• 일우를 도와 각 문제를 주어진 색으로 칠할 때 필요한 최소한의 작업 횟수 구하기

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

 

• 입력
  • 첫째 줄에 색을 칠해야 하는 문제의 수 N (1 ≤ N ≤ 500,000)이 주어짐
  • 둘째 줄에 N개의 문자가 공백 없이 순서대로 주어짐
  • 각 문자는 i번째 문제를 어떤 색으로 칠해야 하는지를 의미하며, R은 빨간색, B는 파란색을 나타냄
  • 그 외에 다른 문자는 주어지지 않음
• 출력
  • 첫째 줄에 일우가 주어진 모든 문제를 원하는 색으로 칠할 때까지 필요한 작업 횟수의 최솟값을 출력

 

 

"""
입출력 예시)

8
BBRBRBBR
    -> 4
"""

 

 

## 의사코드 ##

# 최소한의 작업 횟수 -> 개수가 많은 색을 한 번에 먼저 다 칠한 다음, 남은 색의 개수만큼 칠하기

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

# 최소한의 작업 횟수 = 빨간색과 파란색의 개수 중 더 작은 것 + 1
# min(red_n, blue_n) + 1

 

 

 

 

첫 번째 시도

 

## 의사코드 ##

# 최소한의 작업 횟수 -> 개수가 많은 색을 한 번에 먼저 다 칠한 다음, 남은 색의 개수만큼 칠하기

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

# 최소한의 작업 횟수 = 빨간색과 파란색의 개수 중 더 작은 것 + 1
# min(red_n, blue_n) + 1

 

n = int(input())
colors = input()

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

# 최소한의 작업 횟수 = 빨간색과 파란색의 개수 중 더 작은 것 + 1
print(min(red_n, blue_n) + 1)

 

-> 틀림

 

 

 

두 번째 시도

 

## 의사코드 ##

# 최소한의 작업 횟수 -> 개수가 많은 색을 한 번에 먼저 다 칠한 다음, 남은 색의 개수만큼 칠하기

# 시작 색상 지정
# start_clor = 'R' # 시작 색상 

# 파란색의 개수가 더 많은 경우, 시작 색상을 'B'로 변경 
# if colors.count('B') > colors.count('R'):
#     start_clor = 'B'

# cnt = 1 # 작업 횟수 (맨 처음, 가장 많은 개수의 색상으로 칠해놓기 때문에 1부터 시작)

# for c in colors:
#     # 현재 색상이 시작 색상과 다르면 작업 횟수 + 1
#     if c != start_clor:
#         cnt += 1
# print(cnt)

 

n = int(input())
colors = input()

start_clor = 'R' # 시작 색상 
# 파란색의 개수가 더 많은 경우, 시작 색상을 'B'로 변경 
if colors.count('B') > colors.count('R'):
    start_clor = 'B'

cnt = 1 # 작업 횟수 (맨 처음, 가장 많은 개수의 색상으로 칠해놓기 때문에 1부터 시작)

for c in colors:
    # 현재 색상이 시작 색상과 다르면 작업 횟수 + 1
    if c != start_clor:
        cnt += 1
print(cnt)

 

-> 틀림

 

 

 

통과한 코드

 

## 의사코드 ##

# 최소한의 작업 횟수 -> 개수가 많은 색을 한 번에 먼저 다 칠한 다음, 남은 색의 개수만큼 칠하기

# 두 가지 색상의 작업 횟수를 모두 구해서 둘 중 더 작은 것 + 1

# dic = {'R':0, 'B':0} # 두 색상의 작업 횟수를 담을 딕셔너리
# 시작 색상의 작업 횟수 + 1
# dic[colors[0]] += 1 

# for i in range(1, n):
#     # 현재 색상이 이전 색상과 다른 경우, 현재 색상의 작업 횟수 + 1
#     if colors[i] != colors[i-1]:
#         dic[colors[i]] += 1

# 두 가지 색상의 작업 횟수 중 더 작은 값 + 1
# min(dic['R'], dic['B']) + 1

 

n = int(input())
colors = input()

# 두 색상의 작업 횟수를 담을 딕셔너리
dic = {'R':0, 'B':0} 
# 시작 색상의 작업 횟수 + 1
dic[colors[0]] += 1 

for i in range(1, n):
    # 현재 색상이 이전 색상과 다른 경우, 현재 색상의 작업 횟수 + 1
    if colors[i] != colors[i-1]:
        dic[colors[i]] += 1

# 두 가지 색상의 작업 횟수 중 더 작은 값 + 1
print(min(dic['R'], dic['B']) + 1)

 

-> 딕셔너리를 사용해서 두 색상의 작업 횟수를 저장하고, 둘 중 더 작은 값에 1을 더한 것이 최소 작업 횟수

 

 

• 과정 확인

n = 8
colors = 'BBRBRBBR'

"""
딕셔너리에 시작 색상의 작업 횟수 + 1: {'R': 0, 'B': 1} 

이전 색상: B
현재 색상: B
dic: {'R': 0, 'B': 1} 

이전 색상: B
현재 색상: R
현재 색상의 작업 횟수 + 1
dic: {'R': 1, 'B': 1} 

이전 색상: R
현재 색상: B
현재 색상의 작업 횟수 + 1
dic: {'R': 1, 'B': 2} 

이전 색상: B
현재 색상: R
현재 색상의 작업 횟수 + 1
dic: {'R': 2, 'B': 2} 

이전 색상: R
현재 색상: B
현재 색상의 작업 횟수 + 1
dic: {'R': 2, 'B': 3} 

이전 색상: B
현재 색상: B
dic: {'R': 2, 'B': 3} 

이전 색상: B
현재 색상: R
현재 색상의 작업 횟수 + 1
dic: {'R': 3, 'B': 3} 

최종 dic: {'R': 3, 'B': 3} 
"""

 

 

 

 

 

참고)

 

https://devlibrary00108.tistory.com/325

[백준][Python] 20365 블로그2