Life Engineering
[프로그래머스] 문자열 압축 (C++) 본문
https://programmers.co.kr/learn/courses/30/lessons/60057
#include <string>
#include <vector>
#include <cmath>
using namespace std;
class bucket{
public:
int index;
string pstr;
int cnt;
bucket(int index, string pstr, int cnt){
this->index=index;
this->pstr=pstr;
this->cnt=cnt;
}
};
int solution(string s) {
int len=s.length();
int answer = len;
for (int i=1; i<len; i++){
int ans=0;
bucket b=bucket(i, s.substr(0,i), 1);
ans+=b.pstr.length();
while (b.index<len){
if (b.index+i>len){
ans+=(len-b.index);
break;
}
int start=b.index;
string temp="";
for (int j=start; j<start+i; j++){
temp+=s[j];
}
if (temp.compare(b.pstr)==0){ //비교군과 같을 때
b.cnt+=1;
if (b.cnt==2){ //같은거 2개 나올때
ans+=1;
}
else if (int(log10(b.cnt-1) + 1) < int(log10(b.cnt)+1)){ //자릿수 증가
ans+=1;
}
}
else{ //비교군과 다를 때
b.cnt=1;
b.pstr=temp;
ans+=b.pstr.length();
}
b.index+=i;
}
answer=(ans<answer) ? ans: answer;
}
return answer;
}
카카오 기출. Level 2.
구현 능력+문자열 다루기. 헤맸던 문제. (ㅜㅜ)
시간복잡도는 O(N^2) 로 단위 별로 쪼개서 가장 작은 걸 선택해주면 된다.
그런데 여기서 중요한건 N/2 조각까지만 쪼개도 된다는 것이다.
그 이상 하면 어차피 의미가 없다. 그 이상 하면 기존 압축되지 않은 문자열 길이와 똑같아지므로 의미가 없다.
(이 부분을 문제 풀기전에 머릿속으로 시뮬레이션 해봤어야 하는데 문제푸느라 급급해서 못했다, 이 경우도 O(N^2) 로 나와서 시간 복잡도에 큰 영향은 없었지만..)
나는 bucket 이라는 class를 만들어서 비교대상인 문자열, 그 문자열이 반복된 횟수, 탐색을 할 시작 인덱스 값을 저장했다.
그런데 이렇게 할 필요 없이 for문으로 간단히 돌려주고, cnt 변수만 있으면 된다 (참고: https://yjyoon-dev.github.io/kakao/2020/11/05/kakao-strzip/ ) .
나는 같은거 나올때 cnt를 세주고(이때 자릿수를 계산해서 자릿수가 바뀌면 ans+1 해주는걸로.. 매우 복잡해보인다), 비교군과 다른 새로운거 나올땐 그 문자열의 길이를 세줘서 ans에 집어넣었다. 로직이 깔끔하진 않다.
이 분의 코드를 보니 비교군 temp 문자열을 만들고, 다음 문자열들을 정해진 단위만큼 탐색한 뒤,
동일한 것이 나오면 cnt++ 해주고, 동일한 것이 나오지 않으면 cnt가 2 이상(즉 압축될 수 있다는 의미) 나오면
cnt 를 스트링 변환해줘서 convert 스트링에 집어넣는다. 이후 비교군 temp 문자열도 convert 스트링에 넣어주고,
이제 새로운 비교군을 temp에 집어넣어주고 cnt는 1으로 설정한다. 이렇게 하면 복잡했던 걸 한번에 해결할 수 있다..
비교할때 범위를 벗어난것이 나오면, 기존 cnt가 2이상이면 cnt 값을 convert 문자열에 넣어주고, 비교군도 convert 문자열에 넣어준다.
'Problem Solving' 카테고리의 다른 글
[프로그래머스] 추석 트래픽 (C++) (0) | 2021.08.31 |
---|---|
[프로그래머스] 오픈채팅방 (C++) (0) | 2021.08.30 |
[BOJ 17427] 다리 만들기 (C++) (0) | 2021.08.26 |
[BOJ 7578] 공장 (C++) (0) | 2021.08.20 |
[BOJ 1238] 파티 (C++) (0) | 2021.08.19 |