[그리디] 03.문자열 뒤집기 (유형별 기출문제, 이것이 코딩테스트다 with 파이썬)

그리디 개념

• 현재 상황에서 가장 좋아 보이는 것만을 선택하는 알고리즘
• '최적의 해'를 찾는 문제로 출제 ➝ 그리디 알고리즘의 정당성을 고민해보기
• 다양한 알고리즘에 두루 사용    # ex) 다익스트라 최단 경로 알고리즘, 크루스칼 알고리즘

빈출유형

거스름돈 문제

• 거슬러 줘야 할 동전의 최소 개수 찾는 문제
• 가장 큰 단위의 화폐 ~ 작은 단위의 화폐를 차례대로 확인하고 거슬러 주는 작업

1이 될 때까지

• N이 1이 될 때까지 '1을 빼기' 혹은 'K로 나누기' 연산을 최소 몇 번 수행해야 하는지 계산
• 최대한 많이 나누기가 문제 해결 아이디어

 

문제

 

해설

전부 0으로 바꾸는 경우와 전부 1로 바꾸는 경우 중에서 더 적은 횟수를 가지는 겨우 계산

1. 모두 0으로 만드는 경우
2. 모두 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] != data[i + 1]:
        # 다음 수에서 1로 바뀌는 경우
        if data[i] != data[i+1]:
            count0 += 1
        # 다음 수에서 0으로 바뀌는 경우
        else:
            count1 += 1
            
print(min(count0, count1))

 

해석

 

변수 : 숫자 문자열 data, 0횟수 count0, 1횟수 count1

 

1. 숫자 문자열 data 입력받기

2. 0횟수 count0, 1횟수 count1 초기화

3. 첫 번째 원소 처리 조건문

ㄴ 0 : 0 숫자 개수 세기

ㄴ 1 : 1 숫자 개수 세기

------------------------- 반복문 : 숫자 문자열 data  -------------------------

4. 두번째 원소 처리 조건문

ㄴ 1에서 0으로 바뀜 : 0 숫자 개수 세기

ㄴ 0에서 1으로 바뀜 : 1 숫자 개수 세기

--------------------------------------------------------------------------------------

5. count0과 count1 중 작은 수 출력