사용자 도구

사이트 도구


ps:problems:boj:2941

크로아티아 알파벳

ps
링크acmicpc.net/…
출처BOJ
문제 번호2941
문제명크로아티아 알파벳
레벨실버 5
분류

기초

시간복잡도O(n)
인풋사이즈n<=100
사용한 언어Python
제출기록29200KB / 72ms
최고기록52ms
해결날짜2021/11/12

풀이

  • 어떻게 보면 멀티 패턴 매칭 문제이기는 한데.. 패턴들의 길이가 전부 2~3이라서 복잡한 알고리즘을 쓸 필요가 없다. 그냥 구현하면 된다
  • 좀더 깔끔한 구현방법을 생각해보자면.. 길이 3짜리의 패턴 한개만을 제외하고 보면, 같은 문자가 여러 패턴에 중복 매칭될수가 없기 때문에 그냥 각 패턴들의 매칭 횟수를 각각 세어서, 매칭 횟수만큼 전체길이에서 빼주면 된다 (2글자가 1글자로 바뀌는거라서 매칭 한번당 1씩 줄어든다). 이 방식대로라면 길이 3인 패턴의 경우는 매칭된 횟수*2를 빼줘야 하지만, 이 패턴은 길이 2인 패턴을 포함한다. 그래서 길이3짜리 패턴이 매칭되었다면, 길이 2짜리 패턴에도 이미 매칭되었을것이므로 거기에서 이미 1이 줄어들었을 것이다. 그래서 추가로 1번만 더 빼주면 된다.
  • 시간 복잡도는 O(전체 문자열 길이 * 패턴의 갯수 * 패턴의 길이) 인데, 패턴의 갯수(=8) 이랑 패턴의 길이(=2 or 3) 은 상수이므로 그냥 O(전체 문자열 길이)로 계산.

코드

"""Solution code for "BOJ 2941. 크로아티아 알파벳".

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

ALPHABETS = ('c=', 'c-', 'dz=', 'd-', 'lj', 'nj', 's=', 'z=')


def main():
    word = input()
    answer = len(word) - sum(word.count(alphabet) for alphabet in ALPHABETS)
    print(answer)


if __name__ == '__main__':
    main()

토론

댓글을 입력하세요:
N S X Y E
 
ps/problems/boj/2941.txt · 마지막으로 수정됨: 2021/11/15 13:20 저자 teferi