📌 문제 링크: https://www.acmicpc.net/problem/12891
12891번: DNA 비밀번호
평소에 문자열을 가지고 노는 것을 좋아하는 민호는 DNA 문자열을 알게 되었다. DNA 문자열은 모든 문자열에 등장하는 문자가 {‘A’, ‘C’, ‘G’, ‘T’} 인 문자열을 말한다. 예를 들어 “ACKA”
www.acmicpc.net
✅ 내 풀이(Success) :
🚩 Idea:
DNA 비밀번호 문자열의 길이가 최대 1,000,000으로 만약 시간 복잡도가 O(N)보다 큰 알고리즘을 적용한다면 '시간 초과'가 발생한다. 그래서 슬라이딩 윈도우와 단일 for 반복문을 사용해서 시간 복잡도을 O(N)으로 맞추고, 부분 문자열에 등장하는 알파벳의 개수를 세기위해서 딕셔너리를 사용했다.
'알고리즘 문제 풀이: 파이썬 > BOJ' 카테고리의 다른 글
| [BOJ_5648] 역원소 정렬 (0) | 2022.12.19 |
|---|---|
| [BOJ_1449] 수리공 항승 (0) | 2022.11.28 |
| [BOJ_1926] 그림 (0) | 2022.11.10 |
| [BOJ_11501] 주식 (0) | 2022.11.09 |
| [BOJ_6550] 부분 문자열 (0) | 2022.11.08 |
댓글