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

알고리즘 풀이 방법입니다.
문제(Problem) -> 생각(Think) -> 해결책(Solution) -> 리뷰(Review) 를 통해서 정리해서 작성합니다.

Problem📄

https://programmers.co.kr/learn/courses/30/lessons/17681

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

---

Think🤔

int n이 주어지는데 한변의 길이가 n의 정사각형이 만들어짐

각 칸 공백 또는 # 두 종류로 이루어져 있음

 

전체 지도는 두 장의 지도를 겹쳐서 모두 공백인 부분은 공백

 

n승의 값이 중요하다.(n은 0승 까지 있음)

n이 5이면 맨 처음에 #이 들어갈 경우는 2의4승인 16, 그 다음은 8 그 다음은 4이다

만약 8보다 큰 값이 나오면 그걸로 나눠서 그 값의 나머지를 넣어준다.

 

제곱은 Math.pow(double형, double형)을 이용해서 푼다.

class Solution {
    public String[] solution(int n, int[] arr1, int[] arr2) {
        String[] answer = new String[n];
        StringBuilder sb = new StringBuilder();
        
        for(int i=0; i<n; i++){
            while(arr1[i] != 0 && arr2[i] != 0){
                if(arr1[i] >= Math.pow(2,i)){
                    sb.append("#");
                    arr1[i] %= Math.pow(2,i);
                }else if(arr2[i] >= Math.pow(2,i)){
                    sb.append("#");
                    arr2[i] %= Math.pow(2,i);
                }else{
                    sb.append(" ");
                }
            }
            answer[i] = sb.toString();
        }
        
        return answer;
    }
}

실행시간이 길어서 실행이 중단된 코드

그리고 같은 숫자값이 나오면 if else if문 하나만 타게되고 하나는 16을 나눌 수 없게돼서 맞지 않는 코드가 된다.

 

문제를 보면 중복된 값인 "#"은 한번만 출력하게 하면 된다.

 

모르겠어서 다른 사람의 코드를 확인했다.

 

일단 풀면서 진법 변환 메소드를 사용해야 한다는 것은 알고 있었지만, 그 메소드를 어떻게 사용할지 몰라서 다른 방법으로 풀었었다.

 

1. 진법 변환 메소드 사용

String temp1 = Integer.toBinaryString(arr1[i]); 처럼

temp1에 만약 9가 들어온 값이 있으면 이것을 2진법으로 바꿔서 String형으로 표현할 수 있다.

 

이렇게 진법 변환을 이용하면 n이 5일때 앞에 0을 출력해야 하는 부분이 필요하다.

 

그리고 반복문을 이용해서 charAt값을 '0'의 값으로 뺴주면서 0은 아마 아스키코드에서 48일 것이다.

-48을 빼주거나 -'0'을 해서 문자에 담아서 answer의 번지에 추가 시키는 방법이 있다.

 

또 비슷한 방법은 2진법의 연산을 이용한다.

 

비트 연산!

AND(&)

- AND로 각 자리 수 1이 같으면 1로 변환

OR(|)

- OR로 둘 중 하나라도 1이면 1로 변환

XOR(^)

- 두수 각자리가 다르면 1로 변환

NOT(~)

- 각 자리수를 반대로 변환

 

비트 연산을 이용하면 위에 코드를 리팩토링 해서 풀 수 있다.

---

Solution✍

class Solution {
    public String[] solution(int n, int[] arr1, int[] arr2) {
        String[] answer = new String[n];
        int[] map = new int[n];
        
        // or 비트 연산
        for(int i=0; i<n; i++){
            map[i] = arr1[i] | arr2[i];
        }
        
        for(int i=0; i<map.length; i++){
            String tmp = Integer.toBinaryString(map[i]); // 이진법 변환
            //1001 > 01001 로 출력되게 해야함 n까지 앞에 "0"대입
            while(tmp.length() < n){
                tmp = "0"+tmp;
            }
            tmp = tmp.replaceAll("0"," "); //0은 공백으로
            tmp = tmp.replaceAll("1","#"); //1은 #으로 변환
            answer[i] = tmp;
        }
        
        return answer;
    }
}

---

Review🤩

replaceAll 그리고 Integer.toBinaryString을 통해서 2진법으로 바꾸는 방법과 비트 연산에 대해서 알게되었다.

---