[백준] 1439 : 뒤집기

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

1439번: 뒤집기

---

코드1, 풀이1

# 풀이1, 나의 풀이) 문자열 split() 활용

S = input()

lst_0 = S.split('1') # 연속된 0을 남긴 리스트
lst_1 = S.split('0') # 연속된 1을 남긴 리스트
cnt_0 = 0 # 0을 뒤집는 횟수
cnt_1 = 0 # 1을 뒤집는 횟수

for i in lst_0:
    if '0' in i:
        cnt_0 += 1

for j in lst_1:
    if '1' in j:
        cnt_1 += 1

print(min(cnt_0, cnt_1))

 

 문제에서 주어진 그대로 아주 직관적으로 풀이를 하였다. 문자열 S를 0 기준으로 split()을 한 후, for문을 돌며 해당 원소에 1이 있는지 확인 후 그 개수를 cnt 해주면 1을 뒤집는 최소 횟수가 나온다. 이는 문자열 S를 1을 기준으로 split()해서 동일하게 수행할 수 있다. 두 횟수의 최솟값을 구해주면 뒤집는 최소 횟수가 반환된다.

 

코드2, 풀이2

# 풀이2) 현재 수와 다음 수 비교해 뒤집기

S = input()
cnt = 0

for i in range(len(S)-1):
    if S[i] != S[i+1]:
        cnt += 1

print((cnt+1)//2) # 하나의 수만 뒤집으면 되니까 반으로 나눔

 

 이 풀이는 현재 수와 다음 수를 비교해서 다르면 cnt를 +1 해주고, 결과적으로 0 또는 1 중 하나의 수만 뒤집으면 되니까 반으로 나누어주는 것이다. 마지막 라인의 print()를 보면 (cnt + 1) // 2 를 해주는데 이는 예제 입력, 예제 출력을 하나씩 구해보면 다음과 같은 규칙이 나옴을 알 수 있다.