
오랜만에 문자열 공부 지대로 해보고자 선택한 문제이다.
근데 너무 어렵다 ㅠ... 역시 카카오인가..?
1. 출처
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
예를 들어, "ababcdcdababcdcd"의 경우 문자를 1개 단위로 자르면 전혀 압축되지 않지만, 2개 단위로 잘라서 압축한다면 "2ab2cd2ab2cd"로 표현할 수 있습니다. 다른 방법으로 8개 단위로 잘라서 압축한다면 "2ababcdcd"로 표현할 수 있으며, 이때가 가장 짧게 압축하여 표현할 수 있는 방법입니다.
입출력 예
"aabbaccc" | 7 |
"ababcdcdababcdcd" | 9 |
"abcabcdede" | 8 |
"abcabcabcabcdededededede" | 14 |
"xababcdcdababcdcd" | 17 |
동일한 문자를 숫자로 압축해 가장 작은 문자열 길이를 만들어 return해주면 되는 문제이다.
너무 어려워서 나는 결국 답을 봤다...
[프로그래머스] 문자열 압축 (Java)
[프로그래머스] 문자열 압축 (Java)
velog.io
이 분 코드가 이해하기 쉬워서 이 분 코드로 공부했다.
2. 설계
우선 for문을 2개 쓸 것이다.
for(int i=1;i<=s.length()/2;i++)
1번 for문은 압축 문자열 길이를 몇으로 잡을 것이냐이다.
홀수든 짝수든 전체 문자열 길이의 반만큼 비교하면 동일 여부를 파악할 수 있다.
예를 들어 aaaa aaaa 8자이면, 4자의 문자열을 가지고 뒤 문자열까지 같다는 것을 알 수 있다. = > 2aaaa
예를 들어 aaaa aaaa b 9자이면, 4자의 문자열을 가지고 뒤 문자열까지 같다는 것을 알 수 있다. 나머지 하나는 다 돌고 난 뒤 추가해주면 된다.
for(int i=1;i<=s.length()/2;i++){
StringBuilder result = new StringBuilder(); //압축 결과
String origin = s.substring(0,i);
그래서 1번 for문을 돌 때 처음 내가 문장과 어떤 단어를 비교할 것인지 단어를 뽑아내는 작업을 진행한다.
비교할 단어는 무조건 0번부터 시작하기 때문에 1번 for문은 단어 뽑아내는 자릿수 끝자리 인셈이다.
1자리수를 비교하고 싶다면 0~1
2자리수를 비교하고 싶다면 0~2
.
.
.
이니까 말이다.
저 result에는 압축 결과를 담을 것이다.
int count = 1; //같은 문자열 수
for(int i=1;i<=s.length()/2;i++){
StringBuilder result = new StringBuilder(); //압축 결과
String origin = s.substring(0,i);
for(int j=i;j<=s.length();j+=i){
그리고 2번째 for문에서는 본격적으로 뽑아낸 단어와 문장을 비교해주는 작업을 할 것이다.
비교는 문장 끝까지 하기 때문에 s.length()만큼 진행하고, 자릿수가 정해져 있기 때문에 해당 자릿수의 단어를 조사하고 나면 자릿수만큼 점프를 뛰어준다 -> j+=i
예 를들어 aa bb cc dd 가 있다면, aa 조사하고 bb 쪽으로 뛰어준다.
int count = 1; //같은 문자열 수
for(int i=1;i<=s.length()/2;i++){
StringBuilder result = new StringBuilder(); //압축 결과
String origin = s.substring(0,i);
for(int j=i;j<=s.length();j+=i){
//어디까지 자를 것인지 i+j가 s.length()을 넘으면 안됨
int endIdx = Math.min(j+i, s.length());
String compare = s.substring(j, endIdx);
j를 i부터 잡은 이유는 내가 조사하고 있는 문장 위치의 시작점을 나타내기 위함이다.
0부터 시작하지 않는 이유는 이미 앞 문장으로 단어 origin을 뽑아냈고, 같을게 뻔하기 때문이다. 그래서 count도 1부터 시작한다.
문자열 탐색을 하고 있는 영역을 정해주기 위해 문자열 탐색 영역의 끝점을 계산해줘야 한다. (=endIdx)
endIdx는 시작점+압축 단어 길이이다. 때문에 시작점(j) + 압축 단어 길이(i) 인 것이다.
i+j는 s.length()를 넘어갈 수 있다.
예를들면 aaaa bbbb의 8자인데, j가 length까지 돌다보면 j는 8까지 나올 수 있다.
i = 4이고, j = 8이면 12이기 때문에 s.length()를 넘어간다.
때문에 Math.min(j+i, s.length())를 이용해 문자열 슬라이싱 진행 시 오류가 안나도록 조정한다.
근데 나는 아직도 이해가 안가는 게 2번째 for에 =을 붙여줘야 하는 것인가이다.
<만 해주고 바로 아래서 bbbb를 추가만 해주면 되는 게 아닌가?
실제로 = 안해주면 답도 다르게 나온다... 흠
더 공부해봐야겠다.
이어서...
나온 endIdx를 토대로 현재 탐색하고 있는 문자열을 compare 변수에 슬라이싱하여 넣는다.
int count = 1; //같은 문자열 수
for(int i=1;i<=s.length()/2;i++){
StringBuilder result = new StringBuilder(); //압축 결과
String origin = s.substring(0,i);
for(int j=i;j<=s.length();j+=i){
//어디까지 자를 것인지 i+j가 s.length()을 넘으면 안됨
int endIdx = Math.min(j+i, s.length());
String compare = s.substring(j, endIdx);
if(origin.equals(compare)){
count++;
}else{ //같지 않아
if(count>=2){
result.append(count);
}
//길이가 1이어도 무조건 그냥 넣어주니까
result.append(origin);
//origin을 현재 다른 compare로 바꿔서 비교 또 시작
origin = compare;
count = 1;//초기화
}
그리고 본격적으로 탐색하고 있는 문자열과 내가 현재 뽑은 문자가 같은지 확인하는 작업을 진행한다.
내가 뽑은 문자와 같다면 압축 횟수 count를 늘려준다.
하지만 다르다면, 지금까지 센 압축 횟수와 뽑았던 문자를 result 스트링빌더에 넣어준다.
길이는 1일 때는 1을 표시하지 않기 때문에 2 이상일 때만 count를 넣는다는 것을 주의하자!
그 뒤에 달라서 else 구문을 들어온 것이기 때문에 origin ( 내가 뽑은 문자)를 compare로 바꿔준다.
달라서 들어온 문자열을 기준으로 또 압축할 게 있는지 탐색하기 위함이다.
새로운 압축 탐색이 진행될거기 때문에 count를 초기화한다.
int count = 1; //같은 문자열 수
int answer = s.length();
for(int i=1;i<=s.length()/2;i++){
StringBuilder result = new StringBuilder(); //압축 결과
String origin = s.substring(0,i);
for(int j=i;j<=s.length();j+=i){
//어디까지 자를 것인지 i+j가 s.length()을 넘으면 안됨
int endIdx = Math.min(j+i, s.length());
String compare = s.substring(j, endIdx);
if(origin.equals(compare)){
count++;
}else{ //같지 않아
if(count>=2){
result.append(count);
}
//길이가 1이어도 무조건 그냥 넣어주니까
result.append(origin);
//origin을 현재 다른 compare로 바꿔서 비교 또 시작
origin = compare;
count = 1;//초기화
}
//마지막 문자열 비교할 때 같다면 count만 증가시키고 나올 것이다.
//달라도 origin에 compare 넣어주니까 한 번 더 넣어준다.
//문자열 길이 중간 완성
result.append(origin);
answer = Math.min(answer, result.length());
}//end
return answer;
}
}
aaaa bbbb를 해보다 보면 알겠지만, 마지막 탐색 문자열 bbbb는 aaaa와 비교 후 달라서 else 구문을 거친 후
한 번 더 들어와 count + 1을 진행한다음 나와 bbbb를 따로 result에 기록해주지 않는다.
때문에 result에 마지막으로 한 번 더 기록해준다.
그 후 완성된 문자열을 answer(초기 상태는 문자열의 총 길이)와 비교하여 짧은 길이로 업데이트 한다.
이렇게 반복하여 최종 결과를 answer로 return 한다.
3. 전체 코드
class Solution {
public int solution(String s) {
int answer = s.length();
int count = 1; //같은 문자열 수
for(int i=1;i<=s.length()/2;i++){
StringBuilder result = new StringBuilder();
String origin = s.substring(0,i);
//j는 문자 자르기 시작점
for(int j=i;j<=s.length();j+=i){
//어디까지 자를 것인지 i+j가 s.length()을 넘으면 안됨
int endIdx = Math.min(j+i, s.length());
String compare = s.substring(j, endIdx);
if(origin.equals(compare)){
count++;
}else{ //같지 않아
if(count>=2){
result.append(count);
}
//길이가 1이어도 무조건 그냥 넣어주니까
result.append(origin);
//origin을 현재 다른 compare로 바꿔서 비교 또 시작
origin = compare;
count = 1;//초기화
}
}
//마지막 문자열 비교할 때 같다면 count만 증가시키고 나올 것이다.
//달라도 origin에 compare 넣어주니까 한 번 더 넣어준다.
//문자열 길이 중간 완성
result.append(origin);
answer = Math.min(answer, result.length());
}//end
return answer;
}
}
어려운 것...
'알고리즘 > 프로그래머스' 카테고리의 다른 글
[프로그래머스] lv1. 완주하지 못한 선수 [#해시] + HashMap 순회법 (0) | 2023.10.18 |
---|---|
[프로그래머스] lv1. 포켓몬 [#해시] (1) | 2023.10.18 |
[프로그래머스] lv3. 네트워크 [#Union-Find] (0) | 2023.10.12 |
[프로그래머스] lv2. 게임 맵 최단 거리 [#DFS #BFS] (0) | 2023.10.12 |
[프로그래머스] Lv2. 타겟넘버 (DFS/BFS) (0) | 2023.10.12 |

오랜만에 문자열 공부 지대로 해보고자 선택한 문제이다.
근데 너무 어렵다 ㅠ... 역시 카카오인가..?
1. 출처
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
예를 들어, "ababcdcdababcdcd"의 경우 문자를 1개 단위로 자르면 전혀 압축되지 않지만, 2개 단위로 잘라서 압축한다면 "2ab2cd2ab2cd"로 표현할 수 있습니다. 다른 방법으로 8개 단위로 잘라서 압축한다면 "2ababcdcd"로 표현할 수 있으며, 이때가 가장 짧게 압축하여 표현할 수 있는 방법입니다.
입출력 예
"aabbaccc" | 7 |
"ababcdcdababcdcd" | 9 |
"abcabcdede" | 8 |
"abcabcabcabcdededededede" | 14 |
"xababcdcdababcdcd" | 17 |
동일한 문자를 숫자로 압축해 가장 작은 문자열 길이를 만들어 return해주면 되는 문제이다.
너무 어려워서 나는 결국 답을 봤다...
[프로그래머스] 문자열 압축 (Java)
[프로그래머스] 문자열 압축 (Java)
velog.io
이 분 코드가 이해하기 쉬워서 이 분 코드로 공부했다.
2. 설계
우선 for문을 2개 쓸 것이다.
for(int i=1;i<=s.length()/2;i++)
1번 for문은 압축 문자열 길이를 몇으로 잡을 것이냐이다.
홀수든 짝수든 전체 문자열 길이의 반만큼 비교하면 동일 여부를 파악할 수 있다.
예를 들어 aaaa aaaa 8자이면, 4자의 문자열을 가지고 뒤 문자열까지 같다는 것을 알 수 있다. = > 2aaaa
예를 들어 aaaa aaaa b 9자이면, 4자의 문자열을 가지고 뒤 문자열까지 같다는 것을 알 수 있다. 나머지 하나는 다 돌고 난 뒤 추가해주면 된다.
for(int i=1;i<=s.length()/2;i++){
StringBuilder result = new StringBuilder(); //압축 결과
String origin = s.substring(0,i);
그래서 1번 for문을 돌 때 처음 내가 문장과 어떤 단어를 비교할 것인지 단어를 뽑아내는 작업을 진행한다.
비교할 단어는 무조건 0번부터 시작하기 때문에 1번 for문은 단어 뽑아내는 자릿수 끝자리 인셈이다.
1자리수를 비교하고 싶다면 0~1
2자리수를 비교하고 싶다면 0~2
.
.
.
이니까 말이다.
저 result에는 압축 결과를 담을 것이다.
int count = 1; //같은 문자열 수
for(int i=1;i<=s.length()/2;i++){
StringBuilder result = new StringBuilder(); //압축 결과
String origin = s.substring(0,i);
for(int j=i;j<=s.length();j+=i){
그리고 2번째 for문에서는 본격적으로 뽑아낸 단어와 문장을 비교해주는 작업을 할 것이다.
비교는 문장 끝까지 하기 때문에 s.length()만큼 진행하고, 자릿수가 정해져 있기 때문에 해당 자릿수의 단어를 조사하고 나면 자릿수만큼 점프를 뛰어준다 -> j+=i
예 를들어 aa bb cc dd 가 있다면, aa 조사하고 bb 쪽으로 뛰어준다.
int count = 1; //같은 문자열 수
for(int i=1;i<=s.length()/2;i++){
StringBuilder result = new StringBuilder(); //압축 결과
String origin = s.substring(0,i);
for(int j=i;j<=s.length();j+=i){
//어디까지 자를 것인지 i+j가 s.length()을 넘으면 안됨
int endIdx = Math.min(j+i, s.length());
String compare = s.substring(j, endIdx);
j를 i부터 잡은 이유는 내가 조사하고 있는 문장 위치의 시작점을 나타내기 위함이다.
0부터 시작하지 않는 이유는 이미 앞 문장으로 단어 origin을 뽑아냈고, 같을게 뻔하기 때문이다. 그래서 count도 1부터 시작한다.
문자열 탐색을 하고 있는 영역을 정해주기 위해 문자열 탐색 영역의 끝점을 계산해줘야 한다. (=endIdx)
endIdx는 시작점+압축 단어 길이이다. 때문에 시작점(j) + 압축 단어 길이(i) 인 것이다.
i+j는 s.length()를 넘어갈 수 있다.
예를들면 aaaa bbbb의 8자인데, j가 length까지 돌다보면 j는 8까지 나올 수 있다.
i = 4이고, j = 8이면 12이기 때문에 s.length()를 넘어간다.
때문에 Math.min(j+i, s.length())를 이용해 문자열 슬라이싱 진행 시 오류가 안나도록 조정한다.
근데 나는 아직도 이해가 안가는 게 2번째 for에 =을 붙여줘야 하는 것인가이다.
<만 해주고 바로 아래서 bbbb를 추가만 해주면 되는 게 아닌가?
실제로 = 안해주면 답도 다르게 나온다... 흠
더 공부해봐야겠다.
이어서...
나온 endIdx를 토대로 현재 탐색하고 있는 문자열을 compare 변수에 슬라이싱하여 넣는다.
int count = 1; //같은 문자열 수
for(int i=1;i<=s.length()/2;i++){
StringBuilder result = new StringBuilder(); //압축 결과
String origin = s.substring(0,i);
for(int j=i;j<=s.length();j+=i){
//어디까지 자를 것인지 i+j가 s.length()을 넘으면 안됨
int endIdx = Math.min(j+i, s.length());
String compare = s.substring(j, endIdx);
if(origin.equals(compare)){
count++;
}else{ //같지 않아
if(count>=2){
result.append(count);
}
//길이가 1이어도 무조건 그냥 넣어주니까
result.append(origin);
//origin을 현재 다른 compare로 바꿔서 비교 또 시작
origin = compare;
count = 1;//초기화
}
그리고 본격적으로 탐색하고 있는 문자열과 내가 현재 뽑은 문자가 같은지 확인하는 작업을 진행한다.
내가 뽑은 문자와 같다면 압축 횟수 count를 늘려준다.
하지만 다르다면, 지금까지 센 압축 횟수와 뽑았던 문자를 result 스트링빌더에 넣어준다.
길이는 1일 때는 1을 표시하지 않기 때문에 2 이상일 때만 count를 넣는다는 것을 주의하자!
그 뒤에 달라서 else 구문을 들어온 것이기 때문에 origin ( 내가 뽑은 문자)를 compare로 바꿔준다.
달라서 들어온 문자열을 기준으로 또 압축할 게 있는지 탐색하기 위함이다.
새로운 압축 탐색이 진행될거기 때문에 count를 초기화한다.
int count = 1; //같은 문자열 수
int answer = s.length();
for(int i=1;i<=s.length()/2;i++){
StringBuilder result = new StringBuilder(); //압축 결과
String origin = s.substring(0,i);
for(int j=i;j<=s.length();j+=i){
//어디까지 자를 것인지 i+j가 s.length()을 넘으면 안됨
int endIdx = Math.min(j+i, s.length());
String compare = s.substring(j, endIdx);
if(origin.equals(compare)){
count++;
}else{ //같지 않아
if(count>=2){
result.append(count);
}
//길이가 1이어도 무조건 그냥 넣어주니까
result.append(origin);
//origin을 현재 다른 compare로 바꿔서 비교 또 시작
origin = compare;
count = 1;//초기화
}
//마지막 문자열 비교할 때 같다면 count만 증가시키고 나올 것이다.
//달라도 origin에 compare 넣어주니까 한 번 더 넣어준다.
//문자열 길이 중간 완성
result.append(origin);
answer = Math.min(answer, result.length());
}//end
return answer;
}
}
aaaa bbbb를 해보다 보면 알겠지만, 마지막 탐색 문자열 bbbb는 aaaa와 비교 후 달라서 else 구문을 거친 후
한 번 더 들어와 count + 1을 진행한다음 나와 bbbb를 따로 result에 기록해주지 않는다.
때문에 result에 마지막으로 한 번 더 기록해준다.
그 후 완성된 문자열을 answer(초기 상태는 문자열의 총 길이)와 비교하여 짧은 길이로 업데이트 한다.
이렇게 반복하여 최종 결과를 answer로 return 한다.
3. 전체 코드
class Solution {
public int solution(String s) {
int answer = s.length();
int count = 1; //같은 문자열 수
for(int i=1;i<=s.length()/2;i++){
StringBuilder result = new StringBuilder();
String origin = s.substring(0,i);
//j는 문자 자르기 시작점
for(int j=i;j<=s.length();j+=i){
//어디까지 자를 것인지 i+j가 s.length()을 넘으면 안됨
int endIdx = Math.min(j+i, s.length());
String compare = s.substring(j, endIdx);
if(origin.equals(compare)){
count++;
}else{ //같지 않아
if(count>=2){
result.append(count);
}
//길이가 1이어도 무조건 그냥 넣어주니까
result.append(origin);
//origin을 현재 다른 compare로 바꿔서 비교 또 시작
origin = compare;
count = 1;//초기화
}
}
//마지막 문자열 비교할 때 같다면 count만 증가시키고 나올 것이다.
//달라도 origin에 compare 넣어주니까 한 번 더 넣어준다.
//문자열 길이 중간 완성
result.append(origin);
answer = Math.min(answer, result.length());
}//end
return answer;
}
}
어려운 것...
'알고리즘 > 프로그래머스' 카테고리의 다른 글
[프로그래머스] lv1. 완주하지 못한 선수 [#해시] + HashMap 순회법 (0) | 2023.10.18 |
---|---|
[프로그래머스] lv1. 포켓몬 [#해시] (1) | 2023.10.18 |
[프로그래머스] lv3. 네트워크 [#Union-Find] (0) | 2023.10.12 |
[프로그래머스] lv2. 게임 맵 최단 거리 [#DFS #BFS] (0) | 2023.10.12 |
[프로그래머스] Lv2. 타겟넘버 (DFS/BFS) (0) | 2023.10.12 |