[JS] indexOf 시간복잡도

1. 서론

백준 1620번 풀다가 아무생각 없이 indexOf 썼는데.. 시간초과로 실패가 계속 떴다.

원래 코드

const [count, solutionCount] = input[0].split(" ").map(Number);

for (let i = count + 1; i <= count + solutionCount; i++) {
  if (/[0-9]/.test(input[i])) {
   console.log(input[Number(input[i])]);
  } else {
    console.log(input.indexOf(input[i]));
  }
}

전체를 감싸는 for문 시간 복잡도만 생각해서 O(n) 이라고 생각했었는데, indexOf 메서드의 시간 복잡도도 O(n)이라 사실상 O(n^2) 이였다.

2. indexOf의 시간복잡도?

https://developer.mozilla.org/ko/docs/Web/JavaScript/Reference/Global_Objects/Array/indexOf#매개변수

indexOf()는 인자로 fromIndex를 받았을 경우에 해당 인덱스부터 탐색을 시작해서 해당 값을 return 해준다.
하지만, fromIndex를 받지 않았을 경우에는 0번 인덱스부터 순차적으로 탐색을 시작하며 찾을 경우 해당 값을 return 해준다.
따라서 indexOf의 시간복잡도는 O(n)이다.

3. 결론

결국 저 문제는 indexOf를 활용해서 풀 순 없고, 맵 사용해서 해결했다.

const [count, solutionCount] = input[0].split(" ").map(Number);

const nameToNum = new Map();
const numToName = new Map();

for (let i = 1; i <= count; i++) {
  nameToNum.set(input[i], i);
  numToName.set(i, input[i]);
}

for (let i = count + 1; i <= count + solutionCount; i++) {
  if (/[0-9]/.test(input[i])) {
    console.log(numToName.get(Number(input[i])));
  } else {
    console.log(nameToNum.get(input[i]));
  }
}

N개의 원소가 있는 맵의 값에 접근을 하기 위한 시간 복잡도는 O(1)이다.
위의 코드는 시간복잡도가 O(n)이 되기 때문에 시간 초과가 발생하지 않는다.