[프로그래머스][Java][Lv.0] k의 개수

 

https://school.programmers.co.kr/learn/courses/30/lessons/120887

프로그래머스

 

내가 푼 풀이

1. j-i+1 한 만큼 사이즈의 배열을 만든다. 이유는 값을 집어넣을때 array out of bound exception가 안나오게 하려고 합니다.

2. 정수를 문자열로 형변환한뒤, 각 char에 대한 값이 k와 일치한다면 +를 해줍니다.

class Solution {
    public int solution(int i, int j, int k) {
        int answer = 0;

        int[] ints = new int[j-i+1];
        int idx = 0;
        for (int l = i; l <= j; l++) {
            ints[idx++] = l;
        }

        for (int l = 0; l < ints.length; l++) {
            int target = ints[l];
            for (int m = 0; m < String.valueOf(target).length(); m++) {
                int unit = Integer.parseInt(String.valueOf(String.valueOf(ints[l]).charAt(m)));
                if (unit == k)
                    answer ++;
            }

        }
        return answer;
    }
}

테스트 1 〉	통과 (63.31ms, 99.4MB)
테스트 2 〉	통과 (0.04ms, 74.1MB)
테스트 3 〉	통과 (0.04ms, 77.7MB)
테스트 4 〉	통과 (14.15ms, 81.3MB)
테스트 5 〉	통과 (6.70ms, 78.9MB)
테스트 6 〉	통과 (0.16ms, 71.9MB)
테스트 7 〉	통과 (1.86ms, 80.1MB)
테스트 8 〉	통과 (22.10ms, 96.1MB)

 

 

다른 사람 풀이 1

1. i부터 j까지 입력값을 전부 String으로 더하기 연산합니다.

2. str의 길이에서 k가 들어있는걸 replace로 제거한 만큼 길이를 빼기 연산합니다.

class Solution {
    public int solution(int i, int j, int k) {
        String str = "";
        for(int a = i; a <= j; a++) {
            str += a+"";
        }

        return str.length() - str.replace(k+"", "").length();
    }
}

테스트 1 〉	통과 (4994.22ms, 380MB)
테스트 2 〉	통과 (14.84ms, 88.5MB)
테스트 3 〉	통과 (13.85ms, 78.3MB)
테스트 4 〉	통과 (109.83ms, 189MB)
테스트 5 〉	통과 (33.33ms, 100MB)
테스트 6 〉	통과 (11.91ms, 83.1MB)
테스트 7 〉	통과 (19.08ms, 73.9MB)
테스트 8 〉	통과 (400.93ms, 375MB)

 

 

다른 사람 풀이 1과 내 코드 풀이 비교

 

코드길이는 2번째 코드가 더 짧지만, 속도나 메모리 면에서 내 코드가 훨씬 더 성능이 좋은 걸 알 수 있습니다.

그 이유는 2번째 풀이에서는 for문 만큼 더하기 연산을 해줘서 String인스턴스가 계속 생성 되서 메모리에 올라갑니다.

이 코드는 문자열 연산 및 검색 연산을 사용하고 있기 때문에 첫번째 풀이에 비해 성능이 떨어질 가능성이 있습니다. 특히 문자열 연산은 내부적으로 메모리를 재할당하고 문자열을 복사하는 과정이 필요하므로 성능 면에서 비효율적일 수 있습니다.

코드의 성능은 입력의 크기에 따라 달라지며, 문자열 연산이 많이 발생하게 되는 경우 성능 저하가 발생할 수 있습니다. 예를 들어 i가 1이고 j가 10000인 경우, 1부터 10000까지의 숫자를 모두 문자열로 이어붙이면 매우 큰 문자열이 생성되고, 문자열 검색 및 치환 연산 역시 큰 문자열에서 이루어지므로 성능 문제가 발생할 수 있습니다.

따라서, 주어진 문제를 해결하기 위해서는 문자열 연산을 최소화하고, 숫자 자체의 속성을 이용하여 효율적으로 처리하는 방식을 사용하는 것이 좋습니다. 처음에 제시한 코드가 여전히 성능과 가독성 면에서 더 우수한 선택일 가능성이 높습니다.

 

 

다른 사람 풀이 2

 

1. 중첩 반복문을 통해서 i부터 j까지 숫자를 10으로 나눈 나머지가 k와 일치하다면 +를 해줍니다.

2. tmp가 0이 아닐 경우에만 분기처리를 하게 됩니다.

3. tmp가 10의 자리 수 이상이 될 경우에는 나누기 10해서 일의 자리수를 다시 체크합니다.

class Solution {
    public int solution(int i, int j, int k) {
        int answer = 0;

        for (int num = i; num <= j; num++){
            int tmp = num;
            while (tmp != 0){
                if (tmp % 10 == k)
                    answer++;
                tmp /= 10;
            }
        }
        return answer;
    }
}

테스트 1 〉	통과 (4.61ms, 78.8MB)
테스트 2 〉	통과 (0.01ms, 77.6MB)
테스트 3 〉	통과 (0.02ms, 76.7MB)
테스트 4 〉	통과 (0.91ms, 64.8MB)
테스트 5 〉	통과 (0.75ms, 79MB)
테스트 6 〉	통과 (0.02ms, 71.1MB)
테스트 7 〉	통과 (0.08ms, 79MB)
테스트 8 〉	통과 (1.94ms, 69.7MB)

tmp = 1
1 나누기 10의 나머지는 = 1 
1 나누기 10의 몫은 = 0 
tmp = 2
2 나누기 10의 나머지는 = 2 
2 나누기 10의 몫은 = 0 
tmp = 3
3 나누기 10의 나머지는 = 3 
3 나누기 10의 몫은 = 0 
tmp = 4
4 나누기 10의 나머지는 = 4 
4 나누기 10의 몫은 = 0 
tmp = 5
5 나누기 10의 나머지는 = 5 
5 나누기 10의 몫은 = 0 
tmp = 6
6 나누기 10의 나머지는 = 6 
6 나누기 10의 몫은 = 0 
tmp = 7
7 나누기 10의 나머지는 = 7 
7 나누기 10의 몫은 = 0 
tmp = 8
8 나누기 10의 나머지는 = 8 
8 나누기 10의 몫은 = 0 
tmp = 9
9 나누기 10의 나머지는 = 9 
9 나누기 10의 몫은 = 0 
tmp = 10
10 나누기 10의 나머지는 = 0 
10 나누기 10의 몫은 = 1 
tmp = 11
11 나누기 10의 나머지는 = 1 
11 나누기 10의 몫은 = 1 
tmp = 12
12 나누기 10의 나머지는 = 2 
12 나누기 10의 몫은 = 1 
tmp = 13
13 나누기 10의 나머지는 = 3 
13 나누기 10의 몫은 = 1

 

다른 사람 풀이2 와 내 코드 풀이 비교

 

메모리나 성능적으로 다른 사람 풀이2가 성능이 더 좋은 것 같아서 GPT한테 물어봤습니다.

내가 푼 풀이는 숫자를 문자열로 변환하여 각 자리 숫자를 추출하여 비교하는 방식을 사용하고 있습니다.
다른 사람 풀이 2는 반복문을 사용하여 숫자의 각 자리를 추출하고 비교하는 방식을 사용하고 있습니다.

알고리즘 성능을 비교해보면 다음과 같습니다:


내가 푼 풀이:
주어진 범위 내의 숫자를 먼저 배열로 생성한 후에, 각 숫자를 문자열로 변환하여 각 자리 숫자를 추출하고 비교합니다.이 코드는 주어진 범위 내의 숫자 개수와 무관하게 이미 배열에 모든 숫자가 저장되어 있으므로 내부 반복문의 실행 횟수는 상수입니다.

다른 사람 풀이2:
주어진 범위 내의 각 숫자에 대해 자리별로 숫자를 추출하고 비교합니다.이 코드는 주어진 범위의 숫자 개수에 따라서 내부 반복문의 실행 횟수가 결정됩니다. 예를 들어 i=1, j=10000일 경우 1부터 10000까지의 숫자에 대해 각 숫자의 각 자리를 검사하므로 시간 복잡도가 크게 됩니다.

따라서, 첫 번째 코드가 일반적으로 성능 면에서 우수합니다. 하지만 성능 차이가 크지 않은 경우도 있을 수 있으며, 작은 범위의 숫자에 대해서는 오히려 두 번째 코드가 더 나은 성능을 보일 수 있습니다. 코드의 가독성이나 유지보수 측면에서도 가독성과 유지보수 측면에서는 첫 번째 코드가 더 나은 특성을 가지고 있습니다.

1. 모듈화와 분리: 첫 번째 코드는 숫자를 생성하는 부분과 추출하고 검사하는 부분을 분리하고 있습니다. 숫자 생성 부분이 따로 존재하기 때문에 추후 이 코드를 다른 문제에서 재사용하기 쉬울 것입니다.

2. 가독성: 첫 번째 코드는 숫자 추출과 검사 과정이 명확하게 구분되어 있습니다. 각 단계의 로직이 분리되어 있기 때문에 코드를 읽기 쉽습니다.

3. 유연성: 숫자를 문자열로 변환하여 처리하는 접근 방식은 숫자의 다양한 속성을 처리하는 데 더 유연성을 제공할 수 있습니다. 예를 들어, 자리수가 아닌 특정 숫자 패턴을 찾는 등의 변형이 더 쉽게 적용될 수 있습니다.

4. 배열 활용: 숫자들을 배열로 미리 저장하여 처리하므로, 더 복잡한 데이터 구조로 확장하거나 관리하는 것이 더 용이합니다.

따라서, 첫 번째 코드가 가독성과 유지보수 측면에서 더 나은 선택으로 보입니다. 코드의 재사용성, 수정 및 확장 용이성, 그리고 코드 이해를 위한 구조화 측면에서 첫 번째 코드가 더 우수합니다.

 

 

다른 사람 풀이 3

 

1. i~j까지 주어진 범위 내의 각 숫자를 +""를 통해 바로 문자열로 변환합니다.

2. 각 str에 대한 character 에 아스키코드 '0'를 빼서 int형으로 만든 뒤 k와 일치하다면 +를 해줍니다.

문자열에서 각 자리의 문자를 숫자로 변환하기 위해서는 문자의 ASCII 코드 값을 숫자와의 차이를 이용하여 변환합니다.
예를 들어, ASCII 코드에서 숫자 '0'의 값은 48이고, 숫자 '1'의 값은 49, '2'의 값은 50이 됩니다. 이러한 값의 차이를 이용하여 문자를 해당 숫자로 변환할 수 있습니다. 따라서 '1' - '0' 은 49 - 48이므로 결과는 1이 됩니다. 마찬가지로 '2' - '0'은 50 - 48이므로 결과는 2가 됩니다.

class Solution {
    public int solution(int i, int j, int k) {
        int answer = 0;

        for(int n = i; n<=j; n++){

            String str = n+"";
            for(int l = 0; l<str.length(); l++){
                if(str.charAt(l)-'0'==k) answer++;
            }

        }

        return answer;
    }
}

테스트 1 〉	통과 (26.37ms, 87.3MB)
테스트 2 〉	통과 (5.01ms, 83.7MB)
테스트 3 〉	통과 (6.29ms, 75.3MB)
테스트 4 〉	통과 (16.21ms, 77.1MB)
테스트 5 〉	통과 (11.74ms, 74.6MB)
테스트 6 〉	통과 (6.28ms, 73.5MB)
테스트 7 〉	통과 (7.44ms, 76.1MB)
테스트 8 〉	통과 (15.24ms, 74.6MB)

 

다른 사람 풀이3 와 내 코드 풀이 비교

속도나 메모리가 내 코드랑 가장 비슷하지만 다른 사람 풀이 중에 제일 나은 것 같아서 GPT한테 물어봤습니다.

문자열 연산으로 인해 입력이 커지면 성능 저하가 있지만, 코드 가독성과 이해측면에서는 훨씬 낫다고 합니다.

 

예를 들어 중첩 반복문 내부 for문에서 String으로 변환해서 자릿수만큼만 도는게 성능이 좋다고 생각했는데,

음..내 생각에는 다른 사람 풀이 3 코드의 성능이 제일 좋은 것 같은데 더하기 연산때문에 GPT가 아니라고 합니다.

두번째 코드(다른 사람 풀이3)는 문자열 변환 후 각 자리 숫자를 비교하는 방식을 사용합니다. 따라서 앞서 언급한 대로 문자열 연산 및 비교 연산이 반복되므로, 성능 면에서는 첫 번째 코드(내가 푼 풀이)와 유사한 성능을 가질 것으로 예상됩니다. 즉, 입력 범위가 클 경우에는 성능 저하의 가능성이 있습니다.

그러나 두번째 코드는 코드의 가독성을 향상시킨 특징을 가지고 있습니다. 내부 for 루프에서 문자열의 각 자리를 직접 처리하고, 각 단계가 명확하게 구분되어 있습니다. 이로 인해 코드를 읽기 쉽고 이해하기 쉽습니다.

따라서, 알고리즘 성능과 코드의 가독성 간에는 trade-off가 있을 수 있습니다. 알고리즘 성능을 우선시하는 경우에는 첫 번째 코드와 유사한 방식이 더 나을 수 있지만, 코드의 가독성과 이해성을 중요시하는 경우에는 두 코드와 같은 방식을 선택할 수 있습니다.

4번째 코드 역시 주어진 범위 내의 숫자를 문자열로 변환하여 각 자리를 순회하며 특정 숫자와 비교합니다. 여기서 문자열 연산과 비교 연산이 중복해서 수행되는데, 각 숫자에 대해 문자열을 생성하고 각 자리를 비교하는 과정이 반복됩니다.

코드 내에서 가장 느린 연산은 문자열 연산과 문자 비교 연산입니다. 각 숫자마다 문자열을 생성하고 각 자리를 비교하는 과정은 연산 비용이 큽니다. 따라서, 입력 크기가 증가할수록 문자열 연산의 비용이 기하급수적으로 증가하게 되어 성능 저하의 가능성이 있습니다.

비교적 작은 입력 범위에서는 성능 차이가 크게 나타나지 않을 수 있지만, 입력 범위가 커질 경우 문자열 연산이 느려질 가능성이 있습니다. 이에 비해 첫 번째 코드는 입력 범위에 관계 없이 미리 숫자를 배열에 저장하여 각 숫자를 변환하거나 비교할 필요가 없기 때문에 상수 시간 내에서 처리 가능하므로 성능 면에서 이점을 가집니다.

 

 

String.valueOf()  VS   concatenation with empty String

그렇다면 String.valueOf()랑 +"" 둘 중에 성능이 더 좋은건 뭘까

String.valueOf() 메서드를 사용하는 것이 문자열을 직접 생성하는 것보다 성능적으로 더 나을 수 있습니다.

String.valueOf() 메서드는 매개변수로 전달된 값을 문자열로 변환해주는 메서드입니다. 이 메서드는 내부적으로 입력된 값을 문자열로 변환하는데, 문자열 연산을 통해 새로운 문자열을 생성하지 않고, 문자열 풀(String Pool)에서 이미 존재하는 문자열을 활용할 수 있습니다.

반면에 코드 내에서 숫자를 문자열로 변환하는 과정은 새로운 문자열을 생성하는 연산을 수행하므로, 문자열 연산 비용이 큽니다.
따라서, 성능을 고려한다면 String.valueOf() 메서드를 사용하는 것이 문자열을 직접 생성하는 것보다 더 효율적일 수 있습니다. 그러나 성능 측정을 통해 실제로 얼마나 차이가 나는지 확인하는 것이 중요합니다.

 

참고 링크 : 

https://stackoverflow.com/questions/7752347/string-valueof-vs-concatenation-with-empty-string

String valueOf vs concatenation with empty string

https://frogand.tistory.com/164

[Java] String valueOf vs concatenation with empty string / The difference between String.valueOf and + ""

https://stackoverflow.com/questions/45386769/string-valueofsomevar-vs-somevar

String.valueOf(someVar) vs ("" + someVar)