사용자 도구

사이트 도구


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()

토론

댓글을 입력하세요:
W F C F Q
 
ps/problems/boj/1439.txt · 마지막으로 수정됨: 2022/01/12 16:18 저자 teferi