17615

날짜 : 2022. 12. 10

사용 언어 : python

 

문제

 

 

코드

정답풀이

import sys

n = int(sys.stdin.readline())
ball = str(sys.stdin.readline().rstrip())
cnt = list()

# 우측 연속된 R 제외 후 R의 개수(R을 우측으로 이동)
ex = ball.rstrip("R")
cnt.append(ex.count("R"))

# 좌측 연속된 R 제외 후 R의 개수(R을 좌측으로 이동)
ex = ball.lstrip("R")
cnt.append(ex.count("R"))

# 우측 연속된 B 제외 후 B의 개수(L을 우측으로 이동)
ex = ball.rstrip("B")
cnt.append(ex.count("B"))

# 좌측 연속된 B 제외 후 B의 개수(L을 좌측으로 이동)
ex = ball.lstrip("B")
cnt.append(ex.count("B"))

#print(cnt)
print(min(cnt))

 

15점 풀이

import copy
import sys


def red(a):  # 빨강을 옮김
    t = copy.deepcopy(a)
    cnt = 0
    idx = 0
    flag = False
    for i in range(len(t)-1, -1, -1):
        if not flag and t[i] == "B":
            idx = i  # swap할 인덱스
            flag = True
        if flag and t[i] == "R":
            t[idx], t[i] = t[i], t[idx]  # swap
            cnt += 1
            idx = i
    #print(t)
    return cnt


def blue(a):  # 파랑을 옮김
    t = copy.deepcopy(a)
    cnt = 0
    idx = 0
    flag = False
    for i in range(len(t) - 1, -1, -1):
        if not flag and t[i] == "R":
            idx = i
            flag = True
        if flag and t[i] == "B":
            t[idx], t[i] = t[i], t[idx]  # swap
            cnt += 1
            idx = i
    #print(t)
    return cnt


n = int(sys.stdin.readline())  # 볼의 개수
temp = sys.stdin.readline().rstrip()
a = list()
for i in temp:
    a.append(i)
p = red(a)  # R을 옮김
q = blue(a)  # B를 옮김

print(min(p, q))

 

풀이

- 경우의수는 총 4개가 있다.

1. R을 오른쪽으로 옮기는 경우

2. R을 왼쪽으로 옮기는 경우

3. B를 오른쪽으로 옮기는 경우

4. B를 왼쪽으로 옮기는 경우

 

- 예컨대 1번 경우의 수를 구하는 케이스는 오른쪽에서 시작했을 때 연속된 R을 지운 후 R의 개수를 구하는 것과 동일하다.

ex) R B B B R B R R R 가 있다면, R을 오른쪽으로 옮기는 경우 오른쪽부터 3개가 연속된 R R R 은 가산되지 않는다.

(이동할 필요가 없기 때문이다.)

 그렇다면 남은 배열은 R B B B R B 가 되고, 이중에서 첫 번째와 5번째에 있는 글자인 2개의 R을 옮기면 첫 번째 케이스의 답이 도출된다.

 

- 이렇게 총 4개의 케이스에 대해서 각각 구한 후, 해당 케이스 중에서 가장 작은 값을 min 메소드를 통해 답을 도출할 수 있다.

 

 

 

알게된 점

- 처음에 swap하는 방식으로 했지만 문제 점수가 15점만 나온걸 보고 다른 풀이들을 참고했다.

 

 

 

참고 사이트

- https://fre2-dom.tistory.com/427#recentEntries

[baekjoon] 백준 17615번(파이썬): 볼 모으기