ps:problems:boj:1439
뒤집기
ps | |
---|---|
링크 | acmicpc.net/… |
출처 | BOJ |
문제 번호 | 1439 |
문제명 | 뒤집기 |
레벨 | 실버 5 |
분류 |
그리디 |
시간복잡도 | O(n) |
인풋사이즈 | n<=1,000,000 |
사용한 언어 | Python |
제출기록 | 30864KB / 68ms |
최고기록 | 52ms |
해결날짜 | 2022/01/12 |
풀이
- 간단하게 생각하자. 같은 문자가 연속된 것을 그룹으로 묶자. 0으로 된 그룹의 갯수와 1로 된 그룹의 갯수를 비교해서 적은 쪽을 모두 뒤집으면 최적 횟수가 나온다.
- 0으로 된 그룹의 갯수와 1로 된 그룹의 갯수는 같거나 1차이가 나므로, 그냥 총 그룹의 갯수를 2로 나누고 내림해도 똑같다.
- 그룹의 갯수는 itertool.groupby를 써서 찾아도 되고, 부분문자열 '01'과 '10'의 등장 횟수에 1을 더한 값으로 찾아도 된다.
코드
"""Solution code for "BOJ 1439. 뒤집기".
- Problem link: https://www.acmicpc.net/problem/1439
- Solution link: http://www.teferi.net/ps/problems/boj/1439
"""
import itertools
def main():
S = input()
group_count = sum(1 for _ in itertools.groupby(S))
print(group_count // 2)
if __name__ == '__main__':
main()
ps/problems/boj/1439.txt · 마지막으로 수정됨: 2022/01/12 16:18 저자 teferi
토론