[알고리즘/그리디] 17615번 : 볼 모으기 - python

링크 : https://www.acmicpc.net/problem/17615

17615번: 볼 모으기

---

• 문제
• 소요시간: 30분(15점),  35분(놓친 케이스 참고 : 100점)

---

• 설계하기(접근방법) 

1. 입력받기

문자열을 입력받는다

 

2. 구현하기

이 문제의 핵심은 가장 끝쪽의 연속된 문자열은 문자 한개랑 같다는 것이다.

즉 BRBBBR나

BRBBBRRRR이나

옮겨야 하는 문자열의 수는 같다는 것이다

 

우측을 예시로

R이나 RRRR이든 RRRRRRRR이든

옮겨야 하는 것은 같기 때문에

 

끝쪽에서 연속된 지점이 끝나는 혹은 1개 의 문자열이 다른 문자열로 바뀌는 지점만 파악하면 된다

 

그 지점 부터 R혹은 B의 개수를 더해 나가서

그 중 작은 개수가 옮겨야할 개수이다

 

좌측의 경우도 함께 검사해주어서

 

우측으로 옮기는 경우 중 R,B 중 작은 개수와

좌측으로 옮기는 경우 중 R,B 의 작은 개수 중

가장 작은 횟수가 최소의 수이다

 

 

 

3. 출력하기

 

우측으로 옮기는 case 1의 R,B cnt

좌측으로 옮기는 case 2의 R,B cnt 中

min()을 출력한다

 

 

---

• 코드(출력)

n = int(input())
ball_order = input()

R_cnt_1 = 0
B_cnt_1 = 0


stop = n - 1

## case 1
while stop > 0:
    if ball_order[stop] == ball_order[stop - 1]:
        stop -= 1
        if stop == 1:
            break
    else:
        stop -= 1
        break


for i in range(stop, -1,-1):
    if ball_order[i] == 'R':
        R_cnt_1 += 1
    if ball_order[i] == 'B':
        B_cnt_1 += 1

## case 2
stop = 0
R_cnt_2 = 0
B_cnt_2 = 0

while stop < n - 1:
    if ball_order[stop] == ball_order[stop + 1]:
        stop += 1
    else:
        stop += 1
        break

for i in range(stop, n, 1):
    if ball_order[i] == 'R':
        R_cnt_2 += 1
    if ball_order[i] == 'B':
        B_cnt_2 += 1



print(min(B_cnt_1,B_cnt_2,R_cnt_1,R_cnt_2))

---

• 얻어갈 부분

1. min() 함수는 리스트만이 아닌 정수나 변수를 인자로 받을 수 있다

2. 문제 예시에서 한쪽만 제시한다고 다른 쪽이 불가능 한것은 아니다. 이번 문제에서 공을 오른쪽으로 옮기는 것을 제시하여 왼쪽으로 옮기는 case를 빼먹었다. 열린 생각으로 문제를 읽자