[프로그래머스] [1차] 비밀지도 - JAVA

문제 - [1차] 비밀지도

처음 해결 방법

class Solution {
    public String[] solution(int n, int[] arr1, int[] arr2) {
        String[] answer = new String[n];

        int[] map = new int[n];
        for(int i=0; i<n; i++){
            map[i] = arr1[i] | arr2[i];
        }

        for(int i=0; i<n; i++){
            String s = Integer.toString(map[i], 2);
            s = s.replace("1","#");
            s = s.replace("0", " ");
            if(s.length() < n){
                s = " ".repeat(n - s.length()) + s;
            }
            answer[i] = s;
        }
        return answer;
    }
}

 

처음에는 다음과 같은 흐름으로 문제를 해결했다.

1. 각 행을 비트연산(OR)으로 병합한다.
2. 병합된 값을 2진수 문자열로 변환한다.
3. 1을 #으로 변환하고, 0을 " "으로 변환한다.
4. 변환한 문자열이 n자리보다 짧으면 앞에 " "을 추가해 길이를 맞춘다.

문제점 발견

이 방법은 동작은 하지만 비효율적인 부분이 있었다.

• replace()는 내부적으로 문자열 전체를 순회하므로 시간복잡도 O(N)이 걸린다.
• String은 불변 객체이기 때문에, 문자열을 조작할 때마다 새로운 문자열을 만들어야 한다.
• 공백 문자열을 추가하는 과정도 O(N)이 소모된다.

따라서 한 줄을 변환하는 과정에 O(N) 이상의 부가적인 비용이 들 수 있다.

최종 구현 방법

문자열 변환 대신 비트 연산을 직접 활용해 효율적으로 처리했다.

class Solution {
    public String[] solution(int n, int[] arr1, int[] arr2) {
        String[] answer = new String[n];

        for(int i=0; i<n; i++){
            int merged = arr1[i] | arr2[i];
            StringBuilder sb = new StringBuilder();
            for(int bit=n-1; bit>=0; bit--){
                sb.append(((merged >> bit) & 1) == 1 ? "#" : " ");
            }
            answer[i] = sb.toString();
        }

        return answer;
    }
}

 

변경된 흐름

• 한 줄씩 비트연산(OR)을 수행한다.
• 가장 왼쪽 비트부터 순서대로 0/1을 검사하여 # 또는 " "로 변환한다.
• 별도의 문자열 변환이나 패딩 없이 StringBuilder로 바로 완성한다.

이 방식으로 한 줄의 변환을 O(N)으로 처리할 수 있었다.

생각

이 문제를 풀기 직전에 문자열 변환을 활용하는 문제를 풀었기 때문에, 처음에는 자연스럽게 문자열로 다루는 방향으로 접근했다.
또한, 비트 연산을 적극적으로 활용해 문제를 풀어본 경험이 많지 않아 처음에는 비트 관점으로 문제를 바라보지 못했던 것 같다.

 

처음 풀이에서는 병합까지만 비트연산을 활용하고, 이후에는 병합된 값을 단순히 문자열로 변환해 조작하는 관점으로 접근했지만,
최종 풀이에서는 입력값을 병합하고 변환하는 과정까지 이진수 자체를 인식하며 다루는 사고 전환이 필요했다.

 

앞으로도 이런 식으로 사고를 확장시킬 수 있는 문제를 만나면 이렇게 기록해두겠다.