블로그를 이전 중이라 완료되기 전까지는 벨로그에 작성할 계획입니다.
이후 모든 글은 https://weekwith.me 에 작성 예정이니 다른 글이 궁금하시다면 해당 링크를 통해 방문해주세요.본 글은 [ 백준 ] 1439번: 뒤집기를 풀고 작성한 글입니다.
문제
설명
다솜이는 0과 1로만 이루어진 문자열 S를 가지고 있다. 다솜이는 이 문자열 S에 있는 모든 숫자를 전부 같게 만들려고 한다. 다솜이가 할 수 있는 행동은 S에서 연속된 하나 이상의 숫자를 잡고 모두 뒤집는 것이다. 뒤집는 것은 1을 0으로, 0을 1로 바꾸는 것을 의미한다.
예를 들어 S=0001100 일 때,
전체를 뒤집으면 1110011이 된다.
4번째 문자부터 5번째 문자까지 뒤집으면 1111111이 되어서 2번 만에 모두 같은 숫자로 만들 수 있다.
하지만, 처음부터 4번째 문자부터 5번째 문자까지 문자를 뒤집으면 한 번에 0000000이 되어서 1번 만에 모두 같은 숫자로 만들 수 있다.
문자열 S가 주어졌을 때, 다솜이가 해야하는 행동의 최소 횟수를 출력하시오.
입력
첫째 줄에 문자열 S가 주어진다. S의 길이는 100만보다 작다.
출력
첫째 줄에 다솜이가 해야하는 행동의 최소 횟수를 출력한다.
풀이
접근법
문자열의 첫 번째 숫자와 다른 숫자가 등장하게 되고 이후 해당 숫자가 다시 바뀌게 되는 순간 마다 횟수가 하나씩 늘어나는 방식으로 접근했다.
그래서 문자열의 첫 번째 요소와 반복문을 돌며 현재 요소를 비교하는 방식으로 문제를 해결하려 했다.
나의 풀이
접근법과 동일하게 첫 번째 숫자를 나타내는 변수 first_num 과 현재의 숫자를 나타내는 변수 current_num 을 정의했다.
이후 for 반복문을 문자열의 길이 만큼 돌면서 만약 첫 번째 숫자는 물론 현재의 숫자와도 해당 숫자 -문자열이기 때문에 엄밀히 따지자면 문자- 가 다르다면 answer 변수의 값을 하나 늘리고 현재 문자열을 해당 문자열로 바꿔준다.
이때 첫 번째 숫자와 동일한 숫자로 다시 돌아오는 경우 다시 현재 문자열을 바꿔줘야 하기 때문에 이에 대한 조건문으로 elif 구문을 추가했다.
S: str = input()
answer: int = 0
first_num, current_num = S[0], S[0]
for num in S:
if (first_num != num) and (current_num != num):
current_num = num
answer +=1
elif current_num != num:
current_num += num
print(answer)Big-O
for 반복문을 문자열 S 의 길이 만큼 한번만 실행하면 되기 때문에 Big-O는 O(N)이다.
기타
그리디 알고리즘으로 분류가 되어 있기는 하지만 어째서 그리디 알고리즘인지 잘 이해가 가지는 않았다.
무엇보다 해당 문제의 경우 제시되는 숫자가 마치 이진수처럼 0 과 1 밖에 없어 간단하게 해결했지만 만약 여러 숫자가 나열되어 있는 상황에서는 어떻게 문제를 해결할 수 있을지 조금 더 생각이 필요할 것 같다.
