문제 03 : 문자열 뒤집기(난이도 : 1/3)

문제 출처 : 19597번: 문자열 뒤집기 (acmicpc.net)

19597번: 문자열 뒤집기

---

1. 문제 분석

• 처음 이 문제를 접하고 생각했던 방법은 문자열을 처음부터 검사하면서 앞의 문자와 현재 문자가 다르면 count 변수를 증가시키는 방법으로 접근하려고 했다.
• 나는 count 변수를 하나만 가지고 0으로 바꾸는 경우의 count와 1로 바꾸는 경우의 count를 비교해야 했는데 변수 하나만 가지고는 불가능하고 또한 반복문을 두 번 돌아야 한다는 생각이 들었다.
• 결국 더 좋은 방법을 생각하지 못 했고 문제풀이 해설을 보고 다음과 같이 바꾸게 되었다.

 

• count 변수를 2개로 확장하여 0->1로 바꾸는 경우(flip_to_oen)와 1->0으로 바꾸는 경우(flip_to_zero)를 각각 저장한다.
• 두 변수를 사전에 0으로 초기화하고 첫 문자를 확인해 1인 경우 flip_to_zero를 0인 경우 flip_to_one을 1 증가시킨다.
• 문자열의 0번 인덱스 부터 현재 문자와 다음 문자를 비교하여 서로 다른 경우 다음과 같이 각각의 변수를 증가시킨다.
• 현재 문자가 0이고 다음 문자가 1인 경우 : flip_to_one을 1 증가시킨다.
• 현재 문자가 1이고 다음 문자가 0인 경우 : flip_to_zero를 1 증가시킨다.
• 그리고 두 변수를 비교하여 값이 더 작은 것을 출력한다.

 

• 풀이 해설 방식을 통해 반복문을 한 번만 돌아 행동의 최소 횟수를 출력할 수 있다.

---

2. 코드 구현 - 문제 풀이 해설 방식

flip_to_zero = 0 # 0으로 뒤집는 횟수
flip_to_one = 0 # 1로 뒤집는 횟수

# 문자열의 첫 번재 데이터에 대해서
if s[0] == '1':
    flip_to_zero = 1
else:
    flip_to_one = 1

# 두 번째 문자열 부터 다음 문자열과 비교하여 뒤집는 횟수 계산
for i in range(len(s) - 1):
    if s[i] != s[i + 1]:
        # 다음 문자열이 1인 경우 0으로 뒤집는 횟수 증가
        if s[i + 1] == '1':
            flip_to_zero += 1
        else:
            flip_to_one += 1

# 뒤집는 횟수가 적은 값을 출력
print(min(flip_to_one, flip_to_zero))

• 주의해야 될 점으로 반복문의 범위를 (len(s)-1)로 설정해야 한다.
• 그래야 최종적으로 s[len(s)-2]와 s[len(s)-1]을 비교하는데, 이를 통해 비로소 인덱스 범위 초과 에러 없이 마지막 전 문자와 마지막 문자를 비교할 수 있다.(당연한 이야기지만 이런 부분까지 꼼꼼하게 살펴봐야 한다.)

---

3. 후기

  지금 문제를 보면 너무 쉽지만 처음 문제를 접했을 때는 감히 손도 못 댔었다. 쑥스럽지만 고민하다가 결국 정답 해설지를 보고 문제를 이해하게 되었으며 풀이를 보고는 족므 허탈했던 기억이 있다. 더 웃긴건 문제를 총 3번 풀었는데 두 번째 풀때는 맞췄고 세 번째 풀때는 또 오답이었다. 사실 두 번째 문제를 풀 때는 첫 번째 풀때와 시간 간격이 좁았고 세 번째 풀때는 시간이 좀 지난 뒤에 시도했는데 flip_to_zero, flip_to_one의 사전 설정과 반복문의 범위에서 오류를 범했었다.

---

github : Algorithms/q3_0.py at main · LeeSeok-Jun/Algorithms (github.com)

LeeSeok-Jun/Algorithms