[Codility] BinaryGap (JAVA)

Codility 사이트에 들어가면 기본문제로 풀어볼 수 있는 BinaryGap 테스트를 해보았다.

코딩테스트를 연습해보기 위한 첫 도전!

프로젝트로 스프링만 주구장창 쓰다가 이클립스로 쓰려니까 어색하고 기억도 가물가물했다.

(System.out.println 대신에 logger.info 써야될거 같은 기분... )

 

---

 

코딩 테스트는 자신이 원하는 프로그래밍언어를 선택해서 문제를 풀어볼 수 있다.

내가 선택한 언어는 JAVA 8

 

먼저, 영어로 된 문제를 해석해보자.

 

 

BinaryGap : Find longest sequence of zeros in binary representation of an integer.

=> 정수를 2진수로 표현했을 때 연속된 0의 가장 긴 길이를 구하시오.

---

A binary gap within a positive integer N is any maximal sequence of consecutive zeros that is surrounded by ones at both ends in the binary representation of N.

=> binary gap이란, 어떤(N) 양의 정수를 2진수로 나타냈을 때, 시작과 끝이 1로 둘러쌓인 연속된 0의 가장 긴 길이를 말한다. 

 

For example, number 9 has binary representation 1001 and contains a binary gap of length 2. The number 529 has binary representation 1000010001 and contains two binary gaps: one of length 4 and one of length 3. The number 20 has binary representation 10100 and contains one binary gap of length 1. The number 15 has binary representation 1111 and has no binary gaps. The number 32 has binary representation 100000 and has no binary gaps.

=> 예를들어, 숫자 9는 2진수로 표현했을 때 1001이며 길이 2의 binary gap을 가진다. 

숫자 529는 2진수로 표현했을 때 1000010001이며 길이가 각각 4, 3인 2개의 binary gap을 가지고 있다. 

숫자 20은 2진수로 표현했을 때 10100이며 길이 1의 binary gap을 가진다. 

(뒤의 00은 1로 둘러쌓여있지 않으므로 binary gap이 아님)

숫자 15는 2진수로 표현했을 때 1111이며 binary gap을 가지고 있지 않다.

숫자 32는 2진수로 표현했을 때 100000이며 binary gap을 가지고 있지 않다.

(마찬가지로, 뒤의 00000은 1로 둘러쌓여있지 않으므로 binary gap이 아님)

 

Write a function:

class Solution { public int solution(int N); }

that, given a positive integer N, returns the length of its longest binary gap. The function should return 0 if N doesn't contain a binary gap.

=> Solution 함수를 완성하라.

양의 정수 N의 값이 주어질때, 해당 함수는 가장 긴 binary gap의 길이를  return 하며, binary gap이 없는 경우 0을 리턴한다.

 

For example, given N = 1041 the function should return 5, because N has binary representation 10000010001 and so its longest binary gap is of length 5. Given N = 32 the function should return 0, because N has binary representation '100000' and thus no binary gaps.

=> 예를 들어, 주어진 N이 1041일 때 함수는 5를 리턴해야한다. 왜냐하면, N을 2진수로 표현하면 10000010001 이고 가장 긴 binary gap 값이 5이기 때문이다. 주어진 N이 32라면, 함수는 0을 리턴해야 한다. 왜냐하면, N을 2진수로 표현하면 100000이고 binary gap 값이 없기 때문이다.

 

Write an efficient algorithm for the following assumptions:

N is an integer within the range [1..2,147,483,647].

=> 다음의 가정 하에, 효율적인 알고리즘을 작성하라 : N은 [1..2,147,483,647] 범위 내의 정수이다. 

 

Copyright 2009–2021 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.

---

해당 문제를 풀기 위해, 인덱스 값을 활용했다.

다른 풀이들을 보니 세줄로 끝나기도 하던데, 파이썬이나 PHP 언어를 많이 사용하는 듯 하다.

자바에는 없는 함수들을 사용한 걸 보고, 자바형식으로 풀기위해 인덱스 값과 FOR문을 활용했다.

정상 동작여부를 확인하기 위해, main에서 값을 호출해가며 확인했다.

 

package codingTest;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class BinaryTest {
	//메인에서 확인
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		System.out.println("변환 할 숫자를 입력하세요");
		int N = sc.nextInt();
		System.out.println("gap="+solution(N));
	}
	
   	//함수 => 테스트 부분
	public static int solution(int N) {
		int gap = 0;
		String arr [] = Integer.toBinaryString(N).split("");
		//N이 529일 때 => 1000010001
		
		List<Integer> numList = new ArrayList<Integer>();
		//1의 인덱스값을 담을 INT 배열 선언
		
		for(int i=0;i<arr.length;i++) {
			if(arr[i].equals("1")) {
				numList.add(i);	//1의 인덱스를 담음
				//0,5,9
			}
		}
		
        //사이 값을 구할 것이므로 size()-1번 FOR문 돌리면 됨
		for(int i=0;i<numList.size()-1;i++) {	
			int count = numList.get(i+1)-(numList.get(i)+1);	// 5-(0+1)=4, 9-(5+1)=3
			if(count>gap) {
				gap=count;	//큰 값으로 대입
			}
		}
		
		return gap;
	}
}

 

쉬운 이해를 위해 주석으로 달아두었다. 

더 효율적인 코드 작성이 필요하다고 생각하지만, 오늘은 어찌됐든 풀어낸것으로 만족!