Recent Posts
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
Tags
- tolerated
- 깡돼후
- 티스토리챌린지
- PytestPluginManager
- pytest
- python
- 자원부족
- Spring Batch
- kotlin
- 코루틴 컨텍스트
- mp4fpsmod
- 헥사고날아키텍처 #육각형아키텍처 #유스케이스
- JanusWebRTCGateway
- 오블완
- terminal
- VARCHAR (1)
- k8s #kubernetes #쿠버네티스
- vfr video
- JanusWebRTCServer
- PersistenceContext
- taint
- JanusWebRTC
- 겨울 부산
- JanusGateway
- 개성국밥
- table not found
- Value too long for column
- 코루틴 빌더
- preemption #
- 달인막창
Archives
너와 나의 스토리
[Programmers] 2019 카카오 개발자 겨울 인턴십 - 문자열 압축 본문
Algorithm/브루트 포스 (Brute-Force )
[Programmers] 2019 카카오 개발자 겨울 인턴십 - 문자열 압축
노는게제일좋아! 2020. 5. 4. 20:04반응형
문제: https://programmers.co.kr/learn/courses/30/lessons/60057
문제 풀이:
주목할 조건:
- 앞에서부터 반복되는 문자열이어야 한다.
- 반복되는 문자열의 길이가 같아야 한다.
- 반복되는 문자열의 길이가 [10,100) 사이의 숫자이면 길이가 2 증가하고 e.g. 11abc. -> 문자열 길이 5
풀이:
- 문자열의 길이를 1부터 n/2가지 늘려가면서 중복 문자열 개수를 카운트
- 최대한 길게 겹치는 문자는 절반씩 같은 문자 e.g. abcabc
- 맨 처음 문자열을 sub라고 두고, 다음부터 보는 문자열을 cnt로 둔다
- 같으면 cnt++
- 아니면 지금까지 겹친 문자열 개수 계산한 다음 cnt=0으로 초기화
소스 코드:
int solution(string s) {
int len = s.size();
int answer = len;
for (int i = 1; i <= len / 2; i++) {
string sub= s.substr(0, i);
int cnt = 0;
int tmp = 0;
for (int j = i; j <= len - i; j+=i) {
string cur = s.substr(j, i);
if (sub == cur) cnt++;
else {
tmp += cnt * i;
if (cnt == 999) tmp -= 4;
else if (cnt >= 99)tmp -= 3;
else if (cnt >= 9)tmp -= 2;
else if (cnt >= 1) tmp -= 1;
cnt = 0;
sub = cur;
}
}
tmp += cnt * i;
if (cnt == 999) tmp -= 4;
else if (cnt >= 99)tmp -= 3;
else if (cnt >= 9)tmp -= 2;
else if (cnt >= 1) tmp -= 1;
answer = min(answer, len - tmp);
}
return answer;
}
반응형
'Algorithm > 브루트 포스 (Brute-Force )' 카테고리의 다른 글
[BOJ] 16955 오목, 이길 수 있을까? (0) | 2020.10.09 |
---|---|
[BOJ] 12100번 2048(Easy) (0) | 2020.06.01 |
[BOJ] 14889 스타트와 링크 (0) | 2020.03.30 |
(BOJ) 16235 나무 재테크 (0) | 2019.05.10 |
(BOJ) 14476 최대공약수 하나 빼기 (0) | 2019.05.09 |
Comments