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()
ps/problems/boj/2941.txt · 마지막으로 수정됨: 2021/11/15 13:20 저자 teferi
토론