어떻게 풀까?
: find랑 substr을 사용하기에는 시간복잡도 비효율적이므로,
인덱스를 통해 접근해 풀도록 하자.
왜 틀림?
: find 를 사용했기 때문
5000 글자에 시간복잡도가 증가됨.
최근 풀이 : 240129
- 틀림
-> find의 시간복잡도는 O(n) 임.
https://www.acmicpc.net/submit/14405/72561323
- 왜 틀렸을까??
최대길이가 5000 글자이고, pi를 못찾는 다면, 여기서부터 시간 소모가 많이 발생함.
그냥 다음번째 인덱스의 원소의 값이 i인지만 확인하면 되잖아.
- 맞음.
https://www.acmicpc.net/submit/14405/49107873
-> substr의 시간복잡도는 O(n) 인데 위의 경우는 2 또는 3만큼의 시간복잡도가
발생하기 때문에 문제 없음.
풀이전략
-
1) 비교 대상이 되는 "pi" , "ka" , "chu" 문자가
단 3개 밖에 없으므로 순차 탐색을 사용하자. -
2) 내 생각에는 substr으로 앞에서부터 카운트 2 , 3을 해서 뽑은 다음에
3개 대상와 비교를 하는 방식으로 진행했음.
-> 완료함.
언제품
- 220914 01:00 ~ 01:13
🔥🔥🔥