https://school.programmers.co.kr/learn/courses/30/lessons/60057
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
프로그래머스 - 문자열 압축 (60057번)
자료구조&알고리즘 : Exhaustive Search (완전 탐색)
난이도 : Lv 2
def solution(s):
miny = n = len(s)
for thr in range(1, (n>>1)+1):
acc = 0
std = s[:thr]
cnt = 1
for i in range(thr, n, thr):
if std == s[i:i+thr]:
cnt += 1
else:
acc += thr if cnt==1 else thr+len(str(cnt))
std = s[i:i+thr]
cnt = 1
acc += len(std) if cnt==1 else thr+len(str(cnt))
miny = min(miny, acc)
return miny
2020 KAKAO BLIND RECRUITMENT 기출문제이다.
완전 탐색을 통해, 가장 짧게 압축할 수 있는 문자열 길이를 찾는 문제이다.
문자열 s의 길이가 1000 이하라서, 완전 탐색으로 풀 수 있었다.
① 문자열을 자를 단위(thr)를, for 문을 통해 [1 ~ len(s)//2] 범위에서 하나씩 탐색한다.
② 각 thr에서, 문자열 s를 단위 길이(thr)만큼 잘라서 압축한 뒤의 길이를 확인한다.
중복 횟수(cnt)가 1이면, acc에 [ 단위 길이(thr) ] 를 더해주고
cnt가 1보다 크면, acc에 [ 단위 길이 + len(str(중복 횟수)) ] 를 더해준다.
그리고 acc와 miny 중, 더 작은 값으로 miny를 업데이트 한다.
③ 압축한 길이가 가장 짧았던 경우의 길이를 출력한다. (miny)
'Algorithm' 카테고리의 다른 글
징검다리 건너기 (64062번) - 프로그래머스 (Programmers) (0) | 2023.07.20 |
---|---|
사냥꾼 (8983번) - 백준 (BOJ) (0) | 2023.07.18 |
게임 개발 (1516번) - 백준 (BOJ) (0) | 2023.07.16 |
옥상 정원 꾸미기 (6198번) - 백준 (BOJ) (0) | 2023.07.14 |
블록 이동하기 (60063번) - 프로그래머스 (Programmers) (0) | 2023.07.13 |