본문 바로가기

알고리즘

[이것이 코딩테스트다] 실전 - 문자열 뒤집기

728x90

 

 

1439번: 뒤집기

다솜이는 0과 1로만 이루어진 문자열 S를 가지고 있다. 다솜이는 이 문자열 S에 있는 모든 숫자를 전부 같게 만들려고 한다. 다솜이가 할 수 있는 행동은 S에서 연속된 하나 이상의 숫자를 잡고 모

www.acmicpc.net

 

나의코드

# 나의코드
n = input()

count=0
default=n[0]
for i in range(1,len(n)):
    if n[i]!=default:
        if n[i-1]!=n[i]:
            count+=1
print(count)

최소한의 횟수로 연속된 문자 그룹을 뒤집어 최종적으로 모든 동일한 숫자로 만드는 것이다. 이는 즉 모든 숫자에 대해서 0->1 혹은 1->0으로 하나를 결정하여 바꿔주면 된다.

나의 코드에서는 첫번째 숫자를 기준으로 하여 n=0001100이라 할때 첫번째 숫자 0을 기준 잡고 1인 그룹을 다 0으로 바꾸주는 방식으로 구현하였다.

 

 

정답코드

# 정답코드
data = input()
count0 = 0
count1 = 0

# 첫번째 원소에 대하여 처리
if data[0] =='1':
    count0 +=1
else:
    count1 +=1

# 두번째 원소부터 모든 원소를 확인
for i in range(len(data)-1):
    if data[i] != data[i+1]:
        # 다음 수에서 1로 바뀌는 경우
        if data[i+1] == '1':
            count0 += 1
        # 다음 수에서 0로 바뀌는 경우
        else:
            count1 += 1

print(min(count0,count1))

책에 나와있는 코드에는 1->0, 0->1로 변경되는 경우 각각을 모두 구하여 가장 작은 값을 출력하는 방식으로 동작한다.

반응형