일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
- 문자열
- 프로그래머스
- Firebase
- unityui
- UE4
- Unity
- FSM
- 구현
- BFS
- 유니티
- UnrealEngine
- Photon
- Inventory
- 스파르타내일배움캠프
- Unity2D
- C++
- 스택
- 해시
- 유클리드호제법
- 내일배움캠프
- 스파르타내일배움캠프TIL
- 워크플로
- Unity3d
- c#
- 이분탐색
- 포톤
- 순열
- QueryDSL
- 언리얼엔진
- 알고리즘
- Today
- Total
개발 낙서장
[프로그래머스][문자열][C++] 문자열 압축 본문
문자열 압축
https://programmers.co.kr/learn/courses/30/lessons/60057
문제 설명
데이터 처리 전문가가 되고 싶은 "어피치"는 문자열을 압축하는 방법에 대해 공부를 하고 있습니다.
최근에 대량의 데이터 처리를 위한 간단한 비손실 압축 방법에 대해 공부를 하고 있는데, 문자열에서 같은 값이 연속해서 나타나는 것을 그 문자의 개수와 반복되는 값으로 표현하여 더 짧은 문자열로 줄여서 표현하는 알고리즘을 공부하고 있습니다.
간단한 예로 "aabbaccc"의 경우 "2a2ba3c"(문자가 반복되지 않아 한번만 나타난 경우 1은 생략함)와 같이 표현할 수 있는데, 이러한 방식은 반복되는 문자가 적은 경우 압축률이 낮다는 단점이 있습니다.
예를 들면, "abcabcdede"와 같은 문자열은 전혀 압축되지 않습니다.
"어피치"는 이러한 단점을 해결하기 위해 문자열을 1개 이상의 단위로 잘라서 압축하여 더 짧은 문자열로 표현할 수 있는지 방법을 찾아보려고 합니다.
예를 들어, "ababcdcdababcdcd"의 경우 문자를 1개 단위로 자르면 전혀 압축되지 않지만, 2개 단위로 잘라서 압축한다면 "2ab2cd2ab2cd"로 표현할 수 있습니다.
다른 방법으로 8개 단위로 잘라서 압축한다면 "2ababcdcd"로 표현할 수 있으며, 이때가 가장 짧게 압축하여 표현할 수 있는 방법입니다.
다른 예로, "abcabcdede"와 같은 경우, 문자를 2개 단위로 잘라서 압축하면 "abcabc2de"가 되지만, 3개 단위로 자른다면 "2abcdede"가 되어 3개 단위가 가장 짧은 압축 방법이 됩니다.
이때 3개 단위로 자르고 마지막에 남는 문자열은 그대로 붙여주면 됩니다.
압축할 문자열 s가 매개변수로 주어질 때, 위에 설명한 방법으로 1개 이상 단위로 문자열을 잘라 압축하여 표현한 문자열 중 가장 짧은 것의 길이를 return 하도록 solution 함수를 완성해주세요.
제한 사항
- s의 길이는 1 이상 1,000 이하입니다.
- s는 알파벳 소문자로만 이루어져 있습니다.
풀이 방법
어떤 식으로 문자열을 나누고 어떻게 조건을 걸어야할지 잘 감이 잡히지 않았던 문제였다.
우선 문자열을 자르는 기준은 무조건 맨 첫 문자부터 n개로 잘라 압축해야 하므로 1
개부터 s.size()
까지 모든 경우의 수로 잘라서 최솟값을 뽑아냈다.
최솟값을 계산하기 위해 string형 변수와 두 가지 int형 변수와 사용했는데, 문자열을 잘라 비교하기 위한 cmp
, 현재 압축된 문자열이 몇 개인지 세어주는 cnt
, answer
과 최솟값 비교를 할 res
를 사용했다.
비교 문자열과 cmp
가 같을 땐 cnt
를 문자열 갯수만큼 더해주고, 다르면 res
에 지금까지 압축한 문자열의 길이를 계산해서 넣어줬다.
내 코드에서 한 가지 중요 포인트는 25줄이다. 현재 남은 문자열의 길이가 i
보다 작을 경우 반복문을 멈추고 res
에 남은 문자열의 길이만 더해줬다.
문자열 |
abcabcdede |
위와 같은 입력 조건의 경우 문자열을 3개로 자를 때 8개(2abcdede)로 가장 압축이 잘 되는데, 25줄의 조건을 추가하지 않을 경우
cmp | abc | abc | ded | e |
문자열 | abc | 2abc | 2abcded | 2abcdede |
cnt | 3 | 6 | 3 | 3 |
이렇게 마지막에 e 하나만 남지만 3이 추가돼서 값이 잘 나오지 않았었다.
아마 내 풀이보다 훨씬 좋은 풀이가 많을 것이라고 생각한다. 중간중간 고민을 계속하면서 코드를 리셋하고 수정도 많이 했어서 코드가 상당히 난잡하고 이해하기도 어렵다. 다음에는 이런 문제가 나오면 처음부터 잘 설계해서 좀 더 깔끔하고 효율적인 코딩을 해야겠다.
소스 코드
#include <string>
#include <vector>
#include <cmath>
using namespace std;
int solution(string s) {
int answer = s.size(), cnt = 0, res = 0;
int i = 0, j = 0;
for(i = 1; i <= s.size(); i++) {
string cmp = s.substr(0, i);
cnt = i;
res = 0;
for(j = i; j < s.size(); j += i) {
if(cmp != s.substr(j, i)) {
if(cnt <= i)
res += i;
else if((cnt / i) < 10)
res += i + 1;
else if((cnt / i) < 100)
res += i + 2;
else if((cnt / i) < 1000)
res += i + 3;
if(j + i >= s.size())
break;
cnt = i;
cmp = s.substr(j, i);
}
else
cnt += i;
}
if(j < s.size()) {
res += s.size() - j;
}
else {
if(cnt <= i)
res += i;
else if((cnt / i) < 10)
res += i + 1;
else if((cnt / i) < 100)
res += i + 2;
else if((cnt / i) < 1000)
res += i + 3;
}
answer = min(answer, res);
}
return answer;
}
'Algorithm > Programmers' 카테고리의 다른 글
[프로그래머스][BFS][C++] 타겟 넘버 (0) | 2022.03.16 |
---|---|
[프로그래머스][구현][C++] 124 나라의 숫자 (0) | 2022.03.15 |
[프로그래머스][유클리드호제법][C++] 멀쩡한 사각형 (0) | 2022.03.12 |
[프로그래머스][스택][C++] 크레인 인형뽑기 게임 (0) | 2022.03.04 |
[프로그래머스][BFS][C++] 카카오프렌즈 컬러링북 (0) | 2022.03.04 |