log 2021-09-01

---

• sport
  • kakao 2021
    • 카드 짝 맞추기
  • kakao 2020
    • 문자열 압축

sport

kakao 2021

카드 짝 맞추기

hint

이미 있던 카드는 움직이지 않으므로, 맵 전체가 아니라 남은 카드의 각 위치를 상태로 사용할 수 있다. 그런데 dp를 적용하려면 어떻게 해야 할까? 또한, 현재 위치에 대한 정보도 필요하다.

남은 카드들의 상태는 좌표쌍의 집합이다. 좌표쌍의 집합 -> 다차원 인덱스로 매핑할 방법이 필요하다. dp[ s ] = f(s) = 상태 s로부터 시작하여 남은 최소 횟수 s = (2, 2), [{1, 2}, {3, 0}]

또 큰 문제가 있다. ctrl을 구현해야 하는데, 어떻게 구현해야할 지 모르겠다. 너무 노가다스러운데. 게다가 카드에 걸리는 것도 구현해야 하는데, 집합을 써서 기록하면 다른 아이템 확인이 안 된다.

결국 그러면 현재 맵의 상태는 저장하되, 백트래킹으로 구현해야 하나? 백트래킹과 dp가 같이 사용될 수 있나?

kakao 2020

문자열 압축

분명 잘 구현한 것 같은데 특정 케이스들을 틀려서 한참을 고민하다 찾아보니 다음 글에 해당하는 실수였다.

https://seoftware.tistory.com/115

뭐하러 굳이 다른 블로그들에서 진짜로 배열 쪼개고 만들고 하나 했는데 이래서 필요한 듯 싶다.

그렇지만 수정해서 원래 하려던 방법으로 결국 성공했다.

py solution

def solution(s):
    slen = len(s)
    best = slen
    for curb in range(1, slen + 1):
        saved = 0
        lastpat = ''
        curp = 0
        occ = 0
        while(curp + curb <= slen):
            pat = s[curp : curp + curb]
            if(pat == lastpat):
                saved += curb
                occ += 1
            else:
                lastpat = pat
                if(occ > 1):
                    saved -= len(str(occ))
                occ = 1
            curp += curb
            
        if(occ > 1):
            saved -= len(str(occ))
        res = slen - saved
        if(res < best):
            best = res
    return best

---