Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | |||
5 | 6 | 7 | 8 | 9 | 10 | 11 |
12 | 13 | 14 | 15 | 16 | 17 | 18 |
19 | 20 | 21 | 22 | 23 | 24 | 25 |
26 | 27 | 28 | 29 | 30 | 31 |
Tags
- 깊이 우선 탐색
- Lv. 0
- 프로그래머스
- C언어
- 동적계획법
- SQL
- Java
- Lv. 2
- 소프티어
- select
- level 3
- LEVEL 2
- 자바스크립트
- DP
- dfs
- programmers
- Python
- 파이썬
- softeer
- SQL 고득점 KIT
- join
- 너비 우선 탐색
- group by
- Lv. 3
- 티스토리챌린지
- Dynamic Programming
- Lv. 1
- javascript
- bfs
- 오블완
Archives
- Today
- Total
몸과 마음이 건전한 SW 개발자
프로그래머스 Lv2 문자열 압축 Python 본문
문제 링크
정답코드
def solution(s):
length = len(s)
if length == 1:
return 1
minLength = 1001
for l in range(1, length//2+1):
lString = ""
prevString = ""
cnt = 0
for idx in range(0, length, l):
string = ""
if idx+l > length:
string = s[idx:]
else:
string = s[idx:idx+l]
if string == prevString:
cnt += 1
else:
if cnt:
lString += str(cnt+1) + prevString
else:
lString += prevString
prevString = string
cnt = 0
if cnt:
lString += str(cnt+1) + prevString
else:
lString += prevString
lenString = len(lString)
if minLength > lenString:
minLength = lenString
answer = minLength
return answer
느낀점 & 풀이방법
사실 이정도 쉬운 문제까지 글을 써야 하나 싶었지만 뭔가 핵심이라고 할만한 부분을 찾아서 글을 적어본다. 예전이었으면 떠올리지 못했을 부분 for l in range(1, length//2+1). 글자 길이가 9인 문자열이 있다고 하자. 글자수 5로 압축한다고 하면 될까? 어림도 없다. 5 랑 4로는 압축할 수 없다. 4와 4 + 1로 압축은 가능하다. 따라서 2로 나눠서 시간복잡도를 낮췄다. 추가적으로 for idx in range(0, length, l) 이 부분도 연습하지 않으면 바로 떠오르지 않는다. 뇌가 굳어서 안 떠올랐다면 그냥 range(0, length)로 만들고 if로 인덱스값이 유효한지를 확인했을 것 같다.
'알고리즘' 카테고리의 다른 글
Softeer Level 3 징검다리 Python (4) | 2023.12.07 |
---|---|
프로그래머스 [Lv. 3] 불량 사용자 Python (0) | 2023.09.17 |
Softeer Level 3 비밀 메뉴 2 Python (0) | 2023.09.16 |
프로그래머스 [Lv. 2] 후보키 Python (0) | 2023.09.12 |
프로그래머스 Lv2 순위 검색 Python (2) | 2023.09.11 |