프로그래머스: 실패율

문제

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 통과 (7.39ms, 52.6MB)
테스트 2 통과 (6.26ms, 54.7MB)
테스트 3 통과 (11.14ms, 54.2MB)
테스트 4 통과 (12.53ms, 58.2MB)
테스트 5 통과 (13.17ms, 63.3MB)
테스트 6 통과 (12.28ms, 52.3MB)
테스트 7 통과 (9.12ms, 53.5MB)
테스트 8 통과 (11.79ms, 58.6MB)
테스트 9 통과 (13.39ms, 61.4MB)
테스트 10 통과 (11.68ms, 55.8MB)
테스트 11 통과 (12.76ms, 59.8MB)
테스트 12 통과 (11.43ms, 60MB)
테스트 13 통과 (12.27ms, 62.7MB)
테스트 14 통과 (5.77ms, 54.3MB)
테스트 15 통과 (10.07ms, 54MB)
테스트 16 통과 (9.50ms, 55.6MB)
테스트 17 통과 (7.79ms, 53.4MB)
테스트 18 통과 (9.16ms, 54.8MB)
테스트 19 통과 (6.27ms, 52.8MB)
테스트 20 통과 (7.16ms, 53.2MB)
테스트 21 통과 (8.94ms, 55.3MB)
테스트 22 통과 (12.98ms, 62.7MB)
테스트 23 통과 (11.22ms, 58MB)
테스트 24 통과 (17.40ms, 59.7MB)
테스트 25 통과 (6.25ms, 52.9MB)
테스트 26 통과 (6.00ms, 52.3MB)
테스트 27 통과 (5.83ms, 50.4MB)

테스트 케이스

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://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. 끝

결과

번호 속도
테스트 1 통과 (0.94ms, 50.1MB)
테스트 2 통과 (0.94ms, 52.4MB)
테스트 3 통과 (1.04ms, 52.6MB)
테스트 4 통과 (2.28ms, 50.6MB)
테스트 5 통과 (0.98ms, 50.9MB)
테스트 6 통과 (0.97ms, 50.6MB)
테스트 7 통과 (1.11ms, 52.4MB)
테스트 8 통과 (1.25ms, 52.1MB)
테스트 9 통과 (1.37ms, 54.4MB)
테스트 10 통과 (1.38ms, 52.5MB)
테스트 11 통과 (1.81ms, 52.7MB)

댓글 공유

프로그래머스: 최대공약수와 최소공배수

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://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. 이하 상동

시간 비교

첫 번째 풀이

번호 속도
테스트 1 통과 (5.56ms, 50.8MB)
테스트 2 통과 (5.78ms, 50.2MB)
테스트 3 통과 (5.51ms, 50.9MB)
테스트 4 통과 (4.88ms, 52.9MB)
테스트 5 통과 (6.73ms, 52.3MB)
테스트 6 통과 (5.79ms, 52.6MB)
테스트 7 통과 (6.36ms, 50.7MB)
테스트 8 통과 (5.06ms, 50.7MB)
테스트 9 통과 (5.75ms, 52.5MB)
테스트 10 통과 (4.99ms, 50.6MB)
테스트 11 통과 (5.25ms, 52.7MB)
테스트 12 통과 (5.65ms, 52.4MB)
테스트 13 통과 (5.75ms, 55MB)

두 번째 풀이

번호 속도
테스트 1 통과 (1.34ms, 52.5MB)
테스트 2 통과 (1.57ms, 49.9MB)
테스트 3 통과 (1.52ms, 50.3MB)
테스트 4 통과 (1.36ms, 53.1MB)
테스트 5 통과 (1.52ms, 52.3MB)
테스트 6 통과 (1.42ms, 52.4MB)
테스트 7 통과 (1.52ms, 50.4MB)
테스트 8 통과 (1.43ms, 50.4MB)
테스트 9 통과 (1.37ms, 52.2MB)
테스트 10 통과 (1.50ms, 50.2MB)
테스트 11 통과 (1.42ms, 49.9MB)
테스트 12 통과 (1.72ms, 52.2MB)
테스트 13 통과 (1.73ms, 50.7MB)
  • Stream()이 생각보다 더 느리게 동작하는 듯 싶다.

댓글 공유

Junggu Ji

author.bio


author.job