https://programmers.co.kr/learn/courses/30/lessons/12940

소스

1
2
3
4
5
6
7
8
9
10
11
12

public int[] solution(int n, int m) {
    int big = n > m ? n : m;
    int small = n < m ? n : m;
    
    while (m != 0) {
        int r = n % m;
        n = m;
        m = r;
    }
    
    return new int[] {n, n * (big / n) * (small / n)};
}

흐름

• 유클리드 호제법으로 처리

  두 양의 정수 $$ a, b (a > b) $$ 에 대하여 $$ a = bq + r(0 ≤ r < a) $$
  라 하면, a, b 의 최대공약수는 b, r의 최대공약수와 같다.

1. 두 수를 중 큰 수와 작은 수 구분

2. 큰 수 a의 최대공약수는 b와 r(a mod b)의 최대 공약수와 같으므로 작은 수 m이 0이 될 때 까지 반복

3. 최소공배수는 최대공약수(G) * (a / G) * (m / G) 이므로 계산해서 배열에 할당한다.

   • $$ (a * b) / G $$ 로 하면 수가 큰 경우 overflow가 발생 할 가능성이 있음.

4. 끝

유클리드 호제법

두 양의 정수 $$ A, B (A > B) $$ 에 대하여 $$ A = Bq + R(0 ≤ R < a) $$
라 하면, A, B 의 최대공약수는 B, R의 최대공약수와 같다.

이 때 R은 A mod B 한 값으로 식으로 나타내면 아래와 같다.

$$ G(A,B) = G(B,R) $$

A와 B에게 최대공약수 G가 있다면,

$$ A = aG, B = bG $$

과 같이 나타 낼수 있고 이 때 a와 b는 반드시 서로소 여야 한다.
위에서 A mod B 한 값이 R 이라고 정의했고 A와 B를 나눈 값을 q라고 한다면,

$$ A = Bq + R $$
$$ aG = bGq + R $$
$$ R = G(a-bq) $$

처럼 전개 될 수 있고, 이 경우 R과 B가 G 라는 최대 공약수를 갖기 떄문에 $$ a-bq $$ 와 b가 서로소 임을 증명하면 된다.

만약 $$ a-bq $$ 와 b가 서로소가 아니라면, 둘은 공약수가 존재 하기 떄문에 아래와 같이 표현 할 수 있다.

$$ a-bq = pm , b = pn $$
$$ a = bq + pm $$
$$ a = pnq + pm $$
$$ a = p(nq + m), b = pn $$

이 때 a와 b는 서로소인데 p 라는 공약수를 갖게 되므로
a와 b가 서로소라는 전제가 모순되어 $$ a-bq $$ 와 b는 서로소임이 증명되고 B와 R의 최대 공약수가 G 인 것이 된다.

참고 사이트

• https://sexycoder.tistory.com/65

• https://blog.naver.com/PostView.nhn?blogId=papers&logNo=140207307545&proxyReferer=https%3A%2F%2Fwww.google.com%2F

• https://namu.wiki/w/%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C%20%ED%98%B8%EC%A0%9C%EB%B2%95

댓글 공유

https://programmers.co.kr/learn/courses/30/lessons/12932

소스

1
2
3
4
5
6
7
8
9

public int[] solution(long n) {
    List<Long> list = new ArrayList<Long>();
    while (n > 0) {
        list.add(n % 10);
        n /= 10;
    }

    return list.stream().mapToInt(i -> (int) (long) i).toArray();
}

흐름

1. n은 10,000,000,000이하인 자연수이므로 몇 자리의 수가 올지 알 수 없으므로 배열이 아닌 ArrayList를 생성
2. n mode 10한 값을 저장하고 n을 10 나눔
   • ex) 12345 mod 10 = 5, 12345 / 10 = 1234
3. List를 stream()을 활용하여 int array로 변경함

다른 풀이

1
2
3
4
5
6
7
8
9
10

public int[] solution(long n) {
    int[] arrays = new int[String.valueOf(n).length()];
    int i = 0;
    while (n > 0) {
        arrays[i++] = (int) (n % 10);
        n /= 10;
    }

    return arrays;
}

1. n이 몇 자리의 수가 올지 알 수 없으므로 n을 String으로 변환 후 String의 length를 구해서 array의 크기를 구함
2. 이하 상동

시간 비교

첫 번째 풀이

두 번째 풀이

• Stream()이 생각보다 더 느리게 동작하는 듯 싶다.

댓글 공유

문제

https://programmers.co.kr/learn/courses/30/lessons/12921

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

public int solution(int n) {
    boolean[] prime = new boolean[n+1];

    prime[0] = true;
    prime[1] = true;

    for (int i = 2; (i * i) <= n; i++) {
        if (!prime[i]) {
            for (int j = i * 2; j <= n; j += i) {
                prime[j] = true;
            }
        }
    }

    int answer = 0;
    for (boolean is : prime) {
        if (!is) {
            answer++;
        }
    }

    return answer;
}

흐름

• 에라토스테네스의 체로 해결

1. n까지의 숫자중 0과 1은 소수가 아니므로 true 할당
2. 2부터 루트n 까지 반복하면서 배수들에 true 할당
3. 소수 판별한 배열 prime을 loop 돌면서 false 인 경우에만 갯수 추가
4. 끝

부연 설명

1

for (int i = 2; (i * i) <= n; i++)

입력받은 수 n이 합성수 인 경우 $$n = a * b​$$ 로 나타낼 수 있다.
이 때 a와 b 중 큰거나 같은 수를 a, 작거나 같은 수를 b라고 가정하면 b가 a보다 작으므로 $$ a * a >= a * b $$ 이고
$$ n = a * b $$ 이므로, 큰 수 a의 제곱일 경우 $$ a^2>=n $$ 처럼 된다.
이를 치환하면 $$ a>=\sqrt{n} $$ 이 되므로 a의 최솟값은 $$ \sqrt{n} $$ 이 된다.
그리고 b는 $$ a >= b $$이므로 b의 최댓값은 $$ \sqrt{n} $$ 이 된다.
고로 n이 소수가 아닌 합성수라면 a의 와 b의 합성수로 이루어 짐을 알 수 있으므로, $$ \sqrt{n} $$ 까지만 반복하면 소수임을 판별할 수 있다.

• ex) 입력받은 수 n이 50일 경우 $$ \sqrt{50} $$ = 7.071067811865475‬‬….이므로, 7.071067811865475‬‬… 을 기준으로 50의 약수 {1,2,5,10,25,50}을 나누면 b = {1, 2, 5}, a = {10, 25, 50} 이므로 b만 검사하면 50이 소수 인지 아닌지 알 수 있다.

1

for (int j = i * 2; j <= n; j += i)

원래는 i보다 작은 수인 경우 이미 이전에 작은 수 * i에서 삭제된 상태이므로 i * i인 게 맞으나,
i의 값이 너무 클 경우 문제가 될 수 있으므로 $$ i * 2 $$ 로 설정한다.
물론 이 문제에선 100만 까지로 한정되어 있으므로 $$ i * i $$ 를 해도 문제는 없다.

참고 사이트

• https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4
• https://blog.naver.com/loveshurt/221774410486
• https://makedotworld.tistory.com/13

댓글 공유