백준 #17615 - [S1] 공 모으기 : 그리디

(python3)

17615번: 볼 모으기

 

아이디어

1. A를 왼쪽으로 모은다

2. B를 왼쪽으로 모은다

3. A를 오른쪽으로 모은다

4. B를 오른쪽으로 모은다

단순화하면 이렇게 4가지 경우가 가능합니다.

한가지만 풀린다면 똑같은 방법론을 적용해서 나머지를 해결해줄 수 있으니 1번 예시만 생각해보겠습니다.

 

A를 왼쪽으로 모으는 경우 왼쪽부터 탐색하면서 A를 옮기면 항상 (연속된A)(연속된B)(새로만난A) 의 배치가 유지됩니다. 여기서 그리디가 적용됩니다.

왼쪽에서부터 쭉 탐색하면서 연속된 B를 뛰어넘으면서 왼쪽에다 갖다 붙여야되는 A 개수를 찾으면 됩니다.

이걸 왼쪽에서 탐색하면서 1,2를 찾고, 오른쪽에서부터 탐색하면서 3,4를 찾아주었습니다.

 

코드

import sys
def solution(input) :
    N = int(input().strip())
    L = input().strip()

    # 왼쪽부터 왼쪽으로 다 밀어넣으면 타겟보다 왼쪽은 항상 정리되어있다.
    blue_left = 0
    blue_cnt_left = 0
    red_left = 0
    red_cnt_left = 0
    for i in range(N) :
        if L[i] == 'B' :
            blue_left+=1
            if i >= blue_left :
                blue_cnt_left+=1

        else : # == 'A'
            red_left+=1
            if i >= red_left :
                red_cnt_left+=1

    # print(blue_cnt_left, red_cnt_left)

    blue_right = N-1
    blue_cnt_right = 0
    red_right = N-1
    red_cnt_right = 0
    for i in reversed(range(N)) :
        if L[i] == 'B' :
            blue_right-=1
            if i <= blue_right :
                blue_cnt_right+=1

        else : # == 'A'
            red_right-=1
            if i <= red_right :
                red_cnt_right+=1

    # print(blue_cnt_right, red_cnt_right)

    print(min(blue_cnt_left,blue_cnt_right,red_cnt_left,red_cnt_right))

        
input = sys.stdin.readline
solution(input)

 

실력자 코드 분석

제 코드를 쓰는 것도 중요하긴하지만 실력자분들의 코드를 보고 배우는게 훨씬 크다는걸 다시 느낍니다ㅋㅋ큐ㅠㅠ 알고리즘은 특히 그런 것 같아요. 제가 애써 떠올리는 것보다 다른 사람들의 것을 보고 익히는게 훨씬 빨리 성장하는 방법이라고 생각합니다.

 

접근 아이디어는 위에 작성한것과 같습니다! 저기에서 한발 더 나아가면, 처음에 연속되게 등장한거를 제외한 나머지는 다 옮겨야한다는 것! 그니까 (총 A 개수 - 애초에 연속되게 등장한 개수) 를 찾으면 되겠죠.

TIL : lstrip, rstrip 에 원소를 넣어서 짤라버릴 수 있다.

소스코드 출처 : https://www.acmicpc.net/source/62504998

N = int(input())
balls = input()

rLeft = N - len(balls.lstrip('R'))
rRight = N - len(balls.rstrip('R'))
bLeft = N - len(balls.lstrip('B'))
bRight = N - len(balls.rstrip('B'))

numR = balls.count('R')
numB = balls.count('B')

print(min(numR - rLeft, numR - rRight, numB - bLeft, numB - bRight))

 

 

 

my solved.ac :

solved.ac