• 열심히 풀고 풀이도 써놨는데, 다 쓰고서 공식 풀이를 보니까 단순한 관찰을 추가해서 훨씬 간단하게 푸는 방법이 있었다.
• 원래 적어놨던 풀이와 코드는 망글이 되었지만, 지우지는 않고 그냥 접어놓기만 하겠다
• 핵심 관찰은 게임이 종료된 최종 보드에서는 이름이 abab.. 처럼 번갈아가면서 적혀지게 된다는 것. 그러므로 현재 적혀져있는 이름들의 개수와, 양 끝에 같은 이름을 적을수 있는지 여부만 확인하면 승패를 알수 있다는 것이다. 자세히는 공식 풀이 참고. 시간복잡도는 O(n)

처음 풀었던 (좀더 복잡하게 푸는) 풀이

"""Solution code for "BOJ 35127. Game of Names".

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

Tags: [game theory]
"""

import sys
from teflib import psutils


@psutils.run_n_times
def main():
    n = int(sys.stdin.readline())
    s = sys.stdin.readline().rstrip()

    if s.count('.') == n:
        print('bob' if n > 1 else 'alice')
        return

    left, right = None, None
    if s[0] != '.':
        left = s[0]
    elif s[1] != '.':
        left = 'a' if s[1] == 'b' else 'b'
    if s[-1] != '.':
        right = s[-1]
    elif s[-2] != '.':
        right = 'a' if s[-2] == 'b' else 'b'

    if left is None and right is None:
        left, right = 'a', 'b'
    elif left is None:
        left = 'a'
    elif right is None:
        right = 'a'

    adv = s.count('b') - s.count('a')
    if left == right:
        adv += 1 if left == 'a' else -1

    print('alice' if adv > 0 else 'bob')


if __name__ == '__main__':
    main()