문제

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

소스

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

public int[] solution(int N, int[] stages) {
    int[] failUsers = new int[N+2];
    for (int stage : stages) {
        failUsers[stage] += 1;
    }

    Map<Integer, Double> map = new HashMap<Integer, Double>();
    double userCount = stages.length;
    for (int i = 1; i <= N; i++) {
        double value = 0.0;
        if (failUsers[i] != 0 && userCount != 0) {
            value = (failUsers[i] / userCount) * 100;
            userCount -= failUsers[i];
        }
        map.put(i, value);
    }

    List<Integer> list = new ArrayList<Integer>(map.keySet());
    Collections.sort(list, new Comparator<Integer>() {

        @Override
        public int compare(Integer o1, Integer o2) {
            return map.get(o2).compareTo(map.get(o1));
        }
    });

    int[] answer = list.stream().mapToInt(i -> i).toArray();
    return answer;
}

흐름

1. 유저 수(stages.length) 만큼 loop 돌면서 각 stage 별로 실패한 유저 수를 array에 저장한다.
2. 스테이지별로 틀린 인원 수를 저장히기 위한 Map 변수를 하나 생성하고,
3. 스테이지 수(N) 만큼 loop 돌면서 해당 스테이지에 실패한 사람이 있으면서, 전체 시도한 사람이 0명이 아닌 경우,
4. $$ 해당 스테이지에서 실패한 유저 수 / 해당 스테이지에 도전한 유저 수 * 100 $$ 해서 해당 스테이지의 실패율을 구한다.
   • 이 때 스테이지에 도전한 유저 수는 이전 스테이지를 성공한 사람들 만이다.
5. 이번 스테이지에서 실패한 유저들은 다음 스테이지에 도전 할 수 없으므로, 총 유저 수에서 실패한 유저 수를 제한다.
6. 위에서 선언한 Map 변수에 key를 스테이지 번호로, value를 실패율로 하여 put 한다.
7. 실패율을 저장한 Map을 Value 기준으로 내림차순 정렬을 한다.
8. ArrayList를 int[]로 변환한다.
   • stream에 경우 속도가 느리므로, loop를 돌면서 직접 int[]로 만드는 방법이 퍼포먼스에 더 이로울 듯 하다.
9. 끝

결과

테스트 케이스

1
2
3
4
5
6

assertArrayEquals(new int[] {3,4,2,1,5}, test.solution(5, new int[] {2, 1, 2, 6, 2, 4, 3, 3}));
assertArrayEquals(new int[] {4,1,2,3}, test.solution(4, new int[] {4,4,4,4,4}));
assertArrayEquals(new int[] {2,1,3,4}, test.solution(4, new int[] {1,1,1,1,2}));
assertArrayEquals(new int[] {4,2,3,1}, test.solution(4, new int[] {3,2,5,4,2}));
assertArrayEquals(new int[] {7,6,2,3,5,4,1}, test.solution(7, new int[] {2, 1, 2, 6, 2, 4, 3, 3,7,5}));
assertArrayEquals(new int[] {1,2,3,4,5}, test.solution(5, new int[] {}));

• Junit5로 테스트 했음.

• 프로그래머스에서 제공하는 모든 케이스에 대한 것이 아니라,
  필자가 마음대로 넣은 것 이므로 이 소스를 통과하여도 프로그래머스에선 통과되지 못할 수 있음.

다른 멋진 분들의 해결방법

• https://velog.io/@dion/programmers-42889-algorithm-solution
• https://jayrightthere.tistory.com/entry/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EC%8B%A4%ED%8C%A8%EC%9C%A8

댓글 공유

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

소스

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

public int solution(int[][] board, int[] moves) {
    int[] tops = setTop(board);
    
    Stack<Integer> stack = new Stack<Integer>();
    int answer = 0;
    for (int i = 0; i < moves.length; i++) {
        int move = moves[i] - 1;
        int top = tops[move];
        if (top == 0) {
            continue;
        }
        
        int height = board.length - top;
        int value = board[height][move];
        tops[move] = tops[move] - 1;
        
        if (!stack.isEmpty() && (stack.peek() == value)) {
            stack.pop();
            answer += 2;
        } else {
            stack.push(value);
        }
    }
    
    return answer;
}

private int[] setTop(int[][] board) {
    int height = board.length;
    int width = board[0].length;
    int[] tops = new int[width];
    
    for (int i = 0; i < height; i++) {
        for (int j = 0; j < width; j++) {
            if (tops[j] == 0 && board[i][j] != 0) {
                tops[j] = height - i;
            }
        }
    }
    
    return tops;
}

흐름

1. 인형이 쌓여있는 상자에서 각 열마다 맨 위에 있는 인형의 위치를 배열에 저장함.

2. 크레인이 뽑을 위치가 담긴 배열 크기(moves) 만큼 loop 돔.

3. 배열이 0부터 시작하므로, 뽑을 위치(move) 에서 -1 함.

4. 뽑을 위치에서 맨 위의 위치를 가져오는데 0이면 그 열에 있는 건 모두 뽑아 먹은 것이므로 아무 행동도 하지 않음.

5. 총 높이에서 그 열에서 제일 위에 있는 인형의 위치를 뻄.

6. 상자에서 인형을 꺼냄.(value = board[height][move])

7. 그 열에 한 개 꺼냈으므로, top의 위치를 한 칸 내림.

8. stack이 비어 있지 않으면서, stack의 top이 현재 뽑은 인형과 같으면 stack에 저장된 인형을 삭제하고, 삭제된 인형의 갯수를 더 함.

9. 그렇지 않으면 stack에 인형을 추가.

10. 끝

결과

댓글 공유

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

댓글 공유

https://www.acmicpc.net/problem/11399

소스

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

public static int solution(int n, int[] times) {
    Arrays.sort(times);
    
    int answer = 0;
    for (int i = 0; i < times.length; i++) {
        answer += times[i] * (n-i);
    }
    
    return answer;
}

흐름

1. 시간이 짧게 걸리는 사람이 앞에 올수록 전체 수행 시간이 짧아지므로 sorting부터 실행

2. 앞에 사람이 걸리는 시간은 그 뒤 사람들도 그만큼 시간이 + 되는 것이므로 n-i 한 값을 곱함

   ex) 첫 번째 사람이 1분 걸리면 2, 3, 4, 5 번째 사람도 1분씩 더 걸리게 됨

3. 다 더한 값을 출력하면 끝

댓글 공유