사용자 도구

사이트 도구


ps:problems:boj:2840

행운의 바퀴

ps
링크acmicpc.net/…
출처BOJ
문제 번호2840
문제명행운의 바퀴
레벨실버 4
분류

구현

시간복잡도O(n)
인풋사이즈n<100
사용한 언어Python
제출기록30840KB / 72ms
최고기록56ms
해결날짜2022/04/26
태그

[라이] 리스트/배열/연결 리스트

풀이

  • 그냥 반대로 시뮬레이션하면 되는 문제이긴 한데 구현이 좀 까다롭다 (그리고 문제를 이해하는것도 좀 까다롭다)
  • n개의 칸을 ?로 초기화한 다음, 바퀴가 마지막에 가리킨 문자를 첫번째 칸에 적고 거꾸로 시뮬레이션하면서 문자들을 칸에 채워나가면 된다. 그러다가 이미 채워진 칸을 다른 문자로 채워야 하는 경우가 생기거나, 다 채우고 났을때 ?가 아닌 글자가 중복되어서 등장하게 된다면 “!”를 출력하고 나머지 경우에는 칸을에 채워진 알파벳들을 출력하면 된다,
  • 시간복잡도는 O(n)

코드

"""Solution code for "BOJ 2840. 행운의 바퀴".

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


def main():
    N, K = [int(x) for x in input().split()]
    turns = [input().split() for _ in range(K)]

    pos = 0
    wheel = ['?'] * N
    for S, ch in reversed(turns):
        if wheel[pos] not in (ch, '?'):
            answer = '!'
            break
        wheel[pos] = ch
        pos = (pos + int(S)) % N
    else:
        alphabets = [x for x in wheel if x != '?']        
        answer = (''.join(wheel)
                  if len(set(alphabets)) == len(alphabets) else '!')
    print(answer)


if __name__ == '__main__':
    main()

토론

댓글을 입력하세요:
V E M D D
 
ps/problems/boj/2840.txt · 마지막으로 수정됨: 2022/05/03 07:07 저자 teferi