[백준] 뒤집기 : 1439번 - Python

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

1439번: 뒤집기

 

 

 

문제를 풀면서 몰랐던 개념

 

[Python] 문자열, 리스트 치환

-> replace 사용하기

: 대상 문자열에서 지정한 문자가 있을 경우 원하는 문자로 바꿔주는 기능을 함.

### 문자열 ###

arr = "one2ye, one2ye, one2ye, loves, loves, 20s, 20s, 20s, 20s"
print(arr.replace("20s", "seonho"))


# 출력결과
>>> one2ye, one2ye, one2ye, loves, loves, seonho, seonho, seonho, seonho

### 리스트 ###

arr = [ 'one2ye', 'one2ye', 'one2ye', 'loves', 'loves', '20s', '20s', '20s', '20s' ]

result = []
for i in arr:
    temp = i.replace("20s", "seonho")
    result.append(temp)

print(result)


# 출력결과
>>> ['one2ye', 'one2ye', 'one2ye', 'loves', 'loves', 'seonho', 'seonho', 'seonho', 'seonho']

 

 

 

문제의 접근 방법

 

0 or 1 은 최소 행동 0번, 바뀌는 구간 0개

01 or 10 은 최소 행동 1번, 바뀌는 구간 1개

010 or 101 은 최소 행동 1번, 바뀌는 구간 2개

0101 or 1010 은 최소 행동 2번, 바뀌는 구간 3개

01010 or 10101 은 최소 행동 2번, 바뀌는 구간 4개

010101 or 101010 은 최소 행동 3번, 바뀌는 구간 5개

0101010 or 1010101 은 최소 행동 3번, 바뀌는 구간 6개

 

* 규칙: (구간 개수 + 1) // 2 = 최소 행동 횟수

 

 

 

내가 막혔던 부분

 

0과 1의 개수를 구해서 더 적은 개수의 수만큼 바꿔주면 된다고 생각함 -> 그건 일일이 바꿔주는 것이기 때문에 최소 횟수를 출력할 수 없음.

# 완전 오답 코드

S = list(input())

count = {}
for i in S:
    try: count[i] += 1
    except: count[i] = 1

c = 0
result = []
if count.get('0') >= count.get('1'):
    for i in S:
        temp = i.replace("1","0")
        result.append(temp)
    c += 1
else:
    for i in S:
        temp = i.replace("0","1")
        result.append(temp)
    c += 1

print(c)

 

 

 

문제 풀이 방법

 

규칙성만 찾아내면 너무너무너무 간단하게 풀 수 있는 문제지만 그게 어렵다.

위의 접근 방법에서 찾은 규칙을 적용해서 구현

-> 입력받은 문자열 S를 리스트로 바꾸어 넣어준 후, 각 원소들이 같은지 다른지 비교해준다.

-> 같다면 다음 원소 비교로 넘어가고 만약 다르다면 (1->0 or 0->1) count를 누적해서 더해준다.

-> 더해준 count는 바뀌는 구간의 개수를 의미하므로, +1를 해준 후 2로 나눈 몫을 출력해주면 된다!!! 그게 최소 행동의 횟수.

 

 

 

소스코드

S = list(input())

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

print((count+1)//2)