프로그래머스: 가장 큰 수

문제

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

코드

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
43
44
45
46
47
48
49
50
51
52
public String solution(int[] numbers) {

    List<Numbers> list = new ArrayList<Numbers>();
    for (int i = 0; i < numbers.length; i++) {
        int number = numbers[i];

        char[] str = String.valueOf(number).toCharArray();
        StringBuilder fourDigitString = new StringBuilder();

        fourDigitString.append(str);
        if (str.length < 4) {

            for (int j = 0; j < 4 - str.length; j++) {
                fourDigitString.append(str[((j) % str.length)]);
            }
        }

        list.add(new Numbers(i, Integer.parseInt(fourDigitString.toString())));
    }

    Collections.sort(list, new Comparator<Numbers>() {

        @Override
        public int compare(Numbers o1, Numbers o2) {
            return o2.value.compareTo(o1.value);
        }
    });

    StringBuilder sb = new StringBuilder();
    int sum = 0;
    for (Numbers n : list) {
        sum += n.value;
        sb.append(numbers[n.postion]);
    }

    if (sum == 0) {
        sb.setLength(0);
        sb.append(0);
    }

    return sb.toString();
}

class Numbers {
    public Integer postion;
    public Integer value;

    public Numbers(Integer postion, Integer value) {
        this.postion = postion;
        this.value = value;
    }
}

흐름

  1. 문제에서 numbers의 원소 값이 1000 이하라고 했으므로 numbers 크기 만큼 돌면서 numbers 안에 값이 4자리가 아닌 경우 자기 숫자를 뒤에 덧붙여서 4자리로 만듬
    • ex) 121 > 1212, 1 > 1111, 23 > 2323, …
  2. 현재 배열의 index와 값을 비교하기 위에 inner class를 하나 만들어서 index와 value를 저장하고 class를 list에 추가
  3. list를 class의 value 값으로 큰 수부터 나오도록 정렬
  4. list를 돌면서 value를 StringBuilder로 붙임
  5. 이 때, 0 0 0 0 일 경우 0 이 되어야 하므로 value들을 모두 더했을 때 값이 0이라면 0 만 붙임
  6. toString() 으로 String형으로 return
  7. 끝

다른 분들의 해결방법

다른분의 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public String solution(int[] numbers) {
    String answer = "";

    List<Integer> list = new ArrayList<>();
    for(int i = 0; i < numbers.length; i++) {
        list.add(numbers[i]);
    }
    Collections.sort(list, (a, b) -> {
        String as = String.valueOf(a), bs = String.valueOf(b);
        return -Integer.compare(Integer.parseInt(as + bs), Integer.parseInt(bs + as));
    });
    StringBuilder sb = new StringBuilder();
    for(Integer i : list) {
        sb.append(i);
    }
    answer = sb.toString();
    if(answer.charAt(0) == '0') {
        return "0";
    }else {
        return answer;
    }
}

위 코드의 로직

  • list에 numbers array를 그대로 저장하고 list의 저장된 element를 앞뒤로 붙여서 정수로 바꾼 후 비교해서 정렬
  • String을 다루는 부분이 많아서 속도는 살짝 떨어지는 듯

결과

1 번

번호 속도
테스트 1 통과 (139.80ms, 83.2MB)
테스트 2 통과 (88.71ms, 67MB)
테스트 3 통과 (167.96ms, 82.4MB)
테스트 4 통과 (17.95ms, 50.7MB)
테스트 5 통과 (129.09ms, 77.4MB)
테스트 6 통과 (116.84ms, 71.2MB)
테스트 7 통과 (1.44ms, 52.3MB)
테스트 8 통과 (1.38ms, 52.7MB)
테스트 9 통과 (1.20ms, 50.2MB)
테스트 10 통과 (1.46ms, 52.6MB)
테스트 11 통과 (1.65ms, 52.9MB)

2 번

번호 속도
테스트 1 통과 (340.75ms, 105MB)
테스트 2 통과 (236.67ms, 82.1MB)
테스트 3 통과 (350.56ms, 126MB)
테스트 4 통과 (80.72ms, 59.7MB)
테스트 5 통과 (300.18ms, 110MB)
테스트 6 통과 (280.61ms, 87.6MB)
테스트 7 통과 (31.26ms, 57.2MB)
테스트 8 통과 (35.88ms, 53.4MB)
테스트 9 통과 (34.27ms, 55.3MB)
테스트 10 통과 (30.44ms, 55.6MB)
테스트 11 통과 (40.16ms, 55.3MB)

테스트 케이스

1
2
3
4
5
6
7
8
9
assertEquals("6210", test.solution(new int[] {6, 10, 2}));
assertEquals("9534330", test.solution(new int[] {3, 30, 34, 5, 9}));
assertEquals("220200", test.solution(new int[] {2,200,20}));
assertEquals("2200", test.solution(new int[] {2,0,20}));
assertEquals("0", test.solution(new int[] {0,0,0}));
assertEquals("21212", test.solution(new int[] {12, 212}));
assertEquals("21221", test.solution(new int[] {212, 21}));
assertEquals("7000", test.solution(new int[] {0, 0, 70}));
assertEquals("1000000", test.solution(new int[] {0, 0, 0, 1000}));

댓글 공유

프로그래머스: 문자열 압축

문제

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

코드

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
43
44
45
46
47
48
public int solution(String s) {
    int stringLength = s.length();

    StringBuilder result = new StringBuilder();
    String origin = new String();
    char[] tochar = s.toCharArray();
    int min = Integer.MAX_VALUE;

    for (int i = 1; i <= stringLength / 2; i++) {
        int compression = 1;
        result.setLength(0);
        origin = new String(tochar, 0, i);

        String nextWord = new String();
        for (int j = i; j < stringLength; j+=i) {
            if (j + i > stringLength) {
                nextWord = s.substring(j, stringLength);
            } else {
                nextWord = new String(tochar, j , i);
            }

            if (origin.equals(nextWord)) {
                ++compression;
            } else {
                if (compression != 1) {
                    result.append(compression);
                }

                result.append(origin);

                origin = nextWord.toString();
                compression = 1;
            }
        }

        if (compression != 1) {
            result.append(compression);
        }

        result.append(origin);

        if (min > result.length()) {
            min = result.length();
        }
    }

    int answer = min > stringLength ? stringLength : min;
    return answer;

흐름

  1. 문자열을 반으로 나눠서 2개로 나눈 것 보다 짧을 수 없으므로 문자열 길이 / 2 한 값 만큼 반복

  2. 비교 할 문자열을 구함(origin)

    • 처음엔 1개 짜리 이후엔 2개, 3개, … 증가 할 수 있도록 i를 증가 시키면서 i 번째 까지 자름

  3. i 번째 문자 이후로 비교 할 문자를 구함

  4. 같으면 압축율을 증가시키고

  5. 다르면 압축율과 문자를 더해서 압축문자열(result)을 만듬

  6. 비교 할 문자를 구하면서 마지막 문자는 안 붙여지고 팅기므로 for 문 밖에서 마지막 문자를 붙임

  7. 이전에 구했던 압축문자열 길이와 비교해서 더 작은 길이를 저장함

  8. 끝

결과

번호 속도
테스트 1 통과 (0.99ms, 52.4MB)
테스트 2 통과 (2.92ms, 49.9MB)
테스트 3 통과 (1.72ms, 52.7MB)
테스트 4 통과 (0.99ms, 52.1MB)
테스트 5 통과 (0.84ms, 50MB)
테스트 6 통과 (1.03ms, 52.4MB)
테스트 7 통과 (3.49ms, 50.4MB)
테스트 8 통과 (2.49ms, 50.3MB)
테스트 9 통과 (4.46ms, 52.6MB)
테스트 10 통과 (9.25ms, 52.4MB)
테스트 11 통과 (1.25ms, 50.2MB)
테스트 12 통과 (1.28ms, 52.3MB)
테스트 13 통과 (9.63ms, 51.8MB)
테스트 14 통과 (4.35ms, 52.2MB)
테스트 15 통과 (1.31ms, 52.1MB)
테스트 16 통과 (0.85ms, 50.2MB)
테스트 17 통과 (8.91ms, 52.6MB)
테스트 18 통과 (7.70ms, 52.6MB)
테스트 19 통과 (8.63ms, 54.9MB)
테스트 20 통과 (7.89ms, 52.6MB)
테스트 21 통과 (9.99ms, 52.7MB)
테스트 22 통과 (10.63ms, 52.7MB)
테스트 23 통과 (9.68ms, 52.5MB)
테스트 24 통과 (7.89ms, 54.4MB)
테스트 25 통과 (10.43ms, 52.9MB)
테스트 26 통과 (8.17ms, 52.5MB)
테스트 27 통과 (15.60ms, 52.6MB)
테스트 28 통과 (0.88ms, 50.4MB)
  • result에 문자열을 더하지 말고 그냥 문자열 길이를 더하는 방식으로 하면 더 시간을 줄일 수 있음

테스트 케이스

1
2
3
4
5
6
7
8
assertEquals(7, test.solution("aabbaccc"));
assertEquals(9, test.solution("ababcdcdababcdcd"));
assertEquals(8, test.solution("abcabcdede"));
assertEquals(14, test.solution("abcabcabcabcdededededede"));
assertEquals(17, test.solution("xababcdcdababcdcd"));
assertEquals(1, test.solution("a"));
assertEquals(2, test.solution("aaaaa"));
assertEquals(3, test.solution("aaaaaaaaaa"));

참고 사이트

댓글 공유

프로그래머스: 다리를 지나는 트럭

문제

https://programmers.co.kr/learn/courses/30/lessons/42583?language=java

코드

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
43
44
45
46
47
48
49
50
51
52
public int solution(int bridge_length, int weight, int[] truck_weights) {
    LinkedList<Truck> queue = new LinkedList<Truck>();

    for (int i = 0; i < truck_weights.length; i++) {
        queue.offer(new Truck(bridge_length, truck_weights[i]));
    }

    int answer = 1;
    int bridgeOnTruck = 0;
    while (!queue.isEmpty()) {

        int totalWeight = 0;
        for (int i = 0; i < bridgeOnTruck; i++) {
            totalWeight += queue.get(i).weight;
        }

        int nextWeight = 0;
        if (queue.size() > bridgeOnTruck) {
            nextWeight = queue.get(bridgeOnTruck).weight;
        }

        if (totalWeight + nextWeight <= weight) {
            if (queue.size() > bridgeOnTruck) {
                ++bridgeOnTruck;
            }
        }

        for (int i = 0; i < bridgeOnTruck; i++) {
            Truck truck = queue.get(i);
            truck.position = truck.position - 1;
        }

        if (queue.peek().position == 0) {
            queue.poll();
            --bridgeOnTruck;
        }

        ++answer;
    }

    return answer;
}

class Truck {
    public int position;
    public int weight;

    public Truck(int position, int weight) {
        this.position = position;
        this.weight = weight;
    }
}

흐름

  1. 트럭 array를 queue에 모두 저장
  2. 트럭 모두 건널 때 까지 반복
  3. 한 번에 몇 개의 트럭까지 건널 수 있을 지 계산하기 위해 현재 다리 위에 있는 트럭의 개수 만큼 돌면서 트럭 무게를 더함
  4. 다음 번 트럭까지 다리에 올라 올 수 있는 지 확인하기 위해 큐의 마지막 index가 아니라면 queue에서 다음 번 트럭의 무게를 가져옴
  5. 현재 다리에 있는 트럭들의 무게 + 다음 트럭의 무게를 더한 값이 다리가 버틸 수 있는 무게 보다 가벼우면
  6. 큐의 마지막인지 체크해서 큐의 마지막이 아니라면 그 다음 트럭도 다리 위에 올라와야 하기 때문에 다리 위 트럭의 개수(truckAmount)를 증가 시킴
  7. 다리 위 트럭의 수 만큼 반복하면서 트럭을 앞으로 한칸 씩 움직임
  8. 첫 번째 트럭이 다리를 건넜다면 queue에서 제거하고 다리 위 트럭 수를 하나 감소 시킴
  9. 초를 증가 시킴
  10. 끝

결과

번호 속도
테스트 1 통과 (3.63ms, 52.1MB)
테스트 2 통과 (14.16ms, 52.1MB)
테스트 3 통과 (1.65ms, 53.3MB)
테스트 4 통과 (41.49ms, 53.8MB)
테스트 5 통과 (70.64ms, 53.9MB)
테스트 6 통과 (53.31ms, 56.1MB)
테스트 7 통과 (3.09ms, 50MB)
테스트 8 통과 (1.97ms, 50.3MB)
테스트 9 통과 (10.68ms, 54.6MB)
테스트 10 통과 (2.20ms, 53MB)
테스트 11 통과 (1.10ms, 52.5MB)
테스트 12 통과 (2.35ms, 52.2MB)
테스트 13 통과 (4.50ms, 52.2MB)
테스트 14 통과 (1.26ms, 53MB)

테스트 케이스

1
2
3
assertEquals(8, test.solution(2, 10, new int[] {7,4,5,6}));
assertEquals(101, test.solution(100, 100, new int[] {10}));
assertEquals(110, test.solution(100, 100, new int[] {10,10,10,10,10,10,10,10,10,10}));

댓글 공유

프로그래머스: 멀쩡한 사각형

카테고리 개발

https://programmers.co.kr/learn/courses/30/lessons/62048?language=java

코드

1
2
3
4
5
6
7
8
9
10
11
12
public long solution(long w,long h) {
    long big = w > h ? w : h;
    long small = w > h ? h : w;

    while (small != 0) {
        long r = big % small;
        big = small;
        small = r;
    }

    return (w * h) - (w + h - big);
}

흐름

  1. 최대 공약수를 구함

  2. 전체 사각형 수 (w * h) 에서 안 멀쩡한 사각형 수(w + h - 최대 공약수)를 뺌

  3. 끝

최대 공약수를 사용하는 이유

아래 블로그에서 잘 설명 해주셨음

결과

번호 속도
테스트 1 통과 (0.76ms, 50.7MB)
테스트 2 통과 (0.81ms, 52.4MB)
테스트 3 통과 (0.75ms, 52.6MB)
테스트 4 통과 (0.70ms, 52.6MB)
테스트 5 통과 (0.82ms, 51.9MB)
테스트 6 통과 (0.80ms, 52.1MB)
테스트 7 통과 (0.85ms, 52.4MB)
테스트 8 통과 (0.86ms, 54.6MB)
테스트 9 통과 (0.72ms, 52.3MB)
테스트 10 통과 (0.73ms, 52.6MB)
테스트 11 통과 (0.74ms, 52.2MB)
테스트 12 통과 (0.58ms, 52.5MB)
테스트 13 통과 (0.51ms, 52.5MB)
테스트 14 통과 (0.60ms, 52.6MB)
테스트 15 통과 (0.53ms, 50.3MB)
테스트 16 통과 (0.61ms, 52.5MB)
테스트 17 통과 (0.61ms, 52.3MB)
테스트 18 통과 (0.80ms, 52.3MB)

테스트 케이스

1
2
3
4
5
assertEquals(80, test.solution(8, 12));
assertEquals(12, test.solution(5, 4));
assertEquals(40, test.solution(10, 5));
assertEquals(352, test.solution(17, 23));
assertEquals(30467460, test.solution(3, 15233730));

참고 사이트

본문 참조

댓글 공유

프로그래머스: 프린터

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

코드

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
public int solution(int[] priorities, int location) {
    int answer = 0;

    LinkedList<Integer> queue = new LinkedList<Integer>();
    for (int i = 0; i < priorities.length; i++) {
        queue.offer(priorities[i]);
    }

    while (queue.size() != 0) {
        for (int i = 1; i < queue.size(); i++) {
            if (queue.peek() < queue.get(i)) {
                queue.offer(queue.poll());

                if (location == 0) {
                    location = queue.size() - 1;
                } else {
                    --location;
                }

                i = 0;
            }
        }

        answer++;
        if (location == 0) {
            break;
        }

        --location;
        queue.poll();
    }

    return answer;
}

흐름

  1. 우선순위가 담긴 배열(priorities)을 Queue에 저장

  2. 큐에 첫 번째 값을 꺼내서 그 뒤 값들과 비교

  3. 첫 번째 값이 뒤에 있는 값들 보다 작다면 큐에 맨 뒤로 보냄

  4. 출력해야 되는 프린터의 index를 조정

    • index가 0 이라면 맨 뒤로 이동했을테니 큐 크기 - 1;
    • 아니라면 앞으로 한 칸 이동 했을테니 -1

  5. 맨 뒤로 이동 시켰으면 맨 앞에 값이 변경 됐으므로 처음부터 다시 검사

  6. 큐의 0 번째 인덱스가 가장 큰 값이라면 count를 증가시키고 출력해야 하는 프린터의 위치를 확인

  7. 출력해야하는 프린터가 맨 앞이라면 break로 반복문을 빠져나와 프로그램 종료

  8. 아니라면 맨 앞에 값을 삭제하고 index를 -1 해서 한 칸 앞으로 당김

  9. 끝날 때 까지 반복

  10. 끝

결과

번호 속도
테스트 1 통과 (3.17ms, 52.8MB)
테스트 2 통과 (3.41ms, 52.6MB)
테스트 3 통과 (1.33ms, 52.6MB)
테스트 4 통과 (1.15ms, 50.8MB)
테스트 5 통과 (0.85ms, 52.2MB)
테스트 6 통과 (1.44ms, 52.7MB)
테스트 7 통과 (1.58ms, 50.4MB)
테스트 8 통과 (3.89ms, 52.9MB)
테스트 9 통과 (1.04ms, 52.8MB)
테스트 10 통과 (1.57ms, 52.3MB)
테스트 11 통과 (3.90ms, 52.7MB)
테스트 12 통과 (1.07ms, 52.3MB)
테스트 13 통과 (4.36ms, 52.1MB)
테스트 14 통과 (0.83ms, 52MB)
테스트 15 통과 (0.95ms, 50.4MB)
테스트 16 통과 (1.21ms, 50.3MB)
테스트 17 통과 (2.79ms, 50.7MB)
테스트 18 통과 (0.94ms, 50.7MB)
테스트 19 통과 (2.61ms, 53.1MB)
테스트 20 통과 (1.51ms, 52.3MB)

테스트 케이스

1
2
3
4
assertEquals(1, test.solution(new int[] {2, 1, 3, 2}, 2));
assertEquals(5, test.solution(new int[] {1, 1, 9, 1, 1, 1}, 0));
assertEquals(6, test.solution(new int[] {2, 2, 2, 1, 3, 4}, 3));
assertEquals(2, test.solution(new int[] {1, 2, 3, 2}, 3));

댓글 공유

프로그래머스: 기능개발

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

소스

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
public int[] solution(int[] progresses, int[] speeds) {
    int start = 0;
    List<Integer> list = new ArrayList<Integer>();
    while (start != progresses.length) {
        int deploy = 0;
        for (int i = start; i < progresses.length; i++) {
            progresses[i] += speeds[i];
        }

        for (int i = start; i < progresses.length; i++) {
            if (progresses[start] < 100) {
                break;
            }

            if (progresses[i] >= 100) {
                ++start;
                ++deploy;
            }
        }

        if (deploy != 0) {
            list.add(deploy);
        }
    }

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

흐름

  1. 기능개발이 완료된 인덱스부터 반복하기 위해 start 변수 생성

  2. 기능개발이 끝날 때 까지 반복

  3. 개발이 안 끝난 기능 index 부터 돌면서 작업 속도를 더 함

  4. 개발이 안 끝난 기능 index 부터 돌면서 첫 번째 기능이 개발 됐는지 확인하고 안 끝났으면 3 번으로 돌아감

  5. 첫 번째 기능이 완료 되었으면 그 다음 기능개발을 위해 ++start 하고, deploy된 기능을 카운팅하는 deploy 변수를 증가

  6. deploy한 기능이 있는 경우에만 list에 저장

  7. ArrayList를 int[]로 변경

  8. 끝

다른 분의 소스

1
2
3
4
5
6
7
8
9
10
11
public int[] solution(int[] progresses, int[] speeds) {
    int[] dayOfend = new int[100];
    int day = -1;
    for(int i=0; i<progresses.length; i++) {
        while(progresses[i] + (day*speeds[i]) < 100) {
            day++;
        }
        dayOfend[day]++;
    }
    return Arrays.stream(dayOfend).filter(i -> i!=0).toArray();
}

로직

  • 기능 갯수 만큼 돌면서 진도율과 날짜 * 개발 속도를 비교해서 100 보다 작으면 다음날로 증가시키고 크면 그 날짜에 저장되는 갯수를 증가시킴

  • 대박

결과

1 번

번호 속도
테스트 1 통과 (4.53ms, 50.8MB)
테스트 2 통과 (5.07ms, 50.6MB)
테스트 3 통과 (5.09ms, 52.8MB)
테스트 4 통과 (5.29ms, 52.4MB)
테스트 5 통과 (8.36ms, 55MB)
테스트 6 통과 (4.95ms, 51.2MB)
테스트 7 통과 (5.58ms, 52.6MB)
테스트 8 통과 (5.18ms, 50.7MB)
테스트 9 통과 (5.44ms, 52.5MB)
테스트 10 통과 (5.22ms, 50.5MB)

2 번

번호 속도
테스트 1 통과 (6.60ms, 51.4MB)
테스트 2 통과 (6.83ms, 53.1MB)
테스트 3 통과 (6.92ms, 52.5MB)
테스트 4 통과 (6.70ms, 52.8MB)
테스트 5 통과 (19.88ms, 52.4MB)
테스트 6 통과 (5.05ms, 50.7MB)
테스트 7 통과 (7.01ms, 52.5MB)
테스트 8 통과 (4.68ms, 50.5MB)
테스트 9 통과 (6.95ms, 52.2MB)
테스트 10 통과 (5.31ms, 50.8MB)
  • 두 소스 모두 Arrays.stream을 사용하지 않고 반복해서 저장하면 1초 대로 줄어듬.
  • 확실히 스트림이 느린 듯함.

테스트 케이스

1
2
3
assertArrayEquals(new int[] {2,1}, test.solution(new int[] {93, 30, 55}, new int[] {1, 30, 5}));
assertArrayEquals(new int[] {3}, test.solution(new int[] {0, 30, 55}, new int[] {1, 99, 99}));
assertArrayEquals(new int[] {1,1,1}, test.solution(new int[] {3, 2, 1}, new int[] {1, 1, 1}));

전체 소스

https://github.com/jungguji/algorithm_training/blob/master/src/main/java/algorithm/programmers/level2/stackqueue/%EB%8B%A4%EB%A6%AC%EB%A5%BC_%EC%A7%80%EB%82%98%EB%8A%94_%ED%8A%B8%EB%9F%AD.java

댓글 공유

프로그래머스: 스킬트리

https://programmers.co.kr/learn/courses/30/lessons/49993?language=java

소스

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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
public int solution(String skill, String[] skill_trees) {
    char[] ch = skill.toCharArray();

    List<ArrayList<Skill>> l = new ArrayList<ArrayList<Skill>>();
    for (String element : skill_trees) {
        ArrayList<Skill> list = new ArrayList<Skill>();

        for (int i = 0; i < ch.length; i++) {
            Skill s = new Skill();
            s.skill = ch[i];
            s.index = element.indexOf(ch[i]);

            if (s.index != -1) {
                list.add(s);
            }
        }

        l.add(list);
    }

    int answer = 0;
    for (ArrayList<Skill> list : l) {
        Collections.sort(list, new Comparator<Skill>() {
            @Override
            public int compare(Skill o1, Skill o2) {
                return o1.getIndex().compareTo(o2.getIndex());
            }
        });

        StringBuilder sb = new StringBuilder();
        for (Skill s : list) {
            sb.append(s.getSkill());
        }

        if (skill.startsWith(sb.toString())) {
            answer++;
        }
    }

    return answer;
}

public class Skill {
    private int index;
    private char skill;

    public Integer getIndex() {
        return index;
    }
    public void setIndex(int index) {
        this.index = index;
    }
    public char getSkill() {
        return skill;
    }
    public void setSkill(char skill) {
        this.skill = skill;
    }
}

흐름

  1. 스킬트리에 있는 스킬들을 선행스킬 만큼 반복한다.

  2. 돌면서 스킬들에서 선행스킬의 index와 선행스킬명을 저장하는 클래스(Skill)에 저장하고 그 클래스를 List에 저장한다.

    • ex) List = [{index = 1, skill = A}, {index = 7, skill = Q}, …]

  3. 선행스킬명을 저장한 List를 다른 List(AllSkillList)에 저장한다.

    • 전체 스킬을 저장해야 하므로
    • ex) AllSkillList = [List1, List2, List3, …]

  4. 전체 스킬이 저장된 List(AllSkillList)를 돌면서 저장된 List의 Skill의 Index 순으로 정렬 시킨다.

  5. 정렬된 List를 돌면서 StringBuilder에 스킬명을 담는다.

  6. 입력받은 선행스킬과 비교하여 일치하면 answer을 증가 시킨다.

  7. 끝

다른 분의 소스

1
2
3
4
5
6
7
8
9
10
11
12
13
public int solution(String skill, String[] skill_trees) {
    int answer = 0;
    ArrayList<String> skillTrees = new ArrayList<String>(Arrays.asList(skill_trees));
    Iterator<String> it = skillTrees.iterator();

    while (it.hasNext()) {
        if (skill.indexOf(it.next().replaceAll("[^" + skill + "]", "")) != 0) {
            it.remove();
        }
    }
    answer = skillTrees.size();
    return answer;
}

로직

  • 스킬트리에 있는 스킬들 중 선행스킬이 아닌 녀석들을 없애버리고 선행스킬과 일치하는 지 확인해서 일치하지 않으면 List에서 삭제하고 List의 갯수를 return 하는 것으로 끝을 낸다.

  • ex) “CBD” 인 경우 “BACDE”에서 “C”, “B”, “D”가 아닌 녀석들은 삭제되서 “BCD”가 남지만 “CBD”.indexOf(“BCD”) 할 경우 “CBD”에 “BCD”가 존재 하지 않으므로 1을 return 하고 -1은 0이 아니므로 List에서 삭제된다.

  • “BDA” 인 경우엔 “CBD”.indexOf(“BD”) 할 경우 “CBD”에 존재하지만 1 번째 index에 존재하므로 1을 return 하고 List에서 삭제된다.

  • 직관적이고 가독성이 좋다.

  • 정규표현식 활용도 굿

결과

1 번

번호 속도
테스트 1 통과 (1.40ms, 52.1MB)
테스트 2 통과 (1.37ms, 50.1MB)
테스트 3 통과 (1.29ms, 52.7MB)
테스트 4 통과 (1.11ms, 52.3MB)
테스트 5 통과 (1.42ms, 50.6MB)
테스트 6 통과 (1.33ms, 52.4MB)
테스트 7 통과 (1.38ms, 50.5MB)
테스트 8 통과 (1.38ms, 50.8MB)
테스트 9 통과 (1.46ms, 52MB)
테스트 10 통과 (1.26ms, 52.4MB)
테스트 11 통과 (1.36ms, 54.3MB)
테스트 12 통과 (1.72ms, 52.5MB)
테스트 13 통과 (1.27ms, 52.3MB)
테스트 14 통과 (1.31ms, 52.2MB)

2 번

번호 속도
테스트 1 통과 (17.73ms, 54.5MB)
테스트 2 통과 (18.75ms, 52.2MB)
테스트 3 통과 (17.83ms, 52.4MB)
테스트 4 통과 (19.98ms, 54.3MB)
테스트 5 통과 (20.10ms, 52.3MB)
테스트 6 통과 (20.89ms, 52.5MB)
테스트 7 통과 (20.94ms, 54.3MB)
테스트 8 통과 (18.68ms, 52.2MB)
테스트 9 통과 (19.60ms, 52.8MB)
테스트 10 통과 (20.75ms, 54.4MB)
테스트 11 통과 (18.02ms, 52.3MB)
테스트 12 통과 (18.70ms, 54.3MB)
테스트 13 통과 (18.79ms, 52.5MB)
테스트 14 통과 (19.85ms, 54.8MB)
  • 2 번의 경우 Arrays.asList(skill_trees) 와 replace 때문에 속도가 살짝 느려진 것으로 판단된다.

테스트 케이스

1
2
3
4
5
6
assertEquals(3, test.solution("CBD", new String[] {"BACDE", "CBADF", "AECB", "BDA", "ASF", "BDF","CEFD"}));
assertEquals(4, test.solution("C", new String[] {"BACDE", "CBADF", "AECB", "BDA"}));
assertEquals(2, test.solution("CBD", new String[] {"C", "D", "CB", "BDA"}));
assertEquals(2, test.solution("AC", new String[] {"ABC", "CA", "ATEW", "SFCQTA"}));
assertEquals(2, test.solution("ACHQ", new String[] {"TWER", "FGCHQEA", "ATEW", "SFCQTA"}));
assertEquals(4, test.solution("CBDK", new String[] {"CB", "CXYB", "BD", "AECD", "ABC", "AEX", "CDB", "CBKD", "IJCB", "LMDK"}));
  • 임의로 만든 테스트 케이스 이므로 위 테스트 케이스를 통과해도 시험에서 통과하지 못할 가능성이 있다.

댓글 공유

프로그래머스: 다트게임

https://programmers.co.kr/learn/courses/30/lessons/17682?language=java

소스

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
43
public int solution(String dartResult) {
	char[] charArray = dartResult.toCharArray();
	
	int[] scores = new int[3];
	int i = 0;
	StringBuilder sb = new StringBuilder();
	for (char ch : charArray) {
		switch (ch) {
		case 'S':
			scores[i++] = Integer.parseInt(sb.toString());
			
			sb.setLength(0);
			break;
		case 'D':
			int a = Integer.parseInt(sb.toString());
			scores[i++] = a * a;
			
			sb.setLength(0);
			break;
		case 'T':
			int b = Integer.parseInt(sb.toString());
			scores[i++] = b * b * b;
			
			sb.setLength(0);
			break;
		case '*':
			if (i > 1) {
				scores[i-2] = scores[i-2] * 2;
			}
			scores[i-1] = scores[i-1] * 2;
			break;
		case '#':
			scores[i-1] = scores[i-1] * -1;
			break;
		default:
			sb.append(ch);
			break;
		}
	}
	
	int answer = scores[0] + scores[1] + scores[2];
	return answer;
}

흐름

  1. 문자열을 charArray로 치환하고 loop 돈다.

  2. char를 비교하여 각 문자별로 맞게 계산을 실행하고, index를 증가 시킨 후 다음 점수 저장을 위해 StringBuilder를 초기화 한다.

  3. ‘*‘ 일 경우 이전 점수와 현재 점수 모두 2 배씩 해야 하므로 2 번 던진 경우엔 이전 점수도 2를 곱 해준다.

  4. 계산된 세 점수 모두 더해서 return 한다.

  5. 끝

결과

번호 속도
테스트 1 통과 (0.79ms, 52.4MB)
테스트 2 통과 (0.86ms, 52.2MB)
테스트 3 통과 (0.86ms, 52.4MB)
테스트 4 통과 (0.84ms, 52.3MB)
테스트 5 통과 (0.92ms, 54.5MB)
테스트 6 통과 (0.82ms, 52.5MB)
테스트 7 통과 (0.83ms, 52.1MB)
테스트 8 통과 (0.83ms, 52.2MB)
테스트 9 통과 (0.90ms, 50.8MB)
테스트 10 통과 (0.83ms, 52.7MB)
테스트 11 통과 (0.84ms, 52.9MB)
테스트 12 통과 (0.84ms, 52.5MB)
테스트 13 통과 (0.82ms, 50.4MB)
테스트 14 통과 (0.74ms, 52.6MB)
테스트 15 통과 (0.90ms, 52.1MB)
테스트 16 통과 (0.86ms, 52.9MB)
테스트 17 통과 (0.81ms, 52.7MB)
테스트 18 통과 (0.86ms, 52.4MB)
테스트 19 통과 (0.85ms, 50.1MB)
테스트 20 통과 (0.95ms, 52.4MB)
테스트 21 통과 (0.81ms, 50.4MB)
테스트 22 통과 (0.80ms, 51.9MB)
테스트 23 통과 (0.88ms, 52.3MB)
테스트 24 통과 (0.87ms, 51.9MB)
테스트 25 통과 (0.87ms, 50.4MB)
테스트 26 통과 (0.88ms, 52.1MB)
테스트 27 통과 (0.89ms, 52.4MB)
테스트 28 통과 (0.88ms, 52.2MB)
테스트 29 통과 (0.85ms, 52.7MB)
테스트 30 통과 (0.89ms, 51.8MB)
테스트 31 통과 (0.85ms, 50.2MB)
테스트 32 통과 (0.83ms, 52MB)

테스트 케이스

1
2
3
4
5
6
7
assertEquals(37, test.solution("1S2D*3T"));
assertEquals(9, test.solution("1D2S#10S"));
assertEquals(3, test.solution("1D2S0T"));
assertEquals(23, test.solution("1S*2T*3S"));
assertEquals(5, test.solution("1D#2S*3S"));
assertEquals(-4, test.solution("1T2D3D#"));
assertEquals(59, test.solution("1D2S3T*"));
  • 프로그래머스에서 제공한 예제 테스트 케이스이므로
    위 테스트케이스를 모두 통과하여도 실제 테스트에선 통과하지 못할 수 있음.

댓글 공유

프로그래머스: 실패율

문제

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)

댓글 공유

Junggu Ji

author.bio


author.job