[level 0] 약수 구하기 - 120897

문제 링크

성능 요약

메모리: 68.1 MB, 시간: 8.12 ms

구분

코딩테스트 연습 > 코딩테스트 입문

채점결과

정확성: 100.0
합계: 100.0 / 100.0

문제 설명

정수 n이 매개변수로 주어질 때, n의 약수를 오름차순으로 담은 배열을 return하도록 solution 함수를 완성해주세요.

---

제한사항

• 1 ≤ n ≤ 10,000

---

입출력 예

n	result
24	[1, 2, 3, 4, 6, 8, 12, 24]
29	[1, 29]

---

입출력 예 설명

입출력 예 #1

• 24의 약수를 오름차순으로 담은 배열 [1, 2, 3, 4, 6, 8, 12, 24]를 return합니다.

입출력 예 #2

• 29의 약수를 오름차순으로 담은 배열 [1, 29]를 return합니다.

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges

---

• 내 풀이

class Solution {
    public int[] solution(int n) {
        int sqrt = (int) Math.sqrt((double) n);
        List<Integer> list = new ArrayList<>();
        list.add(1);
        if (1 != n) {
            list.add(n);
        }
        int i = 2;
        while (i <= sqrt) {
            if (n % i == 0) {
                list.add(i);
                if (n / i != i) {
                    list.add(n/i);
                }
            }
            i++;
        }
        Collections.sort(list);
        int[] answer = list.stream()
                .mapToInt(Integer::intValue)
                .toArray();
        return answer;
    }
}

• TDD

class SolutionTest {

    @Test
    @DisplayName("n=24, [1, 2, 3, 4, 6, 8, 12, 24]")
    void solution() {
        int[] answer = {1, 2, 3, 4, 6, 8, 12, 24};
        Assertions.assertThat(new Solution().solution(24)).isEqualTo(answer);
    }

    @Test
    @DisplayName("n=29, [1, 29]")
    void solution2() {
        int[] answer = {1, 29};
        Assertions.assertThat(new Solution().solution(29)).isEqualTo(answer);
    }
}

---

• 풀이
  매겨변수로 주어진 N의 제곱근까지의 약수만 구하면 완전탐색으로 풀지않아도 된다.
  1은 모든 정수의 약수이기에 시작지점을 2로 주고 list에 1을 넣어준 상태로 시작.
  1과 짝을 이루는 자기 자신또한 먼저 넣어줌
  제곱근까지의 약수를 구해
  해당 약수로 매겨변수 N을 나눴을때의 값이 자기 자신이 아니라면 list에 추가해줬다
  자시 자신인 경우는 이러하다 25의 약수 5 는 25 / 5 == 5 나눈수와 몫이 동일하기 때문에
  중복으로 들어가는 경우를 제외하기위해서 자기 자신이 아니라는 조건을 추가해줬다.
  return 타입인 int[]형태로 파싱해주고 return