문자열을 다루는 문제입니다.
문자열을 몇 개 단위로 자를지 모두 봐줘야 하고, 문자열의 길이는 최대 1000이기 때문에 2중 for문으로 쉽게 풀 수 있습니다.
class Solution {
public int solution(String s) {
int answer = s.length();
for(int subLen=1;subLen<=s.length()/2; subLen++) {
String newStr = "";
String standard = s.substring(0, subLen);
int cnt = 1;
for(int i=subLen;i<s.length();i+=subLen) {
if(i+subLen > s.length()) {
newStr+=s.substring(i);
break;
}
String comp = s.substring(i, i+subLen);
if(standard.equals(comp)) cnt+=1;
else {
if(cnt>1) newStr+=Integer.toString(cnt)+standard;
else newStr+=standard;
standard = comp;
cnt = 1;
}
}
if(cnt>1) newStr+=Integer.toString(cnt)+standard;
else newStr+=standard;
answer = answer < newStr.length() ? answer : newStr.length();
}
return answer;
}
}
subLen
: 자른 문자열의 길이 (1개부터 s.length()/2
개 만큼)
newStr
: 압축한 문자열
standard
: 비교의 기준이 될 문자열
cnt
: 반복된 횟수
comp
: 비교할 문자열
우선 subLen
이 전체 문자열의 길이의 반보다 크다면 반복될 수 없으므로 subLen
은 문자열의 반까지만 봐주면 됩니다.
standard
를 먼저 구해주고 그 다음부터 comp
를 구해서 standard
와 comp
를 비교하면서 cnt
를 구해줍니다.
i+subLen > s.length()
라면 마지막까지 체크를 한 것이므로 고대로 넣어주면 됩니다.
standard
와 comp
가 다르다면 cnt
가 2 이상일 때 newStr
에 숫자와 함께 반복된 문자열을 추가해주고, standard
를 comp
로 업데이트 시켜줍니다.
반복문이 다 돌았을 때 남은 것들을 newStr
에 넣어주면 끝!
문자열을 여러 개 단위로 잘랐을 때, 길이의 최소값을 구해야 하므로
answer = answer < newStr.length() ? answer : newStr.length();
로 answer를 구하면 끝입니다.
감사합니다
카카오 공채 뜬 김에 다시 풀어보았슴다... 이번엔 스택을 이용해서 풀어보았습니다..
저번에 풀었던 방법과 아이디어는 같습니다. 문자열의 길이가 1~length/2까지 잘라서 일일이 비교해주는거져.
다만 잘라서 스택에 넣어줌으로써 비교를 해줬습니다!!
스택의 top 에 있는 친구랑 비교하면서 같으면 넣고 다르면 빼는거져.
아이디어는 참 좋은데 맨마지막 문자열 자른 친구는 길이가 지맘대로기 때문에 이거 처리한다고 쪼까 걸렸슴니다.
public int solution(String s) {
int answer = 1000;
if(s.length() == 1) return 1;
for (int i = 1; i <= s.length() / 2; i++) {
StringBuilder compression = new StringBuilder();
Stack<String> stack = new Stack<>();
for(int j =0; j < s.length(); j+=i) {
String sub;
if(j + i > s.length()) // 마지막 부분 문자열
sub = s.substring(j);
else
sub = s.substring(j, j + i);
if(stack.isEmpty()) {
stack.push(sub);
continue;
}
if(stack.peek().equals(sub)) {
stack.push(sub);
}else {
int compLen = stack.size();
compression.append(compLen > 1 ? compLen+stack.peek() : stack.peek());
stack.clear();
stack.push(sub);
}
}
int compLen = stack.size();
compression.append(compLen > 1 ? compLen+stack.pop() : stack.pop());
answer = Math.min(answer, compression.length());
}
return answer;
}
'Algorithm > Programmers' 카테고리의 다른 글
[2020 KAKAO BLIND RECRUITMENT][시뮬레이션/완전 탐색] 자물쇠와 열쇠 - Java (0) | 2020.08.25 |
---|---|
[2020 KAKAO BLIND RECRUITMENT][문자열 처리] 괄호 변환 - Java (0) | 2020.08.24 |
[2018 KAKAO BLIND RECRUITMENT][문자열 처리] [1차] 비밀지도 - Java (0) | 2020.08.15 |
[2017 카카오코드 예선][BFS] 카카오프렌즈 컬러링북 - Java (0) | 2020.08.15 |
[Summer/Winter Coding(2019)][시뮬레이션] 종이접기 - Java (0) | 2020.06.23 |