[241030 TIL] 가장짧은문자거리(시간복잡도)

문제 분석

문자열 s에서 각 문자에 대해 문자 t와의 최소 거리를 구하는 문제입니다. 문자열의 길이는 최대 100으로 제한되므로, O(n^2)의 알고리즘도 사용할 수 있습니다. 다만, 더 효율적인 방법을 찾을 수 있다면 좋습니다.

풀이법 1: 이중 루프 사용

const arr = str.split('');
let answer = [];

for (let i = 0; i < arr.length; i++) {
  let distance = [];
  for (let j = 0; j < arr.length; j++) {
    if (arr[j] === t) distance.push(Math.abs(j - i));
  }
  answer.push(Math.min(...distance));
}
return answer;

풀이 설명

1. 각 문자에 대해 t의 위치를 기준으로 모든 거리 차이를 구합니다.
2. Math.abs(j - i)를 사용해 각 t와의 거리를 배열 distance에 저장합니다.
3. distance 배열에서 최소값을 찾아 answer 배열에 추가합니다.

시간 복잡도

• 바깥쪽 루프(for i)는 n번 실행되고, 내부 루프(for j)도 n번 실행되므로, 총 시간복잡도는 O(n^2)입니다.

장단점

• 장점: 직관적으로 각 위치에서 모든 t와의 거리를 구할 수 있습니다.
• 단점: 이중 루프로 인해 불필요한 계산이 많아, 길이가 길어지면 비효율적입니다.

풀이법 2: 단일 패스와 역방향 패스 사용

let answer = [];
let p = 1000;

for (let x of str) {
  if (x === t) {
    p = 0;
    answer.push(p);
  } else {
    p++;
    answer.push(p);
  }
}

p = 1000;
for (let i = str.length - 1; i >= 0; i--) {
  if (str[i] === t) p = 0;
  else {
    p++;
    answer[i] = Math.min(answer[i], p);
  }
}
return answer;

풀이 설명

1. 첫 번째 루프에서는 왼쪽에서 오른쪽으로 이동하며 t를 만날 때마다 거리를 0으로 초기화하고, 그렇지 않으면 p를 1씩 증가시켜 t와의 거리를 기록합니다.
2. 두 번째 루프에서는 오른쪽에서 왼쪽으로 이동하면서 다시 t와의 거리를 계산해, 기존의 거리(answer[i])와 비교해 더 작은 값을 유지합니다.
3. 두 번의 단일 패스로 최종 answer에 각 위치에서의 최소 거리가 저장됩니다.

시간 복잡도

• 이 방법은 두 번의 단일 패스(O(n))로 해결되므로 시간 복잡도는 O(n)입니다.

장단점

• 장점: 이중 루프를 사용하지 않아 시간 효율이 좋습니다. 두 번의 단일 패스만으로 최소 거리를 구할 수 있어 문자열의 길이가 긴 경우에도 효율적입니다.
• 단점: 직관적이지 않을 수 있지만, 코드 구조는 간단한 편입니다.

결론

두 번째 풀이법이 효율적이고 빠릅니다. O(n)의 시간복잡도로 풀기 때문에 첫 번째 풀이보다 성능이 좋습니다. 따라서 풀이법 2를 사용하는 것이 이 문제를 해결하는 더 좋은 방법입니다.