사용자 도구

사이트 도구


ps:problems:boj:16440

제이크와 케이크

ps
링크acmicpc.net/…
출처BOJ
문제 번호16440
문제명제이크와 케이크
레벨플래티넘 5
분류

슬라이딩 윈도우

시간복잡도O(n)
인풋사이즈n<=200,000
사용한 언어Python 3.11
제출기록31120KB / 36ms
최고기록36ms
해결날짜2024/12/01

풀이

코드

"""Solution code for "BOJ 16440. 제이크와 케이크".

- Problem link: https://www.acmicpc.net/problem/16440
- Solution link: http://www.teferi.net/ps/problems/boj/16440

Tags: [sliding window]
"""


def main():
    N = int(input())
    cake = input()

    target_s_count = N // 4
    s_count = cake[: N // 2].count('s')
    if s_count == target_s_count:
        print('1')
        print(N // 2)
        return

    for rem, add, beg in zip(cake, cake[N // 2 :], range(1, N)):
        if rem == 's':
            s_count -= 1
        if add == 's':
            s_count += 1
        if s_count == target_s_count:
            print('2')
            print(beg, beg + N // 2)
            break


if __name__ == '__main__':
    main()

토론

댓글을 입력하세요:
J N Q W P
 
ps/problems/boj/16440.txt · 마지막으로 수정됨: 2024/12/01 04:19 저자 teferi