프로그래머스__[문제풀이: 카카오 블라인드_문자열 압축]

Jaewon Lee·2021년 8월 5일
0

Algorithm

목록 보기
21/36
post-thumbnail

On.


Algorithm


1. 수도코드

1) 주어진 문자열을 for문으로 반만 순회한다. -- 첫번째 for문 (문자열의 반이 넘어가면 어차피 압축이 불가능)

2) "aabbaccc"라는 문자열이 있으면 "a", "aa", "aab", "aabb" 라는 문자열로 생성할 수 있게 끔 문자열 변수(prev) 생성

3) "a", "aa", "aab", "aabb"를 제외한 나머지 문자열을 순회 -- 두번째 for문 (2번에서 생성한 현재문자열 사이즈 만큼 띄엄 띄엄)해서 문자열 변수(curr) 생성

4-1) prev와 curr이 같으면 count += 1

4-2) prev와 curr이 다르면, 또 두가지의 경우로 나뉨

  • count가 1보다 크면 이전에 일치한 문자가 있었다는 소리니까 "2a", "2aab"등과 같이 압축해야 한다. 따라서, compress += 이전 문자열(prev)의 길이 + len(str(count))
  • count가 1이하라면, compress += 이전 문자열(prev)의 길이
  • 위에 두개의 분기가 끝나면 prev에 curr을 할당하고, count는 다시 1로 초기화

5) 두번째 for문이 끝날 때마다 compress가 가장 최소 값인지 확인하고, answer에 할당한다.

6) 첫번째 for문이 끝나면 answer를 리턴한다.


2. 구현코드

def solution(s):
    answer = len(s)
    
    for size in range(1, len(s) // 2 + 1):
        count = 1
        compress = 0
        prev = s[:size]
        
        for i in range(size, size + len(s), size):
            curr = s[i : i + size]
            if prev == curr:
                count += 1
            else:
                if count > 1:
                    compress += len(prev) + len(str(count))
                else:
                    compress += len(prev)
                prev = curr
                count = 1
        
        answer = min(compress, answer)
    
    return answer

3. 배운 점

  • 입력과 출력을 명확히 하자! 문제에서 입력과 출력이 주어지지만, 문제를 풀다보면 무엇을 출력해야하는지 잊는 경우가 있다. 출력물을 확실히 기억해서 흐트러짐이 없는 풀이 과정을 연습하자.

  • 단순 구현 문제는 그냥,,,,,문제 많이 풀어보자....ㅎㅎ



Off.


프론트와 백을 넘나드는 리드 개발자가 되는 그날까지 🔥🔥🔥

profile
Communication : any

0개의 댓글