[알고리즘] 대충 만든 자판

1. 조건

keymap, target의 길이와 그 원소들의 길이 1 ~ 100

경우1: 자판 전체에 같은 문자 여러 번 할당

경우2: 키 하나에 같은 문자 여러 번 할당

경우3: 아예 할당 되지 않은 경우

특정 문자열 작성할 떄 최소 몇 번 눌러야 가능한지 구하기

 

2. 풀이 과정

좀 오래동안 문제를 쳐다봐쓴ㄴ데 어떤 알고리즘을 활용해서 풀이해야할지 도무지 떠오르지 않았다.

그래서 그냥 무지성 코딩을 갈겼다

사실 내가 생각한대로면 최악의 경우를 생각해보면...

100*100*100*100이니까.. 100,000,000이 나온다 ㅋㅋㅋㅋㅋ!!!!!

시간 초과 날것을 예상하고 시간초과가 나면 조금씩 개선해보자는 생각으로...

 

3. 풀이

function solution(keymap, targets) {
  const answer = [];

  const getLowerIndex = (target) => {
    let lowerIndex = -1;

    for (let idx = 0; idx < keymap.length; idx += 1) {
      const index = keymap[idx].indexOf(target);

      if (index === -1) continue;
      if (lowerIndex === -1) lowerIndex = index;
      if (index < lowerIndex) lowerIndex = index;
    }

    return lowerIndex;
  };

  for (let i = 0; i < targets.length; i += 1) {
    const target = targets[i];
    let temp = 0;

    for (let j = 0; j < target.length; j += 1) {
      const index = getLowerIndex(target[j]);

      if (index === -1) {
        answer.push(-1);
        break;
      }

      temp += index + 1;

      if (j >= target.length - 1) {
        answer.push(temp);
        temp = 0;
        break;
      }
    }
  }

  return answer;
}

진짜 똥을 싸질러 놨네...

 

신기하게 시간초과가 나지않았다.

근데 코드가 진짜 개쓰레기였다.

 

더 스마트한 방법이 없었을까...