JAVA 알고리즘 : 10진수에서 2진수 변환 후 출력되는 1의 최대 연속자릿수 구하기

스터디사이트 : https://www.hackerrank.com

JAVA 알고리즘 : 10진수에서 2진수 변환 후 출력되는 1의 최대 연속자릿수 구하기

※ 코딩실습 - 조건

• 10진수를 입력 받고 2진수로 변환을 한다.
• 변환된 2진수를 놓고 볼때, 1이 연속해서 출력되는 자리 중 제일 길게 1이 연속적으로 출력되는 자릿수가 몇자리인지 출력하기.

입력 1

5

출력 1

1

입력 2

13

출력 2

2

디버깅

         

   1차 디버깅

        입력값을 2로 나누고 몫과 나머지를 변수로 저장한다.

        특히 나머지는 배열타입으로 저장하되, 순서가 있는 배열타입으로 저장한다.

        1) 입력값을 2로 나눠서 몫과 나머지를 저장함. 

            ex) 5 / 2 --> 몫: 2, 나머지: 1

        2) 1)의 결과로 나온 몫을 2로 나눠서 몫과 나머지를 저장함.

            ex) 2 / 2 --> 몫: 1, 나머지: 0

        3) 1)과 2)의 과정을 몫이 0이 나올때까지 반복함

            ex) 1 / 2 --> 몫: 0, 나머지: 1

        4) 반복문을 통하여 나머지가 저장된 배열을 순차적으로 확인해 보면서,

            1을 발견하면, 연속자릿수라는 것을 감지하는 변수를 써서 1씩 더한다.

            연속자릿수를 감지하는 변수를 카운트변수라고 부르겠다.

            카운트변수가 1씩 더해지는 와중에 나머지가 0이 나온다면 0으로 초기화한다.

        5) 그런데 4)처럼하면 1의 최대연속자릿수를 가늠할 수가 없다. 중간에 최고기록이 나왔는데, 나머지가 0이 나오면 초기화되고, 

            그 최고기록을 저장할 변수가 없기 때문에 그대로 날라가 버리기 때문이다.

        6) 생각해보니 나머지를 배열에다가 한자리씩 안 집어넣어도 되겠다..

String.split() 메소드가 생각났기 때문이다..

분리자를 "0"으로 지정하면 0을 기준으로 연속된 111, 11, 11111 등이 모두 배열에 들어가서 한자리씩 차지할 것이기 때문이다.

   2차 디버깅

"난 바보였군.. 역시 한번에 번뜩이는 천재는 아니었어.." 라 생각하며 2차디버깅을 해본다 ㅋ

1차 6)에서 이야기한 대로, split("0") 을 써서 연속된 1의 값들을 String[] 배열에 저장한다.

그러려면 나머지를 String형으로 저장을 해야하고,

입력값을 2로 나눠서 나오는 나머지를 String형을 중복해서 저장시켜야 한다.

1) 입력값을 2로 나눈 나머지를 새로운 String 변수에 중복저장한다. String nameoji 라고 명명해보겠다.

ex) 5 / 2 --> 몫: 2, 나머지: 1 --> nameoji = nameoji + 나머지저장변수(int)

2) 모든 계산이 완료되면, 완성된 nameoji를 split("0") 메소드로 나눠서 새로운 String[] 배열변수에다가 연속된 1의 값들을 저장한다.

3) 반복문을 돌려서, 각 String[] 배열자리수의 길이를 뽑아내서 최대값을 출력시키면 되겠다.

그리고 그 최대값을 저장하는 변수를 따로 만들어야 할 것 같다.

준비해야 할 변수

int : 

(입력값을 나눌때 나오는) 몫, 

(입력값을 나눌때 나오는) 나머지, 

나머지 연속된 1의 값의 1위기록

String : 

나머지를 합쳐 저장하는

String[] : 

나머지 2진수 중 연속된 1의 값들을 저장하는

코딩연습 - 1

public static void main(String[] args) { // TODO Auto-generated method stub Scanner scan = new Scanner(System.in); int number = scan.nextInt(); int mok = number/2; int mod = number%2; int best; String nmj=""+mod; String[] candidates; System.out.println("나머지 : " + nmj); System.out.println("몫 : " + mok); System.out.println("--------------"); while(mok != 0){ mok = mok/2; mod = mok%2; nmj = mod + nmj; System.out.println("몫(반복) : " + mok); System.out.println("나머지(반복) : " + mod); System.out.println("총 나머지(반복) : " + nmj); } //end while candidates = nmj.split("0"); for(int i=0; i<candidates.length-1; i++){ System.out.println("배열("+ i +")" + candidates[i]); if( candidates[i].length() > candidates[i+1].length() ){ best = candidates[i].length(); }else{ best = candidates[i+1].length(); } //end if } //end for System.out.println(candidates[candidates.length-1]); } //end main()

결과 :  입력 : 7 나머지 : 1 몫 : 3 -------------- 몫(반복) : 1 나머지(반복) : 1 총 나머지(반복) : 11 몫(반복) : 0 나머지(반복) : 0 총 나머지(반복) : 011 11

입력값을 테스트로 7을 해보았다.

7의 이진수는 111인데, 110이 나온다...

왜 그러냐면

while 문에 나오는 line 15, 16이 문제였다..

line 5, 6에 나온 입력값 계산 후 저장하는 몫과 나머지는 문제가 없으나,

line 15, 16의 몫과 나머지는 

계산이된 몫을 line15에서 써먹고,

이미 한 번 써먹은 mok을 나머지로 계산하자니 해당 단계의 나머지가 저장되지 않고 그 다음 단계의 나머지가 저장이 되는 것이었다...

그렇다면 한 사이클이 계산 될 동안에 계산에 영향을 받지 않는 몫 변수를 새로 만들어야 한다는 결론이 나온다.

코딩연습 - 2

public static void main(String[] args) { // TODO Auto-generated method stub Scanner scan = new Scanner(System.in); int number = scan.nextInt(); int mok = number/2; int mod = number%2; int best=0; String[] candidates; int while_mok; /*while의 한 사이클이 진행될 동안 고정되어야 할 몫 값을 저장하는 변수*/ String nmj=""+mod; System.out.println("나머지 : " + nmj); System.out.println("몫 : " + mok); System.out.println("--------------"); while(mok != 0){ while_mok = mok/2; mod = mok%2; nmj = mod + nmj; System.out.println("몫(반복) : " + while_mok); /**/ System.out.println("나머지(반복) : " + mod); System.out.println("총 나머지(반복) : " + nmj); mok = while_mok; /*한 사이클이 끝나면 while_mok값을 mok값에 물려준다. */ } //end while candidates = nmj.split("0"); System.out.println("--------------"); System.out.println("candidates의 length : "+candidates.length); for(int i=0; i<candidates.length-1; i++){ System.out.println("배열("+ i +") - " + candidates[i]); System.out.println("배열("+ (i+1) +") - " + candidates[i+1]); if( candidates[i].length() > candidates[i+1].length() ){ best = candidates[i].length(); }else{ best = candidates[i+1].length(); } //end if } //end for System.out.println("--------------"); System.out.println("Best is : " + best); } //end main()

결과1 :  입력 - 13 나머지 : 1 몫 : 6 -------------- 몫(반복) : 3 나머지(반복) : 0 총 나머지(반복) : 01 몫(반복) : 1 나머지(반복) : 1 총 나머지(반복) : 101 몫(반복) : 0 나머지(반복) : 1 총 나머지(반복) : 1101 -------------- candidates의 length : 2 배열(0) - 11 배열(1) - 1 -------------- Best is : 2 결과2 :  입력 - 50 나머지 : 0 몫 : 25 -------------- 몫(반복) : 12 나머지(반복) : 1 총 나머지(반복) : 10 몫(반복) : 6 나머지(반복) : 0 총 나머지(반복) : 010 몫(반복) : 3 나머지(반복) : 0 총 나머지(반복) : 0010 몫(반복) : 1 나머지(반복) : 1 총 나머지(반복) : 10010 몫(반복) : 0 나머지(반복) : 1 총 나머지(반복) : 110010 -------------- candidates의 length : 3 배열(0) - 11 배열(1) -  배열(1) -  배열(2) - 1 -------------- Best is : 1

while의 한 사이클이 진행될 동안 고정되어야 할 몫 값을 저장하는 변수 int while_mok을 하나 생성시키고,

한 사이클이 끝나면 while_mok값을 mok값에 물려준다. 그래야 그 다음 단계를 넘어갈 수 있으니까..

그런데 50을 입력하니까 best란 애가 최대 연속자릿수를 못구하고 저러고 있다.. ㅋ 뭐가문젤까...

코딩연습 - 3

와 별거아닌거같은데 제대로 걸린거같다..ㅋㅋ

바로 아래 박스에 있는 이 비교하는거, 버블정렬이다..

음.. 0번째자리와 1번째자리 비교해서 0번째가 우월하면 0번째를 1등으로 추대.

1번째와 2번째 비교해서 2번째가 우월하면 1등으로 추대된 0번째와 또 비교해야한다..

근데 난 저 바로 이것을 코딩하지 않았던 거다...

Before

if( candidates[i].length() > candidates[i+1].length() ){

best = candidates[i].length();

}else{

best = candidates[i+1].length();

} //end if

After

if( candidates[0].length() > candidates[1].length() ){    ← 맨 첫번째와 두번째의 길이를 비교해서 best 를 임명한다.

best = candidates[0].length();

}else{

best = candidates[1].length();

} //end if

for(int i=2; i<candidates.length; i++){

  if( best < candidates[i].length() ){

best = candidates[i].length();

  } //end if

} //end for

public static void main(String[] args) { // TODO Auto-generated method stub Scanner scan = new Scanner(System.in); int number = scan.nextInt(); int mok = number/2; int mod = number%2; int best=0; String[] candidates; int while_mok; /**/ String nmj=""+mod; System.out.println("나머지 : " + nmj); System.out.println("몫 : " + mok); System.out.println("--------------"); while(mok != 0){ while_mok = mok/2; mod = mok%2; nmj = mod + nmj; System.out.println("몫(반복) : " + while_mok); /**/ System.out.println("나머지(반복) : " + mod); System.out.println("총 나머지(반복) : " + nmj); mok = while_mok; /**/ } //end while candidates = nmj.split("0"); System.out.println("--------------"); System.out.println("candidates의 length : "+candidates.length); //맨 첫번째와 두번째의 길이를 비교해서 best 를 임명한다. if( candidates[0].length() > candidates[1].length() ){ best = candidates[0].length(); }else{ best = candidates[1].length(); } //end if System.out.println("Best so far is : " + best); for(int i=0; i<candidates.length; i++){ System.out.printf("배열(%d) - length : %d / 내용 : %s\n", i, candidates[i].length(), candidates[i]); } //end for for(int i=2; i<candidates.length; i++){ if( best < candidates[i].length() ){ best = candidates[i].length(); } //end if } //end for System.out.println("--------------"); System.out.println("Best is : " + best); } //end main()

결과 :  입력 - 333 나머지 : 1 몫 : 166 -------------- 몫(반복) : 83 나머지(반복) : 0 총 나머지(반복) : 01 몫(반복) : 41 나머지(반복) : 1 총 나머지(반복) : 101 몫(반복) : 20 나머지(반복) : 1 총 나머지(반복) : 1101 몫(반복) : 10 나머지(반복) : 0 총 나머지(반복) : 01101 몫(반복) : 5 나머지(반복) : 0 총 나머지(반복) : 001101 몫(반복) : 2 나머지(반복) : 1 총 나머지(반복) : 1001101 몫(반복) : 1 나머지(반복) : 0 총 나머지(반복) : 01001101 몫(반복) : 0 나머지(반복) : 1 총 나머지(반복) : 101001101 -------------- candidates의 length : 5 Best so far is : 1 배열(0) - length : 1 / 내용 : 1 배열(1) - length : 1 / 내용 : 1 배열(2) - length : 0 / 내용 :  배열(3) - length : 2 / 내용 : 11 배열(4) - length : 1 / 내용 : 1 -------------- Best is : 2

결과

line 20 ~ line 35를 주목하라..

└ 나머지를 '0' 을 기준으로 배열로 저장한 candidates 변수의 길이가 1일때와 2 이상일때의 조건처리를 추가했다.

디버깅을 위한 System.out.println() 모두 걷어내고 출력한 모습.

public static void main(String[] args) { Scanner scan = new Scanner(System.in); int number = scan.nextInt(); int mok = number/2; int mod = number%2; int best=0; String[] candidates; int while_mok; /**/ String nmj=""+mod; while(mok != 0){ while_mok = mok/2; mod = mok%2; nmj = mod + nmj; mok = while_mok; /**/ } //end while candidates = nmj.split("0"); if(candidates.length==1){ best = candidates[0].length(); }else{ if( candidates[0].length() > candidates[1].length() ){ best = candidates[0].length(); }else{ best = candidates[1].length(); } //end if if(candidates.length > 2 ){ for(int i=2; i<candidates.length; i++){ if( best < candidates[i].length() ){ best = candidates[i].length(); } //end if } //end for } //end if length > 2 } //end if length==1 System.out.println(best); }

결과 :  입력 : 5 → 출력 : 1 입력 : 6 → 출력 : 2 입력 : 13 → 출력 : 2 입력 : 333 → 출력 : 2

다른 사람의 초간단 코딩..

나는 완전히 2진수 변환까지 다하고 지지고 볶았는데,

이사람은 단순하게 입력값을 2로 나눠서 나머지가 1이 나오면 s라는 변수에 1씩 더하고, 곧바로 최대 연속자릿수를 출력시키는 t변수에 사이클마다 저장 해놓는다.

사이클이 진행되다가 입력값이 나누어 떨어지면 2진수는 중간에 0이 나오므로 s의 값만 0으로 초기화를 하고 최대연속자릿수를 출력시키는 t변수에는 전혀 영향이 가지 않게 하는.. 매우 단순한 코딩이었다.

나는 뭐... 뭐지? ㅋ

public static void main(String[] args) {
    Scanner in = new Scanner(System.in);
    int n = in.nextInt();
    int rem=0,s=0,t=0;
 
    while(n>0) {
        rem=n%2;
        n=n/2;
        if(rem==1) { 
             s++;
            if(s>=t)
                t=s;
        }else{
            s=0;
        } // end if
    } //end while
    System.out.println(t);
}