인프런 커뮤니티 질문&답변
작성한 질문수
코드의 시간 복잡도에 대해 궁금합니다!
작성
·
235
0
function solution(str, t) {
let answer;
const counts = {};
const formatted = [...str];
formatted.forEach((char, i) => {
if (counts[char]) {
return counts[char].push(i);
}
counts[char] = [];
counts[char].push(i);
});
const tIndexs = counts[t];
answer = formatted.reduce((store, cur, i) => {
const tmp = [];
tIndexs.forEach((index) => {
tmp.push(Math.abs(index - i));
});
store.push(Math.min(...tmp));
return store;
}, []);
return answer.join(' ');
}
let str = 'teachermode';
console.log(solution(str, 'e'));
입력값의 크기 N마다 tIndex만큼 반복하니까 O(N^2) 인지
아니면 O(N)의 시간복잡도를 갖는지 궁금합니다.
답변 1
0
안녕하세요, 인프런 AI 인턴입니다.
DevLuna님, 주신 코드의 시간 복잡도에 대해 질문해주셨군요.
우선 주어진 코드를 분석하면 formatted.forEach와 내부의 tIndexs.forEach로 인해 2중 반복 구조를 갖고 있습니다. 여기서 formatted는 입력 문자열 str을 배열로 변환한 것이고, tIndexs는 문자열 str 내에 있는 문자 t의 인덱스를 모아둔 배열입니다.
시간 복잡도를 계산할 때 핵심은 입력 크기 N에 대해 연산이 얼마나 많이 발생하는지를 봐야 합니다. formatted.forEach는 입력 문자열 길이인 N에 비례하여 한 번 실행되며, 내부의 tIndexs.forEach는 문자 t의 발생 빈도에 비례하여 실행됩니다. 문자 t의 발생 빈도가 최악의 경우 입력 문자열 길이인 N에 비례할 수 있기 때문에, 최악의 경우 이 코드는 O(N^2)의 시간 복잡도를 가집니다. 하지만 평균적인 경우나 문자 t의 발생 빈도가 고정된 상수라고 가정할 때는 O(N)에 가깝게 작동할 수도 있습니다.
정확한 시간 복잡도는 문자 t의 발생 빈도에 따라 달라질 수 있으므로 코드를 실행하는 입력값의 특성을 고려해야 합니다.