[프로그래머스 | Lv. 1 | JavaScript] 문자열 내 p와 y의 개수

 

Link

코딩테스트 연습 - 문자열 내 p와 y의 개수

 

---

문제

풀이

(1)

function solution(s){
    let answer = true;
    let lower = s.toLowerCase();
    
    let pCnt = 0;
    let yCnt = 0;
    for (let c of lower) {
        if (c === 'p') pCnt += 1;
        else if (c === 'y') yCnt += 1;
    }

    return pCnt === yCnt;
}

(2)

function solution(s) {
    const lower = s.toLowerCase();
    return lower.split('p').length === lower.split('y').length;
}

 

주의점

(1)의 풀이가 (2)보다 느림

두 풀이 모두 복잡도가 O(n)이겠지만, (2) 풀이의 실행 시간이 더 느릴 것이라고 생각했다. 하지만 실제 결과는 달랐다.

왼: (1) 풀이, 오: (2) 풀이

주요 원인 (ChatGPT 분석)

• for...of의 내부 동작 방식
  • for...of는 이터레이터(Iterator) 를 사용해 문자열을 순회합니다.
  • 문자열을 이터러블(iterable) 객체로 변환해 하나씩 값을 추출하는 방식이기 때문에, 루프의 각 단계에서 추가적인 오버헤드가 발생합니다.
   

for (let c of s) {
    // 이터레이터가 값을 추출하고 반환
}

• split의 성능 최적화
  • split() 메서드는 C++ 레벨에서 최적화되어 있어 매우 빠르게 동작합니다.
  • split()은 내부적으로 빠른 메모리 복사와 비트 연산을 사용하여 문자열을 효율적으로 나눕니다.
  • 따라서 실제로는 split을 두 번 호출해도, for...of보다 빠르게 동작하는 경우가 많습니다.

결론

• 실제 성능에서는 split 방식이 for...of 방식보다 빠르게 동작할 수 있습니다.
• 이는 JavaScript 엔진이 split과 같은 메서드를 더 깊이 최적화하기 때문입니다.
• 반면 for...of는 동적 이터레이터 오버헤드가 존재하여 상대적으로 느릴 수 있습니다.
• 다만, 공간 복잡도는 첫 번째 코드가 O(1) 로 효율적이며, 두 번째 코드는 O(n) 만큼 추가 메모리를 사용합니다.