[백준17615/실1] 볼 모으기 - Python

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

 

 

처음에 가장 끝의 경계 구간에 어떤 색의 공이든 계속 가져다가 놓으면 자동으로 공이 분류된다고 생각했다.

1. 리스트 순회하면서 경계 찾기

2. 경계 찾으면 그부분 부터 공의 수 세어주기

3. 순회 완료 후 센 빨간공의 수와 파란공의 수 비교해서 min값 출력하기

 

# 실패코드

# 공 모으는 방법 : 경계선에 어느 색깔의 공이든 옮겨놓으면 알아서 분류됨

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

left = 0
right = N-1
cur = balls[-1]
line = False
R = 0
B = 0

for i in range(N-1, -1, -1):

    # 경계선이 안나타났다면 나올때까지 경계선 찾기
    if not line:
        if balls[i] != cur:
            line = True

    # 경계선 찾았으면 공 색깔별로 세어주기
    else:
        if balls[i] == 'B':
            B += 1
        elif balls[i] == 'R':
            R += 1

print(min(B, R))

 

반례

5

BBBRB

: 오른쪽에서 왼쪽으로만 순회하다보니 그 반대로 공 옮길 경우를 놓쳤다.

 

 

그래서 왼쪽으로 오른쪽으로 순회하는 방향도 계산해서 다시 풀었다.

1. 리스트 순회하면서 경계 찾기 (오->왼)

2. 경계 찾으면 그부분 부터 공의 수 세어주기

3. 반대 방향으로 순회하면서 경계 찾기 (왼->오)

4. 경계 찾으면 그부분 부터 공의 수 세어주기

5. 각 방향별 공의 수 (네가지) 중 min값 출력

 

# 성공코드1

# 첫번째 코드 (최적화 전) :  36808KB 228ms

# 공 모으는 방법 : 경계선에 어느 색깔의 공이든 옮겨놓으면 알아서 분류됨

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

# 위에서 아래 탐색
cur = balls[-1]
line = False
start = 0
right_R = 0
right_B = 0

for i in range(N-1, -1, -1):

    # 경계선이 안나타났다면 나올때까지 경계선 찾기
    if balls[i] != cur:
        line = True
        start = i
        break

if line:
    for j in range(start, -1, -1):

        # 경계선 찾았으면 공 색깔별로 세어주기
        if balls[j] == 'B':
            right_B += 1
        elif balls[j] == 'R':
            right_R += 1


# 아래서 위 탐색
cur = balls[0]
line = False
start = 0
left_R = 0
left_B = 0

for i in range(N):

    # 경계선이 안나타났다면 나올때까지 경계선 찾기
    if balls[i] != cur:
        line = True
        start = i
        break

if line:
    for j in range(start, N):

        # 경계선 찾았으면 공 색깔별로 세어주기
        if balls[j] == 'B':
            left_B += 1
        elif balls[j] == 'R':
            left_R += 1

# print(left_R, left_B, right_B, right_R)
print(min(left_R, left_B, right_B, right_R))

 

 

 

그랫더니 코드가 너무 길어졌다!

함수 만들어서 reverse() 추가 후 똑같이 적용하는 방식으로 리팩토링했다.

 

 

# 성공코드2

# 공 모으는 방법 : 경계선에 어느 색깔의 공이든 옮겨놓으면 알아서 분류됨
# 함수로 최적화 36808KB 140ms

# 공 탐색 함수
def ball_count(arr):
    cur = arr[0]
    R = 0
    B = 0
    line = False

    for i in range(N):

        # 경계선이 안나타났다면 나올때까지 경계선 찾기
        if not line and arr[i] != cur:
            line = True

        # 경계선 찾았으면 공 색깔별로 세어주기
        if line:
            if arr[i] == 'B':
                B += 1
            elif arr[i] == 'R':
                R += 1

    return R, B

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

left_R, left_B = ball_count(balls)
balls.reverse()
right_R, right_B = ball_count(balls)

# print(left_R, left_B, right_B, right_R)
print(min(left_R, left_B, right_B, right_R))

 

 

 

이게 최선인지 궁금해서 질문게시판 뒤졌는데 완전 간단한 풀이가 있었다.

1. rstrip으로 오른쪽 R 제거

2. 남은 R count

3. rstrip으로 오른쪽 B 제거

4. 남은 B count

5. lstrip으로 왼쪽도 1~4 반복

6. count한 네개의 값 중 min 출력

 

# 다른풀이

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

# 우측으로 레드 모으기
right_R = balls.rstrip('R')

# 우측으로 블루 모으기
right_B = balls.rstrip('B')

# 좌측으로 레드 모으기
left_R = balls.lstrip('R')

# 좌측으로 블루 모으기
left_B = balls.lstrip('B')

print(min(right_R, right_B, left_R, left_B))

 

 

 

짱이네~~~