[프로그래머스] Lv.1 (1차) 비밀지도

⚠️JAVA 언어를 사용합니다.

 

 

 

카카오 문제인데 생각보다 괜찮아서 작성해 본다.

여기서 String.format()이라는 함수를 접해서 기록하려고 한다.

 

 

🔒문제

네오는 평소 프로도가 비상금을 숨겨놓는 장소를 알려줄 비밀지도를 손에 넣었다. 그런데 이 비밀지도는 숫자로 암호화되어 있어 위치를 확인하기 위해서는 암호를 해독해야 한다. 다행히 지도 암호를 해독할 방법을 적어놓은 메모도 함께 발견했다.

1. 지도는 한 변의 길이가 n인 정사각형 배열 형태로, 각 칸은 "공백"(" ") 또는 "벽"("#") 두 종류로 이루어져 있다.
2. 전체 지도는 두 장의 지도를 겹쳐서 얻을 수 있다. 각각 "지도 1"과 "지도 2"라고 하자. 지도 1 또는 지도 2 중 어느 하나라도 벽인 부분은 전체 지도에서도 벽이다. 지도 1과 지도 2에서 모두 공백인 부분은 전체 지도에서도 공백이다.
3. "지도 1"과 "지도 2"는 각각 정수 배열로 암호화되어 있다.
4. 암호화된 배열은 지도의 각 가로줄에서 벽 부분을 1, 공백 부분을 0으로 부호화했을 때 얻어지는 이진수에 해당하는 값의 배열이다.

네오가 프로도의 비상금을 손에 넣을 수 있도록, 비밀지도의 암호를 해독하는 작업을 도와줄 프로그램을 작성하라.

 

 

 

---

🗝️정답

class Solution {
    public String[] solution(int n, int[] arr1, int[] arr2) {
        StringBuffer answer = new StringBuffer();
        char[] a1 = new char[n];
        char[] a2 = new char[n];
        
        for(int i=0; i<n; i++){
            a1 = String.format("%" + n + "s", Integer.toString(arr1[i],2)).toCharArray();
            a2 = String.format("%" + n + "s", Integer.toString(arr2[i],2)).toCharArray();
            for(int j=0; j<n; j++){
                if(a1[j]=='1' || a2[j]=='1')  answer.append("#");
                else  answer.append(" ");
            }
            answer.append(",");
        }
        return answer.toString().split(",");
    }
}

 

💡풀이해석

- 두 지도 즉, 배열을 합쳤을 때 벽과 벽이 아닌 곳을 구분하는 문제. 

- 배열의 원소를 2진수로 변환하면 (위에서부터)한 줄씩, 벽은 1로 표현, 벽이 아닌 곳은 0으로 표현된다. 이때 주의할 점은 2진수로 변환한 길이가 n(지도의 한 변의 길이) 보다 작다면 부족한 길이만큼 앞을 0으로 채워야 한다.

- 출력 시 벽은 #, 벽이 아닌 곳은 공백으로 표현

 

// 변수 선언

• StringBuffer answer : 스트링 버퍼에 값을 넣은 뒤 마지막에 배열로 반환
  • String으로 사용하면 #또는 공백을 +할 때마다 새로운 객체를 계속 생성하므로 성능이 좋지 않을 것으로 예상
• char[] a1, char[] a2 : 주어진 배열의 원소 하나를 2진수로 변환할 때마다 한 글자씩 담을 char형 배열 선언

 

// 반복문으로 지도의 행 별로 벽의 유무 판단

 

1. 각 배열의 원소 하나를 이진수로 변환 후 자릿수 즉, 길이를 맞춰서 char배열에 저장 

• String.format("%" + n + "s", Integer.toString(arr1[i],2)).toCharArray() : 메소드 체이닝
  • Integer.toString(arr1[i],2) : 숫자 변환. 첫 번째 인수로 변환할 숫자를 주고, 두 번째 인수로 몇 진수로 반환할 것인지 전달. 문자열 리턴
  • String.format() : 여기서 길이를 맞춰준다. 첫 인수로 표현식, 두 번째 인수로 표현할 String을 주는데, "%" + n + "s"라고 값을 넣으면 n길이만큼 앞을 공백으로 채워서 문자열로 반환해 준다.
  • .toCharArray() : 반환된 값이 String이므로 String 클래스의 내장 함수를 사용하여 char 배열로 바꿔준다.

2. 이중 for문으로 각 열의 벽 유무를 판단하여 저장

• if(a1[j]=='1' || a2[j]=='1') : 벽(1)이 하나라도 있으면 전체 지도에서 벽이 되므로 #추가
• else : 둘 중 하나라도 벽이 없으면 전체 지도에 벽이 없으므로 공백(" ") 추가

3. 한 행이 끝나면

• answer.append(",") : 마지막에 배열로 자르기 위해 구분자를 추가

 

//문자열 배열로 반환

• answer.toString().split(",") : 버퍼였으므로 string으로 바꿔준 다음, 구분자를 기준으로 split() 함수 사용하여 자름

 

 

 

---

✏️자기 분석

채점 결과는 다음과 같이 나왔다. 변환을 많이 하다 보니 조금 높게 나온 듯싶다.

이 답을 내기까지 몇 가지 과정을 거쳤다.

 

1. 처음엔 블로그만 따라 보고 format()으로 생긴 공백을 replace()를 사용하여 모두 0으로 바꿔주었다.

하지만 이후 벽 유무를 판단할 때 1만 가지고 판단하는 것을 고려하여 이 부분을 없애주었다.

a1 = String.format("%" + n + "s", Integer.toString(arr1[i],2)).replace(" ", "0").toCharArray();

미세한 차이지만, 어째서인지 이게 더 빠른 듯하다...(?) 조금 더 공부해 봐야겠다.

 

 

2. 또 다른 블로그를 보고 Integer.toString() 대신 Integer.toBinaryString()으로 한 번에 두 이진수를 비교하였다. 미리 두 이진수를 더하여 하나의 char 배열만 보고 1일 때 #을 입력하였다.

a = String.format("%" + n + "s", Integer.toBinaryString(arr1[i] | arr2[i])).toCharArray();

이번엔 조금 더 큰 차이로 느려졌다. 비교연산을 한 번 더 해서 조금 느려진 게 아닐까 조심스래 추측해 본다.

 

 

3. 만약 StringBuffer 대신 String을 사용했다면 어떨까?

class Solution {
    public String[] solution(int n, int[] arr1, int[] arr2) {
        String[] answer = new String[n];
        char[] a1 = new char[n];
        char[] a2 = new char[n];
        
        for(int i=0; i<n; i++){
            a1 = String.format("%" + n + "s", Integer.toString(arr1[i],2)).toCharArray();
            a2 = String.format("%" + n + "s", Integer.toString(arr2[i],2)).toCharArray();
            answer[i] = "";
            for(int k=0; k<n; k++){
                if(a1[k]=='1' || a2[k]=='1')  answer[i] += "#";
                else  answer[i] += " ";
            }
        }
        return answer;
    }
}

역시 제일 오래 걸린다.

 

 

4. 내 답은 아니지만 간결하고 빠른 코드

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

      for(int i = 0 ; i < n ; i++){
          temp = String.format("%16s", Integer.toBinaryString(arr1[i] | arr2[i]));
          temp = temp.substring(temp.length() - n);
          temp = temp.replaceAll("1", "#");
          temp = temp.replaceAll("0", " ");
          answer[i] = temp;
      }
      
      return answer;
  }
}

아주 빠르고 좋은 코드다. 불필요한 배열을 만들지 않아도 되고, replaceAll을 사용하여 문자열에 추가하는 작업이 없어졌다. 댓글을 보면 "%" + n +"s" 대신 "%16s"를 사용하는 게 훨씬 빠르다고 한다. 메소드 체이닝을 사용하여도 괜찮을 것 같다(실제로 돌려보니 성능 차이는 별로 없다). 

 

 

🚩결론

1. 답이 나와도 여러 코드를 보며 비교해보는 자세 굿굿

2. string.format()함수는 유용하게 쓰이나 많이 나오지 않아서 까먹었었다. 기억해라.

3. 기본 타입의 특성을 알고 풀면 도움이 될 때가 많다. 기본기 탄탄히 하자