[프로그래머스/Day 4] 문자, 문자열, 내적, 제곱수 판별 최적화

1. 문자 '0'과 ASCII 값

• 문자 '0'의 ASCII 값은 48
• 숫자 문자 → 정수 변환 공식
• int num = ch - '0';
• '7' - '0' == 7 처럼 동작

---

2. string.substr() 사용법

string.substr(startIndex, count);

• startIndex부터 count개 문자 추출
• 문자열 파싱, 부분 문자열 처리에 필수

---

3. 벡터 내적(Dot Product)

• 정의: a·b = a[0]*b[0] + a[1]*b[1] + ... + a[n-1]*b[n-1]
• 두 벡터 길이는 같아야 함
• 선형대수, 게임/그래픽, 물리 계산에서 자주 사용

---

4. 약수 개수 & 제곱수 핵심 아이디어

• 대부분의 수는 약수 개수가 짝수
• 제곱수만 약수 개수가 홀수
  • 이유: sqrt(n)이 자기 자신과 짝이 안 맞음
• 약수 직접 세기 ❌
  → 제곱수 판별만 하면 됨 ✅

---

5. 시간복잡도 개선 (O(N))

기존 방식:

#include <string>
#include <vector>

using namespace std;

// 1. left부터 right까지 반복문을 실행한다.
// 2. 약수의 개수를 구한다.
// 3-1. 약수의 개수가 짝수일 경우, 결과에 수를 더한다.
// 3-2. 약수의 개수가 홀수일 경우, 결과에 수를 뺀다.
int solution(int left, int right) {
    int answer = 0;

    for(int number = left; number  <= right; ++number)
    {
        vector<int>* vec = new vector<int>();
        for(int d = 1; d * d <= number; ++d)
        {
            if(number % d) continue;

            int q = number / d;
            vec->push_back(d);

            if (q != d) vec->push_back(q);
        }

        if (vec->size() % 2 == 0)
        {
            answer += number;
        } else {
            answer -= number;
        }

        delete vec;
        vec = nullptr;
    }

    return answer;
}

개선 방식:

#include <cmath>

int solution(int left, int right) {
    int answer = 0;

    for (int n = left; n <= right; ++n) {
        int r = (int)std::sqrt(n);
        bool isSquare = (r * r == n);
        answer += isSquare ? -n : n;
    }
    return answer;
}

• 핵심 포인트
  • sqrt(n) 결과를 다시 제곱해서 비교
  • 제곱수 → 빼기
  • 일반 수 → 더하기
• 불필요한 약수 탐색 제거
• 공간복잡도 O(1)

---

6. 정리 한 줄

문제를 수학적으로 재해석하면, 반복문은 줄고 코드는 단순해진다.