Cooper's devlog

[알고리즘 데이]

 이번주 알고리즘 문제는 프로그래머스 문제였다. 이전에는 문제가 6문제였는데 CS10 과정이 절반만큼 온만큼 쉬어가는 의미로 4문제만 풀 수 있게 할당하셨다. 문제를 확인해봤더니 풀어본 문제들이 많았지만 옛날에 풀어본 것들이라 리팩토링 할겸 코드를 다시 작성했다. 그리고 남은 시간에 알고리즘 한문제를 추가로 풀었지만 해결하지 못했다.😢 

(아직 해결하지 못한 문제)

문제 내용은 숫자들 중 k를 제거해서 가장 큰 수를 찾는 문제였다. 그래서 조합을 이용해서 문제를 해결하려고 했다.

 기본 조합 문제의 경우 back tracking을 사용해서 문제를 푸는 방식이지만 기억이 나질 않아 비트마스크를 적용했다.

비트마스크란 이진수의 1과 0을 이용해 집합의 포함관계와 조합을 구하는 접근법이다.

아래와 같은 코드가 nCm의 형태를 추출할 수 있는 비트마스크(bitmask) 코드이다.

        int N = number.length();
        int M = N - k;

        for (int j = 0; (1 << N) > j; j++) {
            StringBuilder temp = new StringBuilder();

            if (Integer.bitCount(j) == M) {
                for (int i = 0; i < N; i++) {
                    if (((1 << i) & j) > 0) {
                        temp.append(number.charAt(i));
                    }
                }

 프로그래밍 언어에는 비트연산자(&, |, ,^)가 있다.

이 비트연산자를 이용하며 집합의 원소들을 표현할 수 있고 이를 이용해서 집합의 포함 관계를 확인해볼 수 있다.

그런데 문제는 테스트케이스의 문제를 풀렸지만 제출 시, 런타임 에러와 실패들이 떴다. 나와 비슷한 원인의 사람들을 확인해보려고 질문하기 페이지를 들어갔는데 자연수의 범위가 1-9가 아닌 0-9까지라고 하는데 무슨 소리인지 모르겠다.

우선 0-9라는 범위를 따질 부분이 없었다. 단순히 수를 빼고 연결한 수를 비교하는 것인데 자연수의 범위가 나온다는 것이 이해가 되질 않았다;;;

 오늘은 해결이 힘들 것 같고 빠른 시일내에 코드를 확인해서 어느 부분이 잘못되었는지 한번 확인해봐야겠다.