프로그래머스: 소수 찾기(완전 탐색)

문제

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

코드

  • 순열을 이용한 완전탐색으로 해결
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
60
61
62
63
public int solution(String numbers) {
    char[] tochar = numbers.toCharArray();

    int numbersLength = tochar.length;

    Set<Integer> numberSet = new HashSet<Integer>();
    for (int i = 1; i <= numbersLength; i++) {
        perm(tochar, 0, i, numberSet);
    }

    int answer = getPrimeCount(numberSet);

    return answer;
}

private void perm(char[] array, int depth, int length, Set<Integer> numberSet) {
    if (depth == length) {

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < length; i++) {
            sb.append(array[i]);
        }

        int number = Integer.parseInt(sb.toString());
        if (number > 1) {
            numberSet.add(number);
        }

        return;
    }

    for (int i = depth; i < array.length; i++) {
        swap(array, i, depth);
        perm(array, depth + 1, length, numberSet);
        swap(array, i, depth);
    }
}

private void swap(char[] arrary, int i, int j) {
    char temp = arrary[i];
    arrary[i] = arrary[j];
    arrary[j] = temp;
}

private int getPrimeCount(Set<Integer> numberSet) {
    int result = 0;
    for (int i : numberSet) {
        boolean isPrime = true;

        for (int j = 2; j * j <= i; j++) {
            if (i % j == 0) {
                isPrime = false;
                break;
            }
        }

        if (isPrime) {
            ++result;
        }
    }

    return result;
}

흐름

  1. [1,2,3] 배열일 경우 3 자리 수 까지 나타날 수 있으므로, numbers의 길이 만큼 반복하면서 순열을 만듬
  2. perm() 메서드를 재귀로 돌면서 깊이 만큼 index를 스위칭하면서 순열을 만듬
    • ex) [1,2,3] 인 경우, 0번째와 0번째를 스왑하여 123이 되고 그 이후엔 0번째와 1번째를 스왑해서 213, 그 이후엔 0과 2를 스왑해서 321 … 이런 식으로 진행된다
  3. 돌다가 깊이랑 이번에 만들 숫자의 길이가 같으면 중복되지 않게 Set에 저장하는데 1 이하인 경우엔 소수가 아니므로 저장하지 않음
  4. 다시 swap() 해서 배열 index를 원상복귀 시킴
  5. 반복해서 모든 순열을 만든 후 해당 Set에 저장된 수들이 소수 인지 판별해서 소수면 카운트 증가시킴
  6. 끝

결과

번호 속도
테스트 1 통과 (1.06ms, 50.3MB)
테스트 2 통과 (9.99ms, 53MB)
테스트 3 통과 (0.83ms, 52.1MB)
테스트 4 통과 (7.08ms, 52.6MB)
테스트 5 통과 (23.43ms, 56MB)
테스트 6 통과 (0.91ms, 52.6MB)
테스트 7 통과 (1.13ms, 51.9MB)
테스트 8 통과 (18.16ms, 55.9MB)
테스트 9 통과 (0.96ms, 49.9MB)
테스트 10 통과 (10.37ms, 52.9MB)
테스트 11 통과 (2.51ms, 51.5MB)
테스트 12 통과 (2.16ms, 52MB)

테스트 케이스

1
2
3
4
5
6
assertEquals(3, test.solution("17"));
assertEquals(2, test.solution("011"));
assertEquals(1, test.solution("2"));
assertEquals(12, test.solution("7843"));
assertEquals(0, test.solution("9999999"));
assertEquals(1336, test.solution("1276543"));

참고 사이트

댓글 공유

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

문제

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"));

참고 사이트

댓글 공유

  • page 1 of 1

Junggu Ji

author.bio


author.job