[Java Algorithm] 이진수 변환 문제 - 모 기업의 코딩테스트 문제를 회상하며 적는 글

 

안녕하딤니카? 😎

재영입니다...

 

오늘의 글은 최근 응시했던 코딩테스트에서 

진짜 풀 수 있었는데 이진수 변환 메서드가 도저히 생각나지 않았던 게 너무 아까워서 적어보는 오답노트입니다 ✏️

 

복기해 보니 나름 간단한 문제였던 게 좀 짜증 납니다

아무래도 전 바보가 맞는 것 같습니다... 우울됨

여러분들은 천재만재니까 이해 부탁드리겠습니다 ㅜ

 

문제는 자세하게 기억나진 않아서 정말 간략하게 적는 점 양해 

같은 건 안 구하겠습니다 

 

레쓰~ 꼬~

 

 

 

 

 

 

1. 문제

입력받은 수 M이 있다. N개를 입력받을 건데, 

무작위로 M 2개를 뽑아 합을 구하고 그 합을 이진수로 변환하여 1이 제일 많은 수의 1의 개수를 답으로 출력한다

첫 줄에는 N을 입력받을 거고, 두 번째 줄에는 M을 N개 입력받을 것이다. M은 서로 공백을 두고 입력받는다. 

 

문제는 진짜 비문학 지문 수준으로 훨씬 길었는데, 제가 구현에 필요한 부분만 축약했습니다

시간복잡도는 모든 언어 2초였는데 N과 M의 값의 범위가 크진 않아서 신경 쓰이는 건 아니었습니다

... 네 맞습니다 사실 N과 M의 범위까지는 도저히 생각나지 않습니다 양해부탁티비 🙏

 

 

 

 

1-1. 예제

입력값

5

2 1 4 5 3

 

출력값

maxCount : 3

두 수의 합이 7인 경우에 이진법으로 7을 표현하면 111 입니다

이 경우가 1이 제일 많은 경우이기 때문에 1의 개수 3을 답으로 출력하면 정답입니다

 

 

입력값

5

1 1 1 1 15

 

출력값

maxCount : 1

두 수의 합이 2인 경우 이진법으로 표현하면 10 이고

16인 경우에는 10000 이기 때문에 둘 다 1의 개수는 1개이기 때문에 1을 답으로 출력하면 정답입니다

 

 

 

 

2. 수도코드

문제 흐름을 일단 수도코드로 정리해 보겠습니다

 

1. N개만큼 저장할 수 있는 V 배열을 선언하고, for문 돌려서 V배열에 값을 입력한다.
2. 두 수를 무작위로 뽑아서 더한 값을 저장할 sumSet 배열을 HashSet 으로 생성해서 중복값을 제거하며 저장한다.
3. 중복을 제거한 sumSet 을 List 로 변환할 건데, List로 변환하면서 이진수의 1의 개수를 구하는 메서드를 사용해서 sumSet에 저장된 값을 이진수로 변환하고, 1의 개수를 countOfOnes 라는 변수에 저장해 준다.  ➡️ 여기서 Integer.toBinaryString() 또는 Integer.bitCount() 메서드를 사용할 것이다.
4. 1의 개수가 가장 많은 값을 선택해서 답으로 출력시킨다.

이런 흐름으로 풀 것이고, 3번을 보시면 두 가지 메서드 중 하나를 선택한다고 적어놨죠?

그 이유를 여기서 잠깐 언급하고 가겠습니다

 

 

 

 

2-1. 이진수 변환에 필요한 Integer.toBinaryString() 와 Integer.bitCount() 메서드의 차이점

1. 보통 이진수로 변환하자! 라고 하면 Integer.toBinaryString() 라는 메서드가 떠오르는데, 이 문제에서 요구하는 것은 "이진수로 변환한 값에서 1이 많이 들어있는 값" 을 골라야 되기 때문에 Integer.toBinaryString() 를 사용하면 변환한 이진수에 있는 1을 세어주는 알고리즘을 더 구현해야 된다.
2. 뭐 그렇게 해도 상관은 없다만... 우리에게는 Integer.bitCount() 라는 편리한 메서드가 있다 (와!). 이 메서드는 이진수 변환 후 1의 개수를 카운트하는 알고리즘을 따로 구현할 필요 없이 바로 10진수의 이진 표현에서 1의 개수를 세는 방법으로 1의 개수를 구해준다.

 

그래서 이 문제에서는 1번과 2번을 사용한 방법 둘 다 남겨보겠습니다

두 가지 다 알고있으면 좋으니까요? 하핫

 

 

 

 

3. 풀이

 

3-1. Integer.toBinaryString() 메서드를 사용한 코드 

import java.util.*;
import java.util.stream.Collectors;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();  // N 입력
        int[] M = new int[N];  // M 배열 생성

        for (int i = 0; i < N; i++) {
            M[i] = sc.nextInt();  // M 배열에 값 입력
        }

        // 중복 없는 V 배열의 합들을 저장할 Set 생성
        Set<Integer> sumSet = new HashSet<>();

        for (int i = 0; i < N; i++) {
            for (int j = i + 1; j < N; j++) {
                sumSet.add(M[i] + M[j]);
            }
        }

        List<Integer> sums = new ArrayList<>(sumSet);

        // 합들을 이진수로 변환하여 1의 개수를 저장할 리스트 생성
        List<Integer> countOfOnes = sums.stream()
                .map(s -> Integer.toBinaryString(s))
                .map(s -> (int) s.chars().filter(c -> c == '1').count()) // 변환한 이진수에서 1의 개수를 직접 계산
                .collect(Collectors.toList());

        // 1의 개수가 가장 많은 값 선택
        int maxCount = Collections.max(countOfOnes);

        System.out.println("maxCount : " + maxCount);
        sc.close();
    }
}

 

위에서 설명했듯이, Integer.toBinaryString() 는 10진수를 이진수로 변환만 해주기 때문에, 

s.chars().filter(c -> c == '1') 을 추가로 사용해서 문자열에서 1을 세어줘야 됩니다

여기서는 map 메서드에서 반환하는 값의 타입과 Collertors.toList() 메서드가 기대하는 타입을 

명시적으로 Integer 로 일치시켜 주기 위해 추가로 (int) 를 넣어 형변환을 시켜줬습니다

 

 

 

 

3-2. Integer.bitCount() 메서드를 사용한 코드 

import java.util.*;
import java.util.stream.Collectors;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();  // N 입력
        int[] M = new int[N];  // M 배열 생성

        for (int i = 0; i < N; i++) {
            M[i] = sc.nextInt();  // M 배열에 값 입력
        }

        // 중복 없는 M 배열의 합들을 저장할 Set 생성
        Set<Integer> sumSet = new HashSet<>();

        for (int i = 0; i < N; i++) {
            for (int j = i + 1; j < N; j++) {
                sumSet.add(M[i] + M[j]);
            }
        }

        List<Integer> sums = new ArrayList<>(sumSet);

        // 합들을 이진수로 변환하여 1의 개수를 저장할 리스트 생성
        List<Integer> countOfOnes = sums.stream()
                .map(s -> Integer.bitCount(s))
                .collect(Collectors.toList());

        // 1의 개수가 가장 많은 값 선택
        int maxCount = Collections.max(countOfOnes);
		
        // 정답 출력
        System.out.println("maxCount : " + maxCount);
        sc.close();
    }
}

 

이진수 변환 ➡️ 1의 개수 카운트 ➡️ 저장 로직을 사용하지 않고 

Integer.bitCount() 메서드를 사용해서 10진수의 이진 표현에서 1의 개수를 바로 카운트해서 저장하는 방법을 사용했습니다

 

 

 

작성해 보니 이진법 관련 메서드를 알고 있는지,

HashSet을 사용해서 배열에 저장한 수를 두 개 뽑아서 더한 값을 중복 없이 저장할 수 있는지, 

Collections 관련 메서드를 사용할 수 있는지

를 물어보는 문제였던 것 같네요

 

담에 저런 문제 나오면 잘 풀어야지! 라는 마음으로~

이번 글은 여기서 마치겠습니따

 

 

 

긴 글 읽어주셔서 감사합니다! 💖

 

 

 

 

 

 

---

🍀

좋아하는 것을 계속 좋아하세요!
반드시 행복해집니다

백엔드 개발자가 되고 싶어서 열심히 헤딩 중인 재영입니다 :-)

[Github] https://github.com/chujaeyeong 
[E-mail] chujy1224@gmail.com