반응형
문제분석
규칙에따라 압축을해줘서 문자열의 길이를 반환하는 문제입니다.
규칙이 1개 2개 3개...단위로 잘라서 압축합니다.
1개 2개 3개..단위로 자른 문자열중 가장 짧은 경우의 길이를 구합니다.
구현난이도가 조금 낮은게, abcabcdede의 압축결과가 2abcdede가 답이듯이,
3개 단위로 잘라도, dede를 압축할 필요가없습니다.(3개단위는 무조건 3개단위)
문제풀이
1개 2개 3개..단위마다 압축한 문자열의 길이를 저장하는 result배열 선언과
1개 2개 3개..단위마다 자른 문자열을 담아내기위한 str리스트를 저장합니다.
str리스트를통해서, 자른문자열이 압축이 가능한지를 판별합니다.
첫번째 큰 반복은 1~ 문자열s의 절반만큼 반복합니다. (X개 단위 반복)
13~20라인의 2차반복은, 단위 i만큼 문자열을 잘라내어, str리스트에 넣어놓습니다.
21~39라인의 2차반복은, str에 저장한 문자열을 비교하며, 압축이 가능할때와, 가능하지 않을때를
구현해주었습니다.
압축이 완료됬다면, result배열에 결과를저장하고, 다음 반복을위해 str문자열을 clear해줍니다.
모든 반복이완료했다면, 제일 적은 문자열의 길이를 반환합니다.
|
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
|
import java.util.*;
class Solution {
public int solution(String s) {
int answer = 0;
int[] result =new int[s.length()/2];
int cnt=1;
String temp="";
List<String> str = new LinkedList<>();
//길이가 2이상인 문자열을 1~n까지 자르자.
for(int i=1;i<=s.length()/2;i++){
//문자열 i만큼자르기
for(int j=0;j<s.length();j+=i){
if(j+i>=s.length()){
str.add(s.substring(j));
}
else{
str.add(s.substring(j,j+i));
}
}
str.add("");
//압축하기
for(int k=0;k<str.size()-1;k++){
if(str.get(k).equals(str.get(k+1))){
cnt+=1;
str.remove(str.get(k));
k--;
}
else{
if(cnt==1){
temp+=str.get(k);
}
else{
temp+=cnt+str.get(k);
cnt=1;
}
}
}
result[i-1]=temp.length();
temp="";
str.clear();
}
//길이가 1인경우 예외처리.....
if(s.length()==1){
return 1;
}
Arrays.sort(result);
answer=result[0];
return answer;
}
}
|
cs |
반응형
'알고리즘 > 프로그래머스 Level2' 카테고리의 다른 글
| [프로그래머스,자바] Level2: 빛의 경로 사이클 (0) | 2021.09.25 |
|---|---|
| [프로그래머스,자바] Level2:멀쩡한 사각형 (0) | 2021.09.23 |
| [프로그래머스,자바] Level2:오픈채팅방 (0) | 2021.09.22 |
| [프로그래머스,자바] Level2: 위클리챌린지 7주차 [입실 퇴실] (0) | 2021.09.14 |
| [프로그래머스,자바] Level2: 위클리 챌린지 5주차 [모음 사전] (1) | 2021.09.01 |