[그리디] 03 문자열 뒤집기

03 문자열 뒤집기

그리디란?

• 현재 상황에서 가장 좋아 보이는 것만을 선택하는 알고리즘이다.
• 정확한 답을 도출하지 못할 수도 있지만 코딩테스트에서는 대부분 ‘최적의 해’를 찾는 문제가 출제되므로 그리디 알고리즘의 정당성을 고민하면서 문제 해결 방안을 떠올려야한다.
• 다양한 그리디 알고리즘
  • 다익스트라 최단 경로 알고리즘
    • 암기가 필요한 알고리즘이다. 팀 노트 필요!
    • 특정 노드까지의 최단 거리 계산한 다음 메모리에 저장하고 나중에 필요할 때 다시 꺼내 본다는 점에서 다이나믹 프로그래밍으로 분류하기도 한다.
  • 크루스칼 알고리즘
    • 우선순위 큐 (최소 힙, 최대 힙)
    • 여러 개의 값들 중 최댓값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조이다.

---

문제

다솜이는 0과 1로만 이루어진 문자열 S를 가지고 있습니다. 다솜이는 이 문자열 S에 있는 모든 숫자를 전부 같게 만들려고 합니다. 다솜이가 할 수 있는 행동은 S에서 연속된 하나 이상의 숫자를 잡고 모두 뒤집는 것입니다. 뒤집는 것은 1을 0으로, 0을 1로 바꾸는 것을 의미합니다.

예를 들어 S = 0001100일 때는 다음과 같습니다.

4번째 문자부터 5번째 문자까지 뒤집으면 한 번에 0000000이 되어서 1번 만에 모두 같은 숫자로 만들 수 있습니다.

문자열 S가 주어졌을 때, 다솜이가 해야 하는 행동의 최소 횟수를 출력하세요.

입력 조건

• 첫째 줄에 0과 1로만 이루어진 문자열 S가 주어진다. S의 길이는 100만 보다 작다.

출력 조건

• 첫째 줄에 다솜이가 해야 하는 행동의 최소 횟수를 출력한다.

입력 예시

11001100110011000001

출력 예시

4

---

사고 과정

• 1111이든 11이든 연속적인 수는 한번에 뒤집어지기 때문에 연속적인 수를 하나의 수로 취급한다.

  (원소 각각이 의미를 갖지 못하는 경우, 원소 전체를 하나로 취급한다.)

  11101101 ⇒ 10101

• 경우의 수를 살펴보자

  • 10101 2번, 1010 2번, 101010 3번
  • 가장 적은 숫자의 개수만큼 뒤집는다

---

풀이

나의 코드 1

# 문자열 s입력받기
s = list(map(int,list(input()))) # map은 list()를 씌워야한다

# 연속된 수를 하나의 수로 취급한다.
group = []
# 리스트에 문자열 앞 숫자를 집어넣고 before(s[i-1])와 now(s[i])가 다르면 now 숫자를 집어 넣는다. 같으면 before과 now를 한 칸 이동시킨다.
group.append(s[0])
for i in range(1, len(s)):
  if s[i-1] != s[i]:
    group.append(s[i])
if len(group) == 1:
  print(0)
else:
  # 가장 빈도가 적은 원소
  print(group.count(min(set(group), key = group.count)))

# 리스트를 입력받아서 빈도수가 가장 높은 요소 출력하는 프로그램
# def most_frequent(data):
#     return max(data, key=data.count)

나의 코드 2

s = input()
count = 0
for i in range(len(s)-1):
    if(s[i] != s[i+1]):
        count += 1
count += 1
print(count // 2)

---

💡사고 과정 흐름을 공식화하자

• 연속된 수를 하나의 수로 취급

    # 리스트에 문자열 앞 숫자를 집어넣고 
    # before(s[i-1])와 now(s[i])가 다르면 now 숫자를 집어 넣는다. 
    # 같으면 before과 now를 한 칸 이동시킨다.
    group = []
    group.append(s[0])
    for i in range(1, len(s)):
      if s[i-1] != s[i]:
        group.append(s[i])
  

• group에서 가장 빈도가 적은 원소 반환