알고리즘
[알고리즘]프로그래머스 - 2018 KAKAO BLIND RECRUITMENT [3차] 압축
옝옹
2024. 10. 10. 19:17
문제 설명
제한사항
- 입력으로 영문 대문자로만 이뤄진 문자열 msg가 주어진다. msg의 길이는 1글자 이상, 1000글자 이하이다.
- 주어진 문자열을 압축한 후의 사전 색인 번호를 배열로 출력하라.
입출력 예
내가 푼 코드
function solution(msg) {
var answer = [];
const index = [];
for (let i = 0; i < 26; i++) {
index.push(String.fromCharCode(i + 65));
}
for (let i = 0; i < msg.length; i++) {
let [w, c] = [msg[i], msg[i + 1]];
while (index.includes(w)) {
let message = w + c;
if (index.includes(message)) {
w += c;
c = msg[++i + 1];
} else {
answer.push(index.indexOf(w) + 1);
index.push(w + c);
break;
}
}
}
return answer;
}
QnA
1. 알파벳 배열을 손쉽게 짤 수 있는 방법은 없는가?
기존 내 코드
const index = [];
for (let i = 0; i < 26; i++) {
index.push(String.fromCharCode(i + 65));
}
간결한 방법
const index = Array.from({ length: 26 }, (v, i) => String.fromCharCode(i + 65));
- 시간복잡도는 동일하나, 보기에 좀 더 간결하다.
- new Array() 는 빈 배열 또는 특정 길이의 배열을 만드는 데 사용되고
- Array.from() 은 매핑함수를 적용하는 옵션과 함께 반복 가능하거나 배열과 유사한 객체에서 배열을 만드는데 사용
내가 작성한 코드에서 좀 더 시간 복잡도 줄이는 방법은?
내가 작성한 코드의 시간 복잡도 : O(n(=msg.length) * m(동적으로 증가하는 index))
function solution(msg) {
let answer = [];
let dic = {};
for (let i = 0; i < 26; i++) {
dic[String.fromCharCode(i + 65)] = i + 1;
}
let currentWord = '';
let nextIndex = 27; // A-Z를 넘어서는 색인
for (let i = 0; i < msg.length; i++) {
currentWord += msg[i];
if (!(currentWord in dic)) {
answer.push(dic[currentWord.slice(0, -1)]); // 이전 단어의 색인을 결과에 추가
dic[currentWord] = nextIndex++; // 새 단어를 사전에 추가
currentWord = msg[i]; // currentWord 초기화
}
}
if (currentWord) answer.push(dic[currentWord]);
return answer;
}
- 해시 맵에서의 검색/추가는 평균적으로 O(1)임을 이용한 코드
- 시간 복잡도 O(n)