8.md

가장 가까운 같은 글자

다양한 풀이에 대해서 알아보자!

1. 해쉬 + for문

function solution(s) {
  const result = [];
  const map = {};
  for (let i = 0; i < s.length; i++) {
    map[s[i]] === undefined ? result.push(-1) : result.push(i - map[s[i]]);
    map[s[i]] = i;
  }

  return result;
}

• 나의 풀이 : 나의 습관적인 부분인것 같은데, 코테 문제를 풀 때는 for문을 많이 사용한다. 🤔 효율적인 부분에선 좋은 경우가 많지만 일반적으로 가독성은 떨어진다. 그리고 처음에 접근해서 막 풀기(?) 좋은 면도 있다.

2. 해쉬 + 내장함수 이용

function solution(s) {
  const map = {};

  return [...s].map((char, index) => {
    const result = map[char] === undefined ? -1 : index - map[char];
    map[char] = index;
    return result;
  });
}

• 내 코드보다 가독성이 많이 개선된 느낌이다. 👍🏻

• 개인적으로 전개연산자 + map 을 통해서 로직이 배열에서 시작해서 배열로 끝나는게 포인트라고 생각한다.

3. 내장함수 이용

function solution(s) {
  return [...s].map((char, i) => {
    const finded = s.slice(0, i).lastIndexOf(char);
    return finded > -1 ? i - finded : finded;
  });
}

• slice와 lastIndexOf의 조화. 사실 최초로 생각한 방법인데, lastIndexOf의 존재를 생각해내지 못해서 로직을 변경한 케이스.

• map 안에서 indexOf, lastIndexOf를 사용하는 것이 사실상 내부적으로는 이중for문과 같은 개념이라고 알고 있다. slice도 마찬가지. 하지만 이렇게 풀어도 가능한지 여부는 제한 조건을 살펴보면 된다.

  1 ≤ s의 길이 ≤ 10,000
  

  일반적으로 1초에 연산이 모두 이루어져야함을 가정하면(코테는 1 ~ 5초 사이), 연산이 10억(부정확한 정보였음을 확인)이 아니라 1억을 넘어가면 오답 판정을 받을 수 있다. 위 문제의 시간복잡도는 O(N^2)이기 때문에 최악을 가정하면, 10000 * 10000 = 100000000(1억)번의 연산 횟수를 해야한다고 예상할 수 있다. 이 수치는 연산이 가능한 수치로 판단되어 아무런 오류 없이 통과된 것으로 보인다. (정확하지는 않지만, 그럼에도 연산에 문제가 없었던 이유는 내부적으로 빌트인 메소드에서의 최적화가 진행되어서 그런 것이 아닌가 싶다...🤔)

  그래서 일반적으로 제한조건에 따라서 어떤 시간복잡도를 갖도록 구현할지를 가늠해볼 수 있다. 제한 조건에 따라서 아래 예시처럼 시간복잡도 설계할 수 있다고 한다.

  • 0 < n <= 500 : O(N^3)

  • 0 < n <= 2000 : O(N^2)

  • 0 < n <= 100,000 : O(NlogN)

  • 0 < n <= 10,000,000() : O(N)

    만약엔 N이 최대치가 100,000인 경우에 O(N^2)의 시간복잡도를 갖게 로직을 구현한다면 테스트 케이스를 통과하지 못할 것이다.

결론

문제 자체는 어렵지 않았지만, 여러 가지 관점에서 생각해볼 것들이 많은 문제였다. 그리고 for문 뿐만 아니라 내장함수를 이용하는 방법으로도 접근해보도록 하자!

시간복잡도에 대한 것은 아마도 레벨2부터는 고려해서 문제를 풀어야하지 않을까 싶다. 레벨2부터는 제한조건이 좀 더 빡빡해질듯... 😶‍🌫️