[알고리즘] 프로그래머스 : 비밀지도

알고리즘 문제 출처 : 프로그래머스 https://programmers.co.kr/learn/courses/30/lessons/17681

코딩테스트 연습 - [1차] 비밀지도

 

내가 작성한 코드

카카오 신입 공채 1차 코딩 테스트 문제로 난이도 하의 81.78%의 정답률을 보이는 문제인데 나는 고전했다... 코드를 짜다보니 코드가 엄청 길어졌고 2를 나눈 몫과 나머지를 계속 쌓아서 코드를 짰었는데 시간 복잡도에서 계속 막혔다.

고민하다가 꼭 2진수로 바꾸지 않아도 된다는 아이디어를 얻게 되었다. 숫자 n이 주어질 경우 주어진 정수 배열에서 변환한 2진수는 n-1자리 이하의 자리를 가지게 된다. 2진수에서 10진수로 바꿀 때 2^n+2^(n-1)+...+2+1의 형태가 되고 10진법으로 2^n은 2진법으로 10^n이 되는 것을 감안하면 굳이 10진법을 2진법으로 바꾸지 않아도 된다.

이런 사고에 착안하여 코드를 짜면 다음과 같다. 변수 compare에 비교 대상이 될 2^(n-1)부터 저장하여 배열 arr1의 원소나 배열 arr2의 원소 중 어느 한 수라도 이 수보다 크거나 같으면 해당 자리가 1이라는 의미이므로 #을 저장하고 둘 다 이 수보다 작으면 해당 자리가 비워져있거나 0이라는 소리이므로 공백을 저장한다. 그리고 compare보다 크거나 같을 경우에는 다음 자리의 비교를 위해 해당되는 정수 배열의 원소에서 compare을 계속해서 뺀다. 한 차례 완성된 문자는 answer 배열에 차곡차곡 저장되며 이 배열 answer를 반환하면 된다.

import java.util.Arrays;
class Solution {
    public String[] solution(int n, int[] arr1, int[] arr2) {
        String[] answer = new String[n];
        String str = "";
        int temp1 = 0;
        int temp2 = 0;
        int compare = 0;
        for(int i=0; i<n; i++){
            str = "";
            temp1 = arr1[i];
            temp2 = arr2[i];
            for(int j=n-1; j>=0; j--){
            	compare = (int)Math.pow(2, j);
                if(temp1 < compare && temp2 < compare){
                    str += " ";
                }else{
                    str += "#";
                    if(temp1 >= compare) temp1 -= compare;
                    if(temp2 >= compare) temp2 -= compare;
                }
            }
            answer[i] = str;
        }
        return answer;
    }
}

 

비록 내가 고전한 문제이지만 지금은 알고리즘 문제를 접한 지 얼마되지 않은 초기이고 계속해서 문제를 풀고 공부를 하다 보면 이 정도 문제쯤은 우스워지는 날이 올 것임을 믿는다. 그러니까 난 주눅들지 않고 계속하여 문제해결력을 키워나갈 것이다.