실수: 문자열의 길이가 1일경우를 생각하지 못해서 시간을 낭비.
시간 복잡도: O(N^2 +알파..?)
시간복잡도 계산이 잘 안된다.
12번 라인과 17번 라인이 서로 의존적이다.
n이1인경우 strncmp는 거의 연산비용이 들지 않게되고...
그렇다고 n을 N으로 키우면... 중간의 while(right < N) 반복문 접근수가 줄어든다.
잘 모르겠다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 | #include <string> #include <vector> #include <iostream> #include <string.h> using namespace std; int solution(string s) { int answer = 1001; int N = s.length(); if (N == 1) return 1; for (int n = 1; n < N; n++) { string str = ""; int left = 0, right = n; int equalCnt = 1; while(right < N){ if (strncmp(&s[left], &s[right], n) == 0) { equalCnt++; } else { if (equalCnt == 1) { str = str + s.substr(left, n); } else { str = str + to_string(equalCnt) + s.substr(left, n); } left = right; equalCnt = 1; } right += n; } if (equalCnt == 1) { str = str + s.substr(left, n); } else { str = str + to_string(equalCnt) + s.substr(left, n); } if (answer > str.length()) { answer = str.length(); } //std::cout << str << endl; } return answer; } | cs |
'알고리즘' 카테고리의 다른 글
| Making A Large Island (0) | 2025.02.02 |
|---|---|
| Redundant Connection (0) | 2025.02.01 |
| 프로그래머스 (Programmers) 입국심사 (0) | 2021.01.12 |
| 프로그래머스 (Programmers) 가장 먼 노드 (0) | 2021.01.11 |
| 프로그래머스 (Programmers) 섬 연결하기 (0) | 2021.01.11 |
짬뽕얼큰하게
