2023.08.18 TIL - 알고리즘 문제 - 1

짝수와 홀수

프로그래머스

입력이 홀수일 때 "Odd", 짝수일 때 "Even"을 출력하는 함수를 작성하는 문제이다.

class Solution {
    public String solution(int num) {
        String answer = num%2==0?"Even":"Odd";
        return answer;
    }
}

%를 사용해 2로 나눈 나머지가 0일 때 "Even", 1일 때 "Odd"를 출력하게 했다.

간단한 조건문 문제로, if else를 사용해도 문제 없이 동작한다.

 

 

평균 구하기

어떤 배열의 평균값을 출력하는 문제이다.

class Solution {
    public double solution(int[] arr) {
        double answer = 0;
        for (int a : arr){
            answer += a;
        }
        return answer/arr.length;
    }
}

arr 안의 요소를 모두 합한 뒤, arr의 길이로 나누면 쉽게 문제를 풀 수 있다.

다른 정답에서 stream을 사용해 Arrays.stream(array).average() 형태로 풀었는데, stream에 대한 이해가 필요할 듯하다.

 

 

자릿수 더하기

주어진 자연수의 모든 자릿수를 더하는 문제이다.

import java.util.*;

public class Solution {
    public int solution(int n) {
        int answer = 0;
        while(n!=0){
            answer +=n%10;
            n/=10;
        }
        return answer;
    }
}

 

 

주어진 정수 n을 %를 이용해 10으로 나눈 나머지를 계속 더하는 형태로 어렵지 않게 풀었다.

n을 String 타입으로 변환하고 split을 활용해 분리한 후, 요소를 int로 변환해 더하는 방법도 생각해 보았는데, 실제로 그렇게 푼 사람들도 있었다.

 

 

약수의 합

주어진 자연수의 약수의 합을 더하는 문제이다.

import static java.lang.Math.floor;
import static java.lang.Math.sqrt;
import java.util.*;

class Solution {
    public int solution(int n) {
        int answer = 0;
        List<Integer> arr = new ArrayList<>();
        double root = sqrt(n);
        for (int i = 1; i<root;i++){
            if (n%i==0){
                arr.add(i);
            }
        }
        int len = arr.size();
        for(int i=0;i<len;i++){
            arr.add(n/arr.get(i));
        }
        if (floor(root)==root)
            arr.add((int)root);
        for (int i:arr){
            answer+=i;
        }
        return answer;
    }
}

먼저 약수에 대한 이해가 필요하다. n의 약수의 갯수는, n의 제곱근을 기준으로 그보다 작은 약수의 갯수와 큰 약수의 갯수가 일치한다. 또한, 그보다 작은 약수의 집합을 a1, a2,...,ax 그보다 큰 약수의 집합을 b1, b2,...,bx(둘 다 숫자가 작은 순서대로 나열한 것)이라 했을 때, n = ay*b(x-y)와 일치하기에 작은 약수의 집합을 알면 큰 약수의 집합도 알 수 있다.

 

먼저 i가 1부터(보통 for문을 쓸때처럼 0부터를 사용하면 ZeroDivisionException이 뜬다.) n의 제곱근까지를 n으로 나누어 작은 약수의 집합을 구한다. 또한, n을 이들에서 각각 나누어 큰 약수의 집합을 구한다. 그렇게 구한 집합의 요소를 모두 더하는 형태로 구성했다.

i가 n의 제곱근 이하로 for문을 지정하게 될 경우 n이 제곱수일 때를 한번에 판별할 수 있지만, 큰 약수를 구할 때 n의 제곱근이 한번 더 들어가기에 n의 제곱근 미만으로 지정한 후, n이 제곱수일 경우는 n의 제곱근이 자연수일 때를 판별해 따로 넣는 방향으로 제작하였다.

 

i를 1부터 n까지 모두 계산하여도 문제는 풀 수 있지만, 이 경우 시간복잡도는 n이 된다. 일부 문제에서 시간 제한을 둘 경우 시간 초과가 출력되었던 경험이 있어 조금 더 빠른 출력을 위해 n^0.5의 시간복잡도를 갖도록 작성하였다.

 

 

나머지가 1이 되는 수 찾기

n을 그보다 작은 수로 나누었을 때 나머지가 1이 되는 가장 작은 수를 찾는 문제이다.

class Solution {
    public int solution(int n) {
        int answer = 1;
        while(n%answer!=1) {
            answer++;
        }
        return answer;
    }
}

문제에서, 답이 항상 존재함은 증명될 수 있음을 알려주어 while을 통해 answer의 조건을 만족할 때까지 실행하는 코드를 작성하였는데, 만약 이것이 증명할 수 없다면 for문이나 break;를 통해 반복을 그만두는 코드를 추가해야 할 필요가 있다.

 

 

x만큼 간격이 있는 n개의 숫자

x부터 시작해 x씩 증가하는 숫자를 n개 지니는 리스트를 출력하는 문제이다.

class Solution {
    public long[] solution(int x, int n) {
        long[] answer = new long[n];
        answer[0]=x;
        for (int i = 1; i < n; i++) {
            answer[i] = answer[i-1] + x;
        }
        return answer;
    }
}

해당 리스트는 초기값이 x이고 공차가 x인 등차수열과 동일하기에, 초기값에 x를 대입한 후 이후 이전 배열 요소에서 x를 더해주는 것으로 문제를 해결하였다.

x를 i+1번 곱해준 수를 대입해도 동일하게 문제를 해결할 수 있다.

 

 

자연수 뒤집어 배열로 만들기

주어진 자연수의 각 자릿수를 순서를 뒤집어 배열로 만드는 문제이다.

class Solution {
    public int[] solution(long n) {
        String[] str = Long.toString(n).split("");
        int len = str.length;
        int[] answer = new int[len];
        for(int i = 0;i<len;i++)
            answer[i] = Integer.parseInt(str[len-i-1]);
        return answer;
    }
}

자릿수 n을 String으로 바꾼 후, split을 활용해 분리하였다. 이를 for문을 활용해 역순으로 집어넣는 행위를 반복해 문제를 해결하였다.

자릿수 합 문제처럼 %를 활용해 10으로 나눈 나머지를 순서대로 저장해도 같은 결과를 얻을 수 있을 것으로 예상했으나, 문제를 해결할 수 없었다. 확인한 결과, long 타입의n을 계산한 결과를 int 타입에 넣을 때 에러가 날 것을 예상해 (int)n%10 형태로 값을 넣어 주었는데, 이것이 n%10을 먼저 계산한 후 형변화한 것이 아닌 n을 형변화한 후 %10을 계산해 생긴 오버플로우가 일으킨 문제였다. (int)(n%10) 형태로 입력한 결과 정상적으로 동작하였다.