안녕하세요 멍청한 토끼입니다.
이번 문제는 2020 카카오 블라인드 채용 문제에 있는
Lv1 문자열 압축 문제 입니다.
※ 저의 풀이가 무조건적인 정답은 아닙니다.
다른 코드가 좀더 효율적이고 좋을 수 있습니다.
다른사람들의 풀이는 언제나 참고만 하시기 바랍니다.
문제 주소입니다.
https://programmers.co.kr/learn/courses/30/lessons/60057
코딩테스트 연습 - 문자열 압축 | 프로그래머스
데이터 처리 전문가가 되고 싶은 어피치는 문자열을 압축하는 방법에 대해 공부를 하고 있습니다. 최근에 대량의 데이터 처리를 위한 간단한 비손실 압축 방법에 대해 공부를 하고 있는데, 문자열에서 같은 값이 연속해서 나타나는 것을 그 문자의 개수와 반복되는 값으로 표현하여 더 짧은 문자열로 줄여서 표현하는 알고리즘을 공부하고 있습니다. 간단한 예로 aabbaccc의 경우 2a2ba3c(문자가 반복되지 않아 한번만 나타난 경우 1은 생략함)와 같이 표현할 수
programmers.co.kr
목차
1. 문제 설명
2. 문제 해석
3. 소스 코드
3.1 주석 없는 코드
3.2 주석 있는 코드
3.3 테스트 코드
4. 결과
1. 문제 설명
|
데이터 처리 전문가가 되고 싶은 어피치는 문자열을 압축하는 방법에 대해 공부를 하고 있습니다. 최근에 대량의 데이터 처리를 위한 간단한 비손실 압축 방법에 대해 공부를 하고 있는데, 문자열에서 같은 값이 연속해서 나타나는 것을 그 문자의 개수와 반복되는 값으로 표현하여 더 짧은 문자열로 줄여서 표현하는 알고리즘을 공부하고 있습니다. 간단한 예로 aabbaccc의 경우 2a2ba3c(문자가 반복되지 않아 한번만 나타난 경우 1은 생략함)와 같이 표현할 수 있는데, 이러한 방식은 반복되는 문자가 적은 경우 압축률이 낮다는 단점이 있습니다. 예를 들면, abcabcdede와 같은 문자열은 전혀 압축되지 않습니다. 어피치는 이러한 단점을 해결하기 위해 문자열을 1개 이상의 단위로 잘라서 압축하여 더 짧은 문자열로 표현할 수 있는지 방법을 찾아보려고 합니다. |
|
예를 들어, ababcdcdababcdcd의 경우 문자를 1개 단위로 자르면 전혀 압축되지 않지만, 2개 단위로 잘라서 압축한다면 2ab2cd2ab2cd로 표현할 수 있습니다. 다른 방법으로 8개 단위로 잘라서 압축한다면 2ababcdcd로 표현할 수 있으며, 이때가 가장 짧게 압축하여 표현할 수 있는 방법입니다. 다른 예로, abcabcdede와 같은 경우, 문자를 2개 단위로 잘라서 압축하면 abcabc2de가 되지만, 3개 단위로 자른다면 2abcdede가 되어 3개 단위가 가장 짧은 압축 방법이 됩니다. 이때 3개 단위로 자르고 마지막에 남는 문자열은 그대로 붙여주면 됩니다. |
문제!!
|
압축할 문자열 s가 매개변수로 주어질 때, 위에 설명한 방법으로 1개 이상 단위로 문자열을 잘라 압축하여 표현한 문자열 중 가장 짧은 것의 길이를 return 하도록 solution 함수를 완성해주세요. |
제한사항
|
예시
| s | return |
| "aabbaccc" | 7 |
| "ababcdcdababcdcd" | 9 |
| "abcabcdede" | 8 |
| "abcabcabcabcdededededede" | 14 |
| "xababcdcdababcdcd" | 17 |
| "a" | 1 |
| "aaaaa" | 2 |
| "aaaaaaaaaa" | 3 |
|
입출력 예 #1 문자열을 1개 단위로 잘라 압축했을 때 가장 짧습니다. 입출력 예 #2 문자열을 8개 단위로 잘라 압축했을 때 가장 짧습니다. 입출력 예 #3 문자열을 3개 단위로 잘라 압축했을 때 가장 짧습니다. 입출력 예 #4 문자열을 2개 단위로 자르면 abcabcabcabc6de 가 됩니다. 입출력 예 #5 문자열은 제일 앞부터 정해진 길이만큼 잘라야 합니다. 입출력 예 #7 문자열의 길이가 1입니다. 더이상 압축할 수 없으므로 길이는 1이 됩니다. 입출력 예 #8 a가 5개 이므로 5a가 됩니다. 길이는 2가 됩니다. 입출력 예 #9 a가 10개이므로 10a가됩니다. 길이가 3이 됩니다. |
2. 문제풀이
# 삽질 이야기
|
1. 처음에는 단순하게 새로운 임시 string을 만들어서 검사를 할때마다 넣고 길이를 측정하여 작은 길이를 반환하도록 설정했습니다. 그랬더니 1이 반환이 안되더군요
2. 두번째는 옮기는 과정에서 마지막 문자열을 그대로 붙여줘야 하는데 그 과정이 처리가 잘 되지 않았습니다.
3. 수정을 거쳐 완료가 됬다구 생각했는데 기본케이스는 통과했지만 테스트의 몇가지가 통과가 안됐습니다.
4. 기존의 방법을 갈아엎고 압축되는 만큼 원래의 길이에서 감소시키고, 표시되는 숫자만큼 증가시키는 방식을 이용했습니다. 마지막 문자열 처리를 해주지 않아도 되는 장점이 있고, 기존의 문자열을 가지고 시작하기때문에 문자열이 1이어도 처리가 됬습니다. 풀이는 아래와 같습니다. |
최종 문제풀이
|
1. 문자열을 압축하는 방법은 1개 압축부터 문자열 길이의 반절까지 압축하는 방법이 있습니다. 반복문을 이용하여 1개 압축부터 문자열 길이의 반절까지 시도를 하며 제일 짧은 방법을 찾습니다.
2. 현재 탐색하는 문자열 현재 위치 + 압축개수 와 다음 문자열을 비교합니다. ex) aaabbc이고 2압축이라고 하면 aa와 ab를 비교합니다.
3. 문자열이 같다면 그다음 문자열과 비교를합니다. 문자열이 같을 때는 count변수를 이용하여 몇개가 중복되는지 확인을 합니다. 달라지거나 문자열 길이가 끝난다면 count * 압축개수 만큼 길이를 줄여줍니다. 압축한 만큼 비교 위치를 압축한 뒤의 문자열로 보내줍니다.
4. 문자열이 다르다면 비교하는 반복문을 탈출하고, 기준을 다음문자열로 옮깁니다.
5. 문자열이 끝날때까지 모든 비교가 끝났다면 지금까지 짧았던 길이와 비교하여, 더 짧은 길이로 갱신을 합니다. |
3. 소스코드
3.1 주석없는 코드
|
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
|
#include <string>
using namespace std;
int solution(string s) {
int answer = s.length();
for (int i = 1; i <= s.length() / 2; i++) {
int len = s.length();
for (int j = 0; j < s.length(); j++) {
for (int count = 0, z = i; j + z < s.length(); z += i){
if (s.substr(j, i) == s.substr(j + z, i)) count++;
else {
len -= i * count;
if (count) len += to_string(count + 1).length();
j += z - 1;
break;
}
if (j + z + i >= s.length()) {
len -= i * count;
len += to_string(count + 1).length();
j += z;
}
}
}
if (len < answer) answer = len;
}
return answer;
}
|
|
3.2 주석있는 코드
|
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
|
#include <string>
using namespace std;
int solution(string s) {
int answer = s.length();
//경우의 수 탐색하기
for (int i = 1; i <= s.length() / 2; i++) {
int len = s.length();
//문자열을 전체 돌면서 반복
for (int j = 0; j < s.length(); j++) {
//부분 비교하기
for (int count = 0, z = i; j + z < s.length(); z += i){
//뒤부분과 일치한다면 count 증가
if (s.substr(j, i) == s.substr(j + z, i)) count++;
//뒤에부분이 일치하지않는다면 count확인후 중복되는 문자열만큼 길이줄임
//추가되는 숫자만큼 길이증가
else {
len -= i * count;
if (count) len += to_string(count + 1).length();
j += z - 1;
break;
}
// 한번이라도 압축이 된상태에서 뒤에가 계산이 안된다면
//압축후 추가하고 나머지를 뒤에 추가
if (j + z + i >= s.length()) {
len -= i * count;
len += to_string(count + 1).length();
j += z;
}
}
}
//문자열 길이를 비교해서 적어진다면 적은걸로 변경
if (len < answer) answer = len;
}
return answer;
}
|
|
3.3 테스트 코드 추가
|
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
47
48
49
50
51
52
53
54
55
56
57
58
59
|
#include <string>
#include <iostream>
using namespace std;
int solution(string s) {
int answer = s.length();
//경우의 수 탐색하기
for (int i = 1; i <= s.length() / 2; i++) {
int len = s.length();
//문자열을 전체 돌면서 반복
for (int j = 0; j < s.length(); j++) {
//부분 비교하기
for (int count = 0, z = i; j + z < s.length(); z += i){
//뒤부분과 일치한다면 count 증가
if (s.substr(j, i) == s.substr(j + z, i)) count++;
//뒤에부분이 일치하지않는다면 count확인후 중복되는 문자열만큼 길이줄임
//추가되는 숫자만큼 길이증가
else {
len -= i * count;
if (count) len += to_string(count + 1).length();
j += z - 1;
break;
}
// 한번이라도 압축이 된상태에서 뒤에가 계산이 안된다면
//압축후 추가하고 나머지를 뒤에 추가
if (j + z + i >= s.length()) {
len -= i * count;
len += to_string(count + 1).length();
j += z;
}
}
}
//문자열 길이를 비교해서 적어진다면 적은걸로 변경
if (len < answer) answer = len;
}
return answer;
}
void print(string s, int answer) {
int t = solution(s);
if (answer == t)
cout << "정답" << endl;
else
cout << "틀림" << endl;
}
int main() {
print("a", 1);
print("aaaaa", 2);
print("aaaaaaaaaa", 3);
print("aabbaccc", 7);
print("ababcdcdababcdcd", 9);
print("abcabcdede", 8);
print("abcabcabcabcdededededede", 14);
print("xababcdcdababcdcd", 17);
return 0;
}
|
|
4. 결과
'코딩테스트 > 프로그래머스' 카테고리의 다른 글
| 라면공장 C++(힙, 우선순위큐)[프로그래머스] (0) | 2019.11.17 |
|---|---|
| 숫자의 표현 C++ [프로그래머스] (0) | 2019.11.16 |
| 후보키 C++ (카카오 블라인드 2019)[프로그래머스] (10) | 2019.11.15 |
| 다트게임 C++(카카오 블라인드 2018)[프로그래머스] (0) | 2019.11.15 |
| 무지의 먹방 라이브 (C++, 2019 카카오 블라인드 채용)[프로그래머스] (0) | 2019.11.13 |
댓글