일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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
- 리트코드
- LeetCode
- codestates
- js
- 리덕스
- 4주 프로젝트
- javascript
- 타입스크립트 올인원
- 프로그래머스
- 리액트
- 백준
- 정재남
- 제로초
- python
- til
- 타입스크립트
- 2주 프로젝트
- 코드스테이츠
- 회고
- 손에 익히며 배우는 네트워크 첫걸음
- 알고리즘
- 자바스크립트
- Async
- 타임어택
- SQL 고득점 Kit
- 코어 자바스크립트
- 파이썬
- 토익
- 렛츠기릿 자바스크립트
- programmers
Archives
- Today
- Total
Jerry
[프로그래머스 / 자바스크립트]문자열 압축 본문
반응형
혹시 틀린 점이나 의견주시고 싶으시면 편하게 말씀해주시면 감사하겠습니다 😀
문제
- 문자열 압축(비손실 압축): 연속된 값의 문자의 개수를 반복되는 값으로 표현
조건
- 1은 생략
- 문자열을 1개 이상의 단위로 잘라서 압축
- 이 중 가장 짧은 문자열의 길이를 반환
- 1개 이상 단위 to 주어지는 문자열의 길이 / 2의 범위를 가진다.
//! first try
function solution(s) {
let arrForLen = [];
let arrForEachUnit = [];
while (1) {
let strLen = 1;
let cnt = 0;
let tempStr = "";
for (let q = 0; q < s.length; q += 1) {
for (let t = 0; t < s.length; t += strLen) {
if (s[t] !== s[t + 1]) {
// cnt++;
if (cnt === 1) {
tempStr += s.slice(t, t + 1);
} else {
tempStr += cnt + s.slice(t, t + 1);
}
arrForLen.push(tempStr.length);
cnt = 0;
tempStr = "";
} else {
if (s.slice(q, t + 1)) {
cnt++;
}
}
}
strLen++;
arrForEachUnit.push(arrForLen.join(""));
}
if (strLen > s.length / 2) break;
}
console.log(arrForLen);
}
첫 시도는 1단위로 압축까지는 구현을 할 수 있지만, 2 단위부터 어떻게 비교를 해야 할지 방법이 잘 떠오르지 않았다.
slice를 이용해서 단위별로 나뉜 문자를 비교를 해줘야겠다고 생각을 했지만, for문이 순회하면서 덩달아 같이 문자열을 알맞게 잘라줘야 되는지 아이디어가 떠오르지 않았다.
정해진 시간이 종료되고 구글링을 통해, 그에 관한 힌트를 얻어 적용해 보았다!
적용한 코드는 아래에 있다.
//! submit code
function solution(s) {
let arrForLen = [];
for (let q = 0; q < s.length; q += 1) {
let strLen = q + 1;
let cnt = 1;
let tempStr = "";
for (let t = 0; t < s.length; t += strLen) {
let currentStr = s.substring(t, t + strLen);
let nextToCurrentStr = s.substring(t + strLen, t + strLen + strLen);
if (currentStr === nextToCurrentStr) cnt++;
else {
if (cnt !== 1) {
tempStr += cnt + currentStr;
} else {
tempStr += currentStr;
}
cnt = 1;
}
}
arrForLen.push(tempStr.length);
if (strLen > s.length / 2) break;
}
return Math.min(...arrForLen);
}
currentStr와 nextToCurrentStr 서로 비교할 변수를 만든 후, substring을 이용해 초기화 및 할당을 해주었다.
다음, 두 변수를 비교를 조건으로 두어서 문제를 풀었다.
시간복잡도는 O(n^2)이다!
반응형
'Problem Solving > Algorithm 문제 풀기' 카테고리의 다른 글
프로그래머스 자바스크립트 - 스킬트리 (0) | 2021.06.15 |
---|---|
프로그래머스 자바스크립트 - 3진법 뒤집기 (0) | 2021.06.13 |
[Programmers] 완주하지 못한 선수 (JavaScript) (0) | 2020.12.20 |
[HackerRank] Compare the Triplets.js (JavaScript) (0) | 2020.11.09 |
[HackerRank] Compare the Triplets (JavaScript) (0) | 2020.11.08 |