[색인 찾기] 압축

[ericagong]

⭐ 성찰

1. 문자열 자를 때, String.prototype.slice(beginIdx, endIdx)사용 ⭐ 이는Array.prototype.slice(start, end)와 유사 ⭐String.prototype.substr(start[, length])은 deprecated 되었으므로 사용 비추(https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/String/substr) ⭐ **String.prototype.substring(indexStart[, indexEnd]),String.prototype.slice(beginIndex[, endIndex])`는 모두 원본 문자열 변환 없이**, [startIdx, endIdx)인 신규 문자열을 반환한다는 점에서 동일하므로 원하는 것 사용
2. for문의 맨 뒤에서부터 찾을 때, 인덱스 잘 확인하기
3. 효율적인 검색을 위해 검색 범위를 어떻게 줄일 수 있을까 고민하기 -> 별도의 max_length 두어 딕셔너리 내 최장 key 길이 확인

❓ 문제 상황

압축

👨‍💻 문제 해결: 풀이 방식

✅ 1차 풀이: 문자열 뒤에서부터 확인하기

1. 주어진 문자열을 맨 뒤에서부터 하나씩 줄이며 사전(map)내 포함 여부 확인하며 w 찾기 ⭐ 이 때, 효율적으로 확인하기 위해 매번 문자열 길이만큼이 아니라 사전 내 key 중 가장 길이가 긴 것만큼을 최장 길이로 설정해 확인하기 ⭐
2. 존재 시 w 입력에서 없애기
3. 입력에 남은 글자 있는 경우, w+c 사전에 추가하기
4. 1-3 과정을 입력이 남아있는 동안 계속 반복

function solution(msg) { let result = [];

let dict = new Map();

// 뒤에서부터 효율적으로 인덱스 찾기 위해, dict의 key 중 가장 긴 길이 별도로 저장 let max_len = 1; let indexes = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"; for (let i = 0; i < indexes.length; i++) { dict.set(indexes[i], i + 1); }

while (msg.length > 0) { let w = "";

// w 찾기
for (let i = max_len; i > 0; i--) {
  w = msg.slice(0, i);
  if (dict.has(w)) {
    //  w에 해당하는 색인 번호 출력
    result.push(dict.get(w));
    break;
  }
}

// 입력에서 w 제거
msg = msg.slice(w.length);

// wc 사전 추가
if (msg.length !== 0) {
  let key = w + msg[0];
  dict.set(key, dict.size + 1);

  max_len = Math.max(max_len, key.length); // 최장 길이 반영
}

}

return result; }

### ✅ 2차 풀이: 빌트인 함수 활용
- Array.prototype.slice(startIdx, endIdx: endIdx 미제공시 문자열 끝까지 자름
- Map 초기값 빠르게 설정하기 위해, for문으로 key 순회 
- 
```js
function solution(msg) {
  const dict = new Map();
  let index = 1;
  for (alpha of "ABCDEFGHIJKLMNOPQRSTUVWXYZ") {
    dict.set(alpha, index);
    index += 1;
  }

  const answer = [];
  while (msg) {
    let w;
    for (let i = msg.length; i > 0; i--) {
      w = msg.slice(0, i);
      if (dict.has(w)) {
        break;
      }
    }
    answer.push(dict.get(w));
    msg = msg.slice(w.length);
    const c = msg[0];
    if (c !== "") {
        dict.set(w + c, dict.size + 1);
    }
  }

  return answer;
}