Notion에서 작성된 글이라, 여기에서 더 깔끔하게 보실 수 있습니다! 😮😊

---

[Beginner] 문자열을 정수로 바꾸기

[문자열을 정수로 바꾸기]

• …

Solution) $O(len(s))$

def solution(s):
    return int(s)

---

[Middler] JadenCase 문자열 만들기

[JadenCase 문자열 만들기]

• python에는 단어의 첫 글자를 대문자로, 나머지 글자를 소문자로 바꿔주는 capitalize() 가 있다.
• 바로 s.capitalize()할 경우 전체 string에서 첫 글자만 대문자로 바뀌기 때문에, 각 단어의 첫 글자를 대문자로 바꾸기 위해서는 문자열을 각 단어로 나누어서 각각 capitalize()를 적용해주어야 한다.
• 이 때 아름다운 내장함수가 있다. map() 을 이용하면 iterable의 각 요소에 대해 지정한 함수를 적용하여 map 객체를 반환한다.
• 여기서 주의해야 할 점은, 공백문자가 연속해서 나올 수 있다는 점이다. 따라서, 단순히 split()을 하면 틀리고, split(' ')을 해야 한다.
  • split() : 공백(하나 이상의 연속된 공백, \t, \n 등)을 기준으로 통째로 split한다.
  • split(' ') : 하나의 공백만으로 split한다.

Solution) $O(n)$

def solution(s):
    return ' '.join(map(lambda w: w.capitalize(), s.split(' ')))

---

[Challenger] 문자열 압축

[문자열 압축]

• 압축할 문자열의 단위를 하나씩 증가시키면서, 완전탐색으로 압축된 문자열의 길이의 최솟값을 갱신해나가면 된다.
  • 압축할 문자열의 단위는 전체 문자열 길이의 절반까지만 증가시켜보면 된다. 압축할 문자열의 단위가 전체 문자열 길이의 절반보다 클 땐 항상 압축될 수 없기 때문이다.
  • 물론 len(s)까지 돌려도 되지만, 이 방법으로 시간복잡도 계수 커팅이 가능하다.

• 압축된 문자열의 길이를 계산하는 과정에서, 마지막에 미처 계산되지 않은 남은 substring에 대해 마저 길이를 계산해준다.
  • 마지막 substring까지 압축되는 경우에 대해 생각해 보자.
    • 2 단위로 압축한다고 했을 때, ~~~abab 는 반복문이 종료될 때까지 cnt만 늘어났지 늘어난 cnt와 substring의 길이를 추가로 계산하지 않았다.
  • 마지막 substring이 압축되지 않는 경우에 대해 생각해 보자.
    • 3 단위로 압축한다고 했을 때, abcabcxyz 는 반복문이 종료될 때까지 이전 substring의 길이에 대해서만 계산해주고 반복문이 종료된다(마지막 substring의 길이가 계산되지 않았다).
    • 하지만, 반복문에서 압축된 문자열의 길이를 계산했던 것과는 다르게 마지막으로 슬라이싱된 cur의 길이는 token의 길이와 항상 일치하지 않다. 슬라이싱할 땐 인덱스의 범위를 벗어나도 오류가 나지 않고 유효한 부분에 대해서만 슬라이싱되기 때문에 cur = s[i:i+token]의 길이는 항상 일정하지 않기 때문에, 이 경우 len(cur)을 더해주어야 한다.

Solution) $O(n^2)$

def solution(s):
    min_len = len(s)
    
    for token in range(1, len(s)//2+1):
        prev = s[:token]
        cnt = 1
        cur_len = 0
        
        for i in range(token, len(s), token):
            cur = s[i:i+token]
            if prev == cur:
                cnt += 1
            else:
                cur_len += (len(str(cnt)) + token) if cnt>=2 else token
                prev = cur
                cnt = 1
        cur_len += (len(str(cnt)) + token) if cnt>=2 else len(cur)
        
        min_len = min(min_len, cur_len)
        
    return min_len

---