A. 문제설명
문제에 대한 자세한 설명은 링크 참조
programmers.co.kr/learn/courses/30/lessons/60057
코딩테스트 연습 - 문자열 압축
데이터 처리 전문가가 되고 싶은 어피치는 문자열을 압축하는 방법에 대해 공부를 하고 있습니다. 최근에 대량의 데이터 처리를 위한 간단한 비손실 압축 방법에 대해 공부를 하고 있는데, 문자
programmers.co.kr
1. 문자열 s가 존재
2. 문자열에서 중복 발생하는 문자들의 발생횟수를 기록하여 문자열을 압축하려 함
3. 문자열을 잘라 압축하는 단위는 1개이상
4. 문자열을 잘라 압축하는 표현 중, 가장 길이가 짧은 것을 반환
B. 접근법
문제 조건에 따라 문자열 재단이 주요한 문제. 완전 탐색으로 길이 1부터 |문자열 길이| / 2까지의 압축길이 방식의 모든 압축열을 만들어서 확인
구현 자체에 특별한 점은 없으나, 특정경우에 대한 반례가 있다.
입출력 예 #5
"xababcdcdababcdcd"
문자열은 제일 앞부터 정해진 길이만큼 잘라야 합니다.
따라서 주어진 문자열을 x / ababcdcd / ababcdcd 로 자르는 것은 불가능 합니다.
이 경우 어떻게 문자열을 잘라도 압축되지 않으므로 가장 짧은 길이는 17이 됩니다.문자열은 반드시 첫번째 문자부터 정해진 길이만큼 잘라야할 것.
C. 풀이
1. 현재 기준 위치에서 substr과 다음 substr을 비교
2. 현재 위치가 다음 substr을 비교가능할 때
2-1. 만약 substr이 같은게 없으면 문자열에 그대로 해당 위치 문자 붙이고 continue
2-2. 만약 substr이 같은게 있으면 substr들을 확인가능한 위치까지 비교. 그 갯수만큼 인덱스 이동, tmp에 이어붙임
3. 현재 위치가 다음 substr을 비교불가능할 때, 남은 문자열을 tmp에 붙여 for문 탈출
4. 더 짧은 압축열을 찾으면 길이 정답에 업데이트
D. 내 코드
