[백준 17615] 볼 모으기 (Python)

www.acmicpc.net/problem/17615

17615번: 볼 모으기

 

문제풀이

N, arr :  입력값

red, blue : N에서 'R', 'B' 의 개수

ans : 최소 이동 횟수

cnt : 좌측, 우측의 연속된 색상의 개수

 

생각보다 까다로운(?) 문제였다. 그리디(Greedy) 알고리즘 문제로, 가장 좌측에서 연속된 색상의 개수, 가장 우측에서 연속된 색상의 개수, 더 적은 색상의 개수를 구하고 이 중 최소값을 출력해야 한다.

 

1. 각 색상의 개수를 센다.

- 더 적은 개수의 색상의 공을 옮기는 것이 더 효율적

 

2. 왼쪽부터 연속된 색상의 개수를 세어서 해당 색상의 전체 개수에서 연속된 개수를 빼준다. (공을 왼쪽으로 옮기는 경우)

- 해당 값이 기존 ans 보다 작으면 이를 갱신

 

3. 오른쪽부터 연속된 색상의 개수를 세어서 해당 색상의 전체 개수에서 연속된 개수를 빼준다. (공을 오른쪽으로 옮기는 경우)

- 해당 값이 기존 ans보다 작으면 이를 갱신

 

코드

import sys

if __name__ == '__main__':
    N = int(input())
    arr = list(map(str, sys.stdin.readline().rstrip()))
    red = arr.count('R')
    blue = N - red

    # 더 적은 개수의 볼이 정답 후보
    ans = min(red, blue)
    cnt = 0
    # 앞에서부터 연속된 구간 확인하기
    for i in range(N):
        if arr[i] != arr[0]: break
        cnt += 1
    # 가장 첫번째 원소의 색상을 옮기는 것이 효율적
    if arr[0] == 'R': ans = min(ans, red - cnt)
    else: ans = min(ans, blue - cnt)

    cnt = 0
    # 뒤에서부터 연속된 구간 확인하기
    for i in range(N - 1, -1, -1):
        if arr[i] != arr[N - 1]: break
        cnt += 1
    # 가장 마지막 원소의 색상을 옮기는 것이 효율적
    if arr[N - 1] == 'R': ans = min(ans, red - cnt)
    else: ans = min(ans, blue - cnt)
    # 빨, 파 중 더 적은 개수, 가장 좌측 원소의 색상 기준으로 좌측으로 몰아넣기, 가장 우측 원소의 색상 기준으로 우측으로 몰아넣기 중 최소값이 정답
    print(ans)

 

결과

 

위 풀이는 'octorbirth' 님의 C++ 풀이를 참고한 코드입니다.

octorbirth.tistory.com/551

문제풀이나 코드에서 이상한 부분 지적은 언제나 환영합니다!