1937년 Collatz란 사람에 의해 제기된 이 추측은, 주어진 수가 1이 될 때까지 다음 작업을 반복하면, 모든 수를 1로 만들 수 있다는 추측입니다. 작업은 다음과 같습니다.

1-1. 입력된 수가 짝수라면 2로 나눕니다. 
1-2. 입력된 수가 홀수라면 3을 곱하고 1을 더합니다. 
2. 결과로 나온 수에 같은 작업을 1이 될 때까지 반복합니다. 

예를 들어, 주어진 수가 6이라면 6 → 3 → 10 → 5 → 16 → 8 → 4 → 2 → 1 이 되어 총 8번 만에 1이 됩니다. 위 작업을 몇 번이나 반복해야 하는지 반환하는 함수, solution을 완성해 주세요. 단, 주어진 수가 1인 경우에는 0을, 작업을 500번 반복할 때까지 1이 되지 않는다면 –1을 반환해 주세요.

[제한사항]

• 입력된 수, num은 1 이상 8,000,000 미만인 정수입니다.

[입출력 예]

추측) 

만약 주어진 수가 {

- 1 이면 return할 카운트 값에 0 대입 

- 아니면 while문을 주어진 수가 1이 아직 아니라면 계속 돌린다 {

      만약 카운트 값이 500이면 -1를 카운트에 대입한다.

      만약 주어진 수가 {

       -짝수라면 2로 나누기 값을 다시 수에 대입

       -홀수라면 3을 곲하고 1을 더한다 값을 다시 수에 대입

       }

       return할 카운트 값을 올린다. 

    }

}

소스코드) 

* 1차) 실패 - 마지막 테스트 값이 500을 넘지 않는다

public int solution(int num) {
    int answer = 0;
    while(num!=1){
        if(answer == 500){
            answer = -1;
            break;
        }
        if(num%2 == 0){
            num = num/2;
        } else {
            num = (num*3)+1;
        }
        System.out.println(num);
        answer++;
    }
    return answer;
}

* 2차) 성공 [메모리: 76.9 MB, 시간: 0.03 ms]

public int solution(int num) {
    int answer = 0;
    long longNum = num;

    while(longNum!=1){
        if(answer == 500){
            answer = -1;
            break;
        }

        if(longNum%2 == 0){
            longNum = longNum/2;
        } else {
            longNum = (longNum*3)+1;
        }

        answer++;
    }
    return answer;
}

리뷰) 

1차) 뭐에서 틀렸지 고민하다가 num을 입출력 해보니 중간에 음수가 나온다 왜 값자기 음수??? 

일단 오래 고민만하다 입출력을 넣은거라 입출력의 중요성을 깨닫는다. 입출력은 정말 자주해보자.

음수 직전에 나온 수를 인자값으로 주어 왜 음수가 나오는지 먼저 확인한다.

아! 값이 느닷없이 -로 바뀐다. int로 표현 할 수 있는 값을 오버해서 그렇게 된 걸까??? num의 타입을 바꿔서 실행해보자 

2차) int로 표현할 수 있는 범위가 넘어가면서 값이 바뀐게 맞았다!

추측) 

배열을 정리해 index[0] 값을 제외한 나머지 값을, arr 배열보다 1개 작은 배열에 넣으면 될거라고 생각하려는데

return값을 보니까 배열의 위치가 변하면 안된다. 

그럼 최소값을 넣을 변수를 하나와 인덱스 값을 저장할 변수 하나를 선언하고

for문으로 각 인덱스 값을 최소값과 비교해 인덱스 값이 더 작으면 최소값을 갱신한다. (다만 처음 최소값이 0으로 시작하니까 배열의 첫번째 인덱스 값은 최소값을 필수로 갱신한다. 인덱스 값은 갱신하지 않는다.)

그리고 최소값을 갱신하는 순간의 인덱스의 값을 인덱스 값을 저장할 변수에 갱신 시킨다.

분기점1) 배열이 애초에 한개일 때 

배열이 하나일때 위 과정을 과정을 거치면 인덱스값에 저장이 안되어 있을 것이다. (int로 선언하니 0값이 되어 있고 이게 인덱스 0이 최소값일 경우와 충돌할 것 쉽게 배열 길이를 체크하면 되는데 왜 그랬어..)

그것이 true라면 return변수에 바로 -1를 넣은 new 배열 변수를 선언한다. 

분기점 2) 배열이 두개 이상일 때

첫번째 for문이 종료되면 arr배열보다 한개 작은 배열을 생성해 

다시 for문을 열어 arr배열로 부터 값을 하나씩 받는 식을 반복하는데 이때, 아까전에 저장한 인덱스 값과 동일한 인덱스에서는 continue문으로 넘어가도록 한다.

분기점 종료하면 값을 return

소스코드) 

* 1차) 실패 - 장렬한 런타임 에러 러쉬

public int[] solution(int[] arr) {
    int[] answer = new int[1];
    int minNum = 0;
    int exportIndex = 0;
    for (int i = 0; i < arr.length; i++) {
        if (i == 0) {
            minNum = arr[i];
        } else if (minNum > arr[i]) {
            minNum = arr[i];
            exportIndex = i;
        }
    }
    if (arr.length == 1) {
        answer[0] = -1;
    } else {
        answer = new int[arr.length - 1];
        int cnt = 0;
        for (int j = 0; j < answer.length; j++) {
            if (j != exportIndex) {
                answer[j] = arr[cnt];
                cnt++;
            } else {
                cnt++;
                continue;
            }
        }
    }

    return answer;
}

* 2차) 성공 [메모리: 76.7 MB, 시간: 0.27 ms]

public int[] solution(int[] arr) {
    int[] answer = {};
    int minNum = 0;

    if(arr.length == 1){
        answer = new int[1];
        answer[0] = -1;
    } else {
        for (int i=0; i<arr.length; i++){
            if(i==0){
                minNum = arr[i];
            } else {
                minNum = Math.min(minNum, arr[i]);
            }
        }

        ArrayList<Integer> num_arr = new ArrayList<Integer>();
        for (int j=0; j<arr.length; j++){
            if(arr[j] == minNum){
                continue;
            } else {
                num_arr.add(arr[j]);
            }
        }

        answer = new int[num_arr.size()];
        for (int k=0; k<answer.length; k++){
            answer[k] = num_arr.get(k);
        }
    }
    return answer;
}

리뷰) 

1차) for문과 if문을 남발한 케이스. IDE에서는 테스트 결과값은 동일하게 나오는데 제출과정의 테스트에서 전부 런타임에러가 뜨며 실패한 코드다. 이게 왜 예외가 발견됬을까 다시 한번 분석해야겠다. (오늘 코드리뷰 시간 지나고 한번 보는걸로)

2차) ArrayList를 사용해서 개선해 보려고 했는데 결국 for문은 3개가 됬다. 

+ 복잡도를 올리는 건 중첩된 for문이 특히 올린다 이를 피하는 방법이라면 for문 자체를 여러번 쓰는 것에 대해 너무 민감하게 생각하지 말아도 된다고..

+ 알고리즘 문제풀이 세션에서 변수명에 신경써야 한다고 했다. 변수명을 신경쓰지 않으면 코드가 길어졌을 때 더 번거로워질 수 있다고 하니 변수명 신경쓰는 버릇을 들이자.  

[제한사항]

• n은 1이상, 50000000000000 이하인 양의 정수입니다.

[입출력 예]

추측) 

임의의 양의 정수임을 판단하려면 for문으로 2에서부터 n까지 차례로 숫자를 제곱 시키면서 n과 결과값을 비교 (그런데 제한사항 숫자가 너무 큰데 이 방법이 괜찮을까?? 제곱근을 구하는 함수가 있을거 같다.). 동일한 값이 나오는 순간  그값에 +1하고 제곱하여 return할 값에 저장 및 break;하고 n까지 다달았음에도 출력값이 없다면 -1을 return할 값에 저장

소스코드) 

• 1차) 실패 - 역시 시간초과 에러!

class Solution {
    public long solution(long n) {
        long answer = 0;
        for (int num=2; num<n; num++){
            if(num*num==n){
                answer = (num+1)*(num+1);
                break;
            }
        }
        if(answer==0){answer=-1;}
        return answer;
    }
}

• 2차) 실패 - 순간 약수 개념을 집어넣어서 이상하게 된 코드;

class Solution {
    public long solution(long n) {
        long answer = 0;
        double root = Math.sqrt((double)n);
        int intRoot = (int) root;
        if(intRoot != 1 && intRoot != n ){
            answer = (long) Math.pow(root+1,2);
        } else {
            answer = -1;
        }
        return answer;
    }
}

• 3차) 성공 - 다시 제대로 개념을 잡고 푼 코드 [ 성능 : 메모리: 77.9 MB, 시간: 0.04 ms ]

public long solution(long n) {
    long answer = 0;
    double root = Math.sqrt((double)n);
    if(root - (int)root == 0){
        answer = Double.valueOf(Math.pow(root+1,2)).longValue();
    } else {
        answer = -1;
    }
    return answer;
}

리뷰) 

1차) 역시 숫자가 커지면 너무 효율성이 안좋을 거 같다는 생각했던 대로 시간 초과가 떠버렸다. 

2차) - 함수를 이용해 풀어보자!

Math클래스를 사용하자! 제곱근에 관련해서는 Math.sqrt와 Math.pow를 이용해 구하면 될거 같다.

java.lang.Math 클래스는 수학 계산에 사용할 수 있는 메소드를 제공하고 있는데 Math 클래스가 제공하는 메소드는 모두 *정적(static)이므로 Import나 Math클래스 선언 없이 바로 사용이 가능하다. 

Math.pow(x, y)는 double형태로 인자로해서 x를 y만큼 제곱해 double형으로 값을 출력한다.  

Math.sqrt(x)을 사용하면 되는데 sqrt라는건 Square root의 약자로 제곱근을 의미한다. 인자로 받은 x에 √(루트)를 씌워 값을 내보내는데  sqrt역시 double형으로 값을 출력한다. 

문제 자체가 정수 제곱근을 구하는 거니 제곱근을 정수화시켜 1 또는 n값 그 자체가 나오는게 아니면 (여기가 문제 였네 왜 소수 개념이 왜 들어갔지??) 정수 제곱근이 도출된다. 

3차) - 어디서 예외가 떴을까? 그리고 long > double > int > long으로 형변환하는데 이걸 줄일순 없을까?

왜 갑자기 소수개념을 넣었지??? 해당 내용은 삭제하자.

다시 원점으로 생각하면 이 문제는 정수 제곱근을 판별하는 문제가 제곱근에서 정수가 나오지 않았다면 정답이 아닌것.

그럼 제곱근에서 정수값을 빼서 소수점이 나온다면 그건 정수 제곱근이 아니니 -1을 넣어주고 맞다면 제곱근에 +1을 해 다시 제곱해 주어 출력한다.

+ 추가로 공부해봐야할 링크

Math클래스

static의 개념

[제한사항]

• n은 1이상 8000000000 이하인 자연수입니다.

[입출력 예]

추측) 

숫자 그대로 배열을 만든다 (문자열은 문자별로 바로 array만들어 주는 함수가 있던데 int는 없을까?). 배열을 정리한다. 그리고 for문으로 하나씩 출력해 하나의 String변수에 += 하고 최종적으로 나온 문자열을 다시 long형태로 바꿔준다.

소스코드) 

* 1차 - 실패) 런타임 에러와 예외발생

import java.util.*;
class Solution {
    public long solution(long n) {
      
        long answer = 0;
        
        int numLen = 0;
        int num1 = (int) n;
        while(num1 > 0){
            num1 /= 10;
            numLen++;
        }
        
        int[] num_arr = new int [numLen];
        for(int i=0; i<numLen; i++){
            num_arr[i] = (int) (n%10);
            n /= 10;
        }
        
        Arrays.sort(num_arr);
        String merge = "";
        for(int j=numLen; j> 0; j--){
            merge += Integer.toString(num_arr[j-1]);
        }
        
        answer = Long.parseLong(merge);
        return answer;
    }
}

* 2차 - 성공) 그러나 비효율

import java.util.ArrayList;
import java.util.Comparator;
class Solution {
    public long solution(long n) {
      
        long answer = 0;
        
        ArrayList<Integer> num_arr = new ArrayList<Integer>();
        
        for(int i=0; 0<n; i++){
            num_arr.add((int) (n%10));
            n /= 10;
        }
        
        num_arr.sort(Comparator.naturalOrder());
        String merge = "";
        int len = num_arr.size();
        for(int j=0; j<len; j++){
            merge += Integer.toString(num_arr.get(len-j-1));
        }
        
        answer = Long.parseLong(merge);
        return answer;
    }
}

* 3차 - 성공) 문자열 배열 정렬

long answer = 0;

char[] num_arr = Long.toString(n).toCharArray();       
Arrays.sort(num_arr);

String merge = "";
int len = num_arr.length;
for(int j=0; j<len; j++){
    merge += num_arr[len-j-1];
}

answer = Long.parseLong(merge);
return answer;

리뷰) 

숫자 자릿수를 그대로 배열해주는 함수는 Stream이라는 데이터를 다루기 위한 API를 사용하는 것이 있는 데 아직 내가 사용하기엔 기본적인 지식이 부족해서 일단은 존재는 알아두고 이후 객체등 좀더 공부가 되었을때 사용해보자.

숫자 그대로 배열을 만드는 건 지금 상황에서 넘기고, for문으로 n값을 받은 다른 int값에 10을 계속 /= 대입을 하면서 count수를 올린다. 이 count는 자릿수에 해당한다. 이 자릿수를 가지고 배열을 생성.

그 배열의 길이 만큼 자리마다의 수를 10으로 나눈 나머지로 구하며 배열을 채우고 이 배열을 정렬한다. 

이후에 String변수를 만들어 for문에서 역순으로 받아오는 index값을 추가해 문자열을 완성한다.

이를 long값으로 형변환 시켜서 최종적으로 반환한다.

하는 방식으로 시도했는데 런타임에러와 예외가 발생했다

2차) ArrayList를 사용하면서 for문을 하나 줄일 수 있었다.  

3차) 아! 문자도 배열된다는 걸 왜 잊고 있었을까. 문자로 만들어서 배열까지 작업한다면 1차 시도한거에서 for문을 2개나 줄일수 있게된다. 

[제한사항]

• n은 10,000,000,000이하인 자연수입니다.

[입출력 예]

추측) 

일단 숫자를 문자열로 바꾸고 문자열 하나하나로 배열에 넣는다. 배열 길이 값을 가지고 return할 변수를 생성하고, 숫자를 문자로 바꿔 넣어뒀던 배열을 for으로 뒤에서 부터 하나씩 출력해 return할 변수의 0번부터 넣어주고 return!

소스코드) 

* 1차 

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

* 2차 

class Solution {
    public int[] solution(long n) {
        
        String numString = Long.toString(n);
        int numLen = numString.split("").length;
        int[] answer = new int[numLen];
        for(int i=0; i<numLen; i++){
            answer[i] = (int) (n % 10);
            n /= 10;
        }
        return answer;
    }
}

리뷰) 

형 변환하는 함수가 자꾸 헷갈린다. 한번 정리해서 잘 기억하도록 하자. 

처음엔 배열을 또다른 배열로 거꾸로 값을 옮기면서 String을 int로 바꾸는 방식을 사용했는데 형변환을 안하고 싶어 도전했으나 결론적으로는 long타입에서 int형태로 바꿔줘야하는 형변환이 일어난다.

그렇다면 String > int로 바꾸는 것이 나을까? long에서 > int로 바꿔주는게 더 효율적인 건가?

내일 기술매니저님께 한번 물어보자.