백준 17615 볼 모으기 Python

🐸 문제 정보

17615번: 볼 모으기

 

🤖 알고리즘

그리디

 

⏱️ 풀이 시간

22.24m

 

📝 풀이

공을 양 끝으로 옮긴다는 아이디어는 쉽게 얻을 수 있지만, 역시 이를 구현하는 과정이 어려운 문제였다.

한 번 틀리고 검색의 힘을 빌렸음에도 대부분의 블로그에서 아이디어에 대한 이야기만 하고 있을 뿐 공을 옮기는 수에 대한 이야기는 거의 하지 않고 있었다..

헷갈린다면 아래 방법을 잘 읽어보면 도움이 될 것 같다.

1. 우선 주어진 입력에서 red와 blue의 개수를 찾는다
   • 이 중 개수가 적은 색이 정답 후보가 된다.
   • 최악의 경우 모든 공의 색을 옮겨야하는데, 이때 더 적은 개수를 옮기는 것이 효율적이기 때문이다.
2. 먼저 공의 앞부분부터 탐색을 진행한다.
   • 맨 앞부터 연속된 공의 개수를 찾는다.
   • 옮겨야하는 공의 개수 = (맨 앞 공의 색을 가진 공의 개수) - (맨 앞 부터 연속된 공의 개수)
   • 맨 앞부터 연속된 공을 제외한 나머지를 옮겨서 넣어야하기 때문이다.
3. 공의 뒷부분도 동일하게 탐색을 진행한다
   • 옮겨야하는 공의 개수 = (맨 뒤 공의 색을 가진 공의 개수) - (맨 뒤 부터 연속된 공의 개수)
4. 이제 옮겨야하는 공의 개수와 기존 정답 후보 중 최소값을 찾아낸다.

 

🧑‍💻 나의 답

# pypy3

import sys
input = sys.stdin.readline

n = int(input().rstrip())
balls = input().rstrip()

red = balls.count('R')
blue = n - red

res = min(red, blue)

cont = 1
for i in range(1, n):
    if balls[i] == balls[i - 1]:
        cont += 1
    else:
        break

if balls[0] == 'R':
    res = min(res, red - cont)
else:
    res = min(res, blue - cont)

cont = 1
for i in range(n - 2, -1, -1):
    if balls[i] == balls[i + 1]:
        cont += 1
    else:
        break

if balls[-1] == 'R':
    res = min(res, red - cont)
else:
    res = min(res, blue - cont)

print(res)