[알고리즘] 기사단원의 무기

// guidelines

1. Always include reasons for choosing certain approach/technology/framework/technique, etc.

2. Before writing a code, summarize the plan in 3 lines, including but not limited to:

- What data structures are we using?

- Time / Space complexity

- What are the edge cases?

 

3. Always leave reasons for failures to find patterns in mistakes. It is helpful in recognizing my weaknesses.

4. Don't cling to a problem that takes more than 30 minutes to solve. Check the answer first, and come back to days later.

  4-1. After you understood the answer, make it yours.

5. When you solved a problem without knowking how you did it, and it occurs repeatedly, it's time to take a step back and grind on one problem. 

Problem

숫자나라 기사단의 각 기사에게는 1번부터 number까지 번호가 지정되어 있습니다. 기사들은 무기점에서 무기를 구매하려고 합니다.
각 기사는 자신의 기사 번호의 약수 개수에 해당하는 공격력을 가진 무기를 구매하려 합니다. 단, 이웃나라와의 협약에 의해 공격력의 제한수치를 정하고, 제한수치보다 큰 공격력을 가진 무기를 구매해야 하는 기사는 협약기관에서 정한 공격력을 가지는 무기를 구매해야 합니다.
예를 들어, 15번으로 지정된 기사단원은 15의 약수가 1, 3, 5, 15로 4개 이므로, 공격력이 4인 무기를 구매합니다. 만약, 이웃나라와의 협약으로 정해진 공격력의 제한수치가 3이고 제한수치를 초과한 기사가 사용할 무기의 공격력이 2라면, 15번으로 지정된 기사단원은 무기점에서 공격력이 2인 무기를 구매합니다. 무기를 만들 때, 무기의 공격력 1당 1kg의 철이 필요합니다. 그래서 무기점에서 무기를 모두 만들기 위해 필요한 철의 무게를 미리 계산하려 합니다.
기사단원의 수를 나타내는 정수 number와 이웃나라와 협약으로 정해진 공격력의 제한수치를 나타내는 정수 limit와 제한수치를 초과한 기사가 사용할 무기의 공격력을 나타내는 정수 power가 주어졌을 때, 무기점의 주인이 무기를 모두 만들기 위해 필요한 철의 무게를 return 하는 solution 함수를 완성하시오.

제한사항
1 ≤ number ≤ 100,0002 ≤ limit ≤ 1001 ≤ power ≤ limit

나의 풀이

class Solution {
    public int solution(int number, int limit, int power) {
        int answer = 0;
        for (int i = 1; i <= number; i++) {
            answer += divisorCounterWithLimit(i, limit, power);
        }
        return answer;
    }

    private int divisorCounterWithLimit(int number, int limit, int power) {
        if (number == 1) return 1;
        int count = 2;
        for (int i = 2; i <= number / 2; i++) {
            if (number % i == 0) {
                count++;
            }
            if (count > limit) return power;
        }
        return count;
    }
}

---

핵심 아이디어

1과 자기 자신은 항상 약수이므로 count = 2로 초기화하고, 2부터 number/2까지만 순회하여 나머지 약수를 셉니다. 제한 초과 시 루프를 즉시 탈출하는 early return 전략을 사용해 불필요한 반복을 줄입니다.

---

Strengths:

가독성: divisorCounterWithLimit라는 이름이 "제한이 있는 약수 카운터"라는 의미를 명확히 전달합니다. 관심사 분리도 잘 되어 있습니다. 단일 책임 원칙을 의식한 구조입니다.

early return 최적화: count > limit이 되는 순간 바로 power를 반환하므로, 약수가 많은 수(예: 매우 작은 limit일 때)에서 루프를 일찍 끊는 효과가 있습니다. 이는 단순 완전탐색보다 실제 수행시간을 낮춰줍니다.

초기값 최적화: count = 2로 잡고 i = 2부터 number/2까지만 보는 방식은 1과 자기 자신을 반복 확인하는 낭비를 없앱니다.

---

Limitations (or Trade-offs):

가장 큰 약점 — 시간복잡도: 약수 탐색의 핵심 최적화인 √number까지만 순회를 사용하지 않았습니다. 현재는 number/2까지 순회하므로 각 숫자에 대해 O(n)이고, 전체는 O(n²) 수준입니다. 실제로 채점 결과에서 테스트 11, 12, 14, 15, 24, 25번이 5~6초대로 타임아웃 직전까지 간 것이 그 증거입니다. 제한 시간이 조금 더 짧았다면 탈락했을 수 있습니다.

√number를 사용하면 동일 로직을 O(n√n) 으로 줄일 수 있고, 체감 시간은 수십 배 차이납니다.

// √number 방식 예시
for (int i = 1; i * i <= number; i++) {
    if (number % i == 0) {
        count += (i == number / i) ? 1 : 2; // 완전제곱수 처리
    }
}

number == 1 하드코딩: count = 2로 시작하기 때문에 1의 약수가 2개로 계산되는 걸 막기 위한 분기입니다. 논리적으로는 맞지만, √number 방식으로 바꾸면 이 특수 케이스 없이도 자연스럽게 처리됩니다.

---

면접관 입장에서 궁금한 점

• "약수 탐색을 왜 number/2까지로 정했나요? √number까지만 보면 안 되는 이유가 있었나요?" 몰랐습니다, 할 말이 없네요.
• "테스트 11~16번이 5초 이상 나왔는데 인지하고 있었나요? 시간 제한이 더 빡빡했다면 어떻게 개선하겠습니까?" 인지하지 못했습니다. 빡빡했다면 약수의 개수를 계산하는 방식을 최적화시키는 방법을 고민했을 것이고, 그 과정에서 √number까지 탐색하는 방법을 떠올렸을 것입니다.
• "early return을 사용했는데, count > limit 체크를 루프 내부에서 하는 것과 루프 후 한 번에 하는 것의 차이를 설명해줄 수 있나요?" (→ worst case vs average case 트레이드오프) 루프 내부에서 체크가 이루어지는 경우 count가 limit를 초과한 시점에 바로 early return이 이루어지므로 평균 실행 시간을 단축시킬 수 있습니다. 하지만 이 효과는 number와 limit의 크기에 따라 달라집니다. Number의 크기가 커서 약수가 많은 숫자가 많은 경우, 또 limit의 크기가 작아 early return이 자주 발생하는 경우 average case가 크게 개선됩니다. 하지만 limit의 크기가 충분히 커서 early return이 드물게 발생하는 경우 worst case는 동일합니다.

---

사용한 자료구조

별도의 자료구조 없이 정수 변수(answer, count) 만 사용합니다. 공간을 거의 쓰지 않는 심플한 구조입니다.

---

시간 / 공간 복잡도

현재 풀이√n 최적화

시간	O(n²) — 각 i마다 i/2 순회	O(n√n)
공간	O(1)	O(1)

number = 100,000일 때 현재 풀이의 연산 횟수는 약 25억 회 (∑i/2 ≈ n²/4), √n 방식은 약 3,200만 회 수준으로 약 80배 차이가 납니다.

---

엣지케이스 처리 수준

케이스처리 여부

number == 1 (기사 1명)	✅ 명시적 return 1로 처리
약수 수 == limit (경계값)	✅ count > limit이므로 limit는 허용, 정확함
모든 기사가 제한 초과	✅ early return으로 전원 power 반환
power == limit	✅ 별도 처리 불필요, 연산에 영향 없음
완전제곱수 (√n이 정수인 수)	⚠️ 현재 방식에선 문제없으나, √n 방식으로 바꿀 때 i*i == number 처리를 빠뜨리기 쉬운 함정

---

종합 한 줄 평

정확성과 코드 구조는 좋으나, 약수 탐색의 핵심 최적화(√n)를 놓쳐 성능이 아슬아슬합니다. 실전 코테에서 number 상한이 높아지면 TLE(Time Limit Exceeded) 위험이 있으니, √n 패턴을 반드시 체화해두는 것을 추천합니다.

 

Lessons Learned

약수의 개수를 구할 때는 완전제곱수를 기억하자.
면접관의 질문에서 답변의 힌트를 얻고, 구체적인 조건과 케이스를 들어(average case, worst case) 답변하는 습관을 체화하는 것이 좋다.

 

My Github Repository for Solution Code

[level 1] Title: 기사단원의 무기, Time: 5947.04 ms, Memory: 79 MB -BaekjoonHub · ginsengcandy/Coding-Test-Practice@b77c3

 

Problem Source

프로그래머스