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

문제

문자열 s에 모든 숫자를 같게 만들려고한다.

s에서 연속된 하나이상의 숫자를 잡고 모두 뒤집는다.

뒤집는것은 0에서 1로, 1에서 0으로 뒤집는 행위이다.

 

예를들어 s=0001100

1. 전체를 뒤집으면 1110011

2. 4번쨰부터 5번째 문자까지 뒤집으면 1111111 이 되어서 두번만에 모두 같은 숫자로 만들 수 있음

 

하지만 처음부터 4번쨰부터 5번째 숫자를 뒤집어서 한번에 0000000이 되어서 1번 만에 모두 같은 숫자로 만들 수 있음

 

입력 조건 : 첫째 줄에서 0과 1로만 이루어진 문자열 s가 주어짐(s의 길이는 100만 보다 작음)

출력 조건 : 뒤집는 행동의 최소 횟수를 출력함

 

입력예시 : 0001100

출력 예시 : 1

 

문제 해결 방법

같은 문자가 연속되는 것을 제거하여 저장한다.

예를들어 0001100같은 경우는 010 이렇게 저장해서 숫자가 달라지는 부분을 표시

그 후 문자열에서의 0의 횟수와 1의 횟수를 비교해서 최솟값을 출력한다. 0이 등장하는 횟수는 2번이고, 1이 등장하는 횟수는 1번이니 1이 출력된다.

 

코드

#입력
s=input()
#s의 첫번째 문자 저장
temp=s[0]
#축소 저장할 배열 초기화
word_list=[]
for char in range(1,len(s)) :
    #기존 문자와 현재 문자가 다를때 wordlist에 저장하고 현재 문자로 값 변환
    if s[char]!=temp :
        word_list.append(temp)
        temp=s[char]

#0의 횟수와 1의 횟수의 최솟값
answer=min(word_list.count("0"), word_list.count("1"))
print(answer)

 

<책에서의 풀이>

전부 0으로 바꾸는 경우와 1로 바꾸는 경우의 횟수를 카운트해서 최솟값 비교하는 방식이다.

data=input()
count0=0 #전부 0으로 바꾸는 횟수
count1=0 #전부 1로 바꾸는 함수

#첫번째 문자에 대한 처리
if data[0]=="1" :
    count0+=1
else :
    count1+=1

for i in range(len(data)-1) :
    if data[i+1]=="1" :
        count0+=1
    elif data[i+1] == "0" :
        count1+=1

answer=min(count0, count1)

 

※이 게시글은 <이것이 취업을 위한 코딩테스트다(나동빈 저)> 를 참고하여 작성되었습니다.