알고리즘 - 프로그래머스 2018 KAKAO BLIND RECRUITMENT[1차] 비밀지도 (Swift)

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

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

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

입력 형식
입력으로 지도의 한 변 크기 n 과 2개의 정수 배열 arr1, arr2가 들어온다.

1 ≦ n ≦ 16
arr1, arr2는 길이 n인 정수 배열로 주어진다.
정수 배열의 각 원소 x를 이진수로 변환했을 때의 길이는 n 이하이다. 즉, 0 ≦ x ≦ 2n - 1을 만족한다.
출력 형식
원래의 비밀지도를 해독하여 '#', 공백으로 구성된 문자열 배열로 출력하라.

---

지도가 나오고..그래서 어려워 보였지만 간단하게 비트 및 xor 등 고급 연산자를 사용하면 쉽게 해결할 수 있는 문제입니다.

하지만 전 아직 비트 및 고급연산자를 사용을 해보질 않았네요.. 하하

 

그래서 일단은 기본 내장 함수로 문자열로 해서 풀어 보겠습니다.

 

추후에 고급연산자를 사용해서 푸는 방법을 추가해볼게요.

 

solution(5, [9, 20, 28, 18, 11], [30, 1, 21, 17, 28])

func solution(_ n:Int, _ arr1:[Int], _ arr2:[Int]) -> [String] {
    
    let arr1Array = arr1.map { (String(repeating: "0", count: n - String($0, radix: 2).count) + String($0, radix: 2))}
    let arr2Array = arr2.map { (String(repeating: "0", count: n - String($0, radix: 2).count) + String($0, radix: 2))}

    return zip(arr1Array, arr2Array).map { String(zip($0, $1).map { ($0 == "1" || $1 == "1") ? "#" : " " }) }
}

 

네 엄청 길조. 그리고 함수가 엄청 많이 들어가조.. 하지만 요즘은 고차함수에 대해서 공부중이기 때문에 고차함수만을 이용해서 풀고 있어요. ㅜㅜ

 

풀이는 아래의 순서로 진행하면 됩니다.

1. 2진수로 변환한다.

2. 글자 갯수를 n으로 맞춰준다

3. 두개의 값을 비교 하여 "or" 연산을 진행한다. (1 || 0 = 1)

4. 연산된 배열 값을 "#", " "으로 변환하여 반환한다.

 

먼저 솔루션으로 들어오는 파라미터로는 n(가로의 총길이), 비교할 2개의 배열(arr1, arr2)가 들어오게 됩니다.

map 함수를 써서 배열안의 모든값을 순차적으로 연산을 진행할게요.

 

arr1.map { (String(repeating: "0", count: n - String($0, radix: 2).count) + String($0, radix: 2))}

1. String($0, radix: 2))

  -> 함수부터 진행하는데 받은 인자값을 2진수로 변환하는 함수이며, // 1001 

2. String(repeating: "0", count: n - String($0, radix: 2).count)

  -> 자릿수를 맞춰줘야 하기 때문에 변환된 글자 갯수에 모자른 만큼 "0"을 추가합니다.

 

이렇게하면 변환된 2진수 배열이 완성됩니다.

arr1Array = ["01001", "10100", "11100", "10010", "01011"]
arr2Array = ["11110", "00001", "10101", "10001", "11100"]

 

 

그리고 이제 반환될 값을 만들어 줘야하는데 이방법 또한 그렇게 어렵지 않습니다.

zip(arr1Array, arr2Array).map { String(zip($0, $1).map { ($0 == "1" || $1 == "1") ? "#" : " " }) }

zip(arr1Array, arr2Array)

 -> 함수를 이용해서 두개의 배열값을 합쳐줄겁니다.

.map { .... }

 -> 함수를 이용하여 내부값을 순차적으로 연산 합니다.

 

이제 맵 함수내의 연산을 설명할게요!

String(zip($0, $1).map { ($0 == "1" || $1 == "1") ? "#" : " " })

 

String으로 감싸준 이유는 내부에는 현재 스트링으로 "01001"으로 값이 들어가 있는데 이것을 char로 하나식 연산을 진행해야 하기 때문에

연산을 진행하고 나온 값은 [String] 배열이 되기때문에 String으로 다시 형변환을 진행 해야 하기 때문에요.

 

zip($0, $1).map { ..... }

 -> 위에서 설명했듯이 두 값을 합처줄거고 내부를 순차적으로 연산할 것이기 때문에 함수는 동일해요.

 

맵 함수 내부의 연산 내용이에요. 첫번쨰 비교대상 값이 "1" 이거나 두번째 비교 연산 값이 "1" 이면 -> "#"을 반환해줘라!

($0 == "1" || $1 == "1") ? "#" : " "

 

반환된 값은 아래 처럼 출력이 되겠조? 이렇게 하면 간단하게 문제를 해결 할 수 있어요.

["#####", "# # #", "### #", "#  ##", "#####"]

 

하지만 이렇게 푸는 방식은 문제를 풀기만 한것으로 밖에 보이지 않네요... ㅜㅜ 현타의 시간이 오네요...

 

 

결론은 모든 값을 분해해서 -> or 연산으로 값을 비교하여 치환하고 -> 그값을 반환한다.

 

 

--> 추가

 

네 2진수 및 고급연산자(비트)를 알아보고 왔습니다.

 

다시한번 풀어볼게요. 

 

func solution(_ n:Int, _ arr1:[Int], _ arr2:[Int]) -> [String] {
    var answer: [String] = []
    for i in 0..<n{
        var data = arr1[i] | arr2[i]
        answer.append("")
        for _ in 0..<n{
            if data & 0b00000001 == 1{
                answer[i] = "#" + answer[i]
            }else{
                answer[i] = " " + answer[i]
            }
            data = data >> 1
        }
    }
    return answer
}

위에 풀었던 코드보다 간단해 보이조 네 다른분이 푸신 방법을 이용해서 다시 풀어보았어요.

 

먼저 방식은 동일합니다. 하지만 그 과정이 다르조 자세히 한번 볼게요

 

for i in 0..<n{ 
	......
}

먼저 첫번째 for문 루프에서는 문제에서 처음 n으로 주어지는 숫자가 가로의 갯수 및 배열의 갯수 라고 이라고 작성 되어 있어

n값만큼 루프를 진행할 예정입니다.

 

var data = arr1[i] | arr2[i]
answer.append("")

arr[1] | arr[i] 이부분에서 비트 연산자 OR " | "로 연산을 해주는데 

 

OR연산은 보통 합집합을 의미합니다. 진행을 하게 되면 아래처럼 값이 나오게 됩니다. 

그리고 반환해줄 Array 배열에 미리 공간을 추가합니다.

arr1 = [9, 20, 28, 18, 11]
arr2 = [30, 1, 21, 17, 28]

let data = arr[0] | arr2[0]

// arr1[0] = 01001 -> 9
// arr2[0] = 11110 -> 30

// data = 11111 -> 31

 

EX) Swift 공식 가이드 문서의 OR연산 예제

let someBits: UInt8 = 0b10110010
let moreBits: UInt8 = 0b01011110
let combinedbits = someBits | moreBits // equals 11111110

이런식으로 2진수의 값을 합해주는 값이 나오게 되조. 

따로 UInt단위로 형변환 하지 않아도 고급 연산자를 사용하면 연산이 자동으로 진행됩니다.

 

 

for _ in 0..<n{
    .......   
}

이후에 다음과 같이 for문이 한번더 등장하는데 이부분은 2진수로 변경한 데이터의 길이는 5개까지만 비교하기 때문에

위의 for문과 동일하게 n까지의 값만 비교합니다.

 

if data & 0b00000001 == 1{
	answer[i] = "#" + answer[i]
}else{
	answer[i] = " " + answer[i]
}

data = data >> 1

자이제 이부분이 문제의 핵심이라고 볼수 있습니다.

 

문제에서 어느 하나라도 벽인 부분은 벽으로 "#" 반환하며, 공백인 부분은 " "으로 반환한다.

여기에서 data는 현재 2진수로 "11111"입니다. 그렇다면 반환되는 내용은 "#####"으로 반환 되어야 겠조

 

여기에서 비트연산자 AND를(교집합) 사용하여 data & 0b00000001 == 1 의 조건문을 사용하여 1일 경우 #으로 표현하는 방법입니다.

 

0b000000001은 10진수로 1을 의미하조 결국 마지막 오른쪽 자리의 값만 비교하여 1의 값이 나왔을 경우에는 벽이라는 연산을 진행합니다. 그리고 아닐경우에는 공백을 진행하게 됩니다.

 

 

그리고 마지막 data = data >> 1 으로 연산을 진행하는데 

 

이부분은 비트 시프트 연산자라고 (>>) 해서 data의 이진수 값을 화살표 방향으로 1칸식 밀어주는 연산입니다.

 

이렇게 진행해서 모든값을 연산하여 반환해주는게 이번 방식입니다.

 

 

# ex) 비트 시프트 연산자에 대한 Swift 공식 문서 예제

let shiftBits: UInt8 = 4   // 00000100 in binary
shiftBits << 1             // 00001000
shiftBits << 2             // 00010000
shiftBits << 5             // 10000000
shiftBits << 6             // 00000000
shiftBits >> 2             // 00000001

 

 

 

잘 이해가 안되신다면 for문을 돌때의 진행 내용인 아래 로그를 한번 봐주세요.

arr1[0] = 1001, arr2[0] = 11110
index = 0 data = 11111
answer[0] = #
index = 1 data = 01111
answer[0] = ##
index = 2 data = 00111
answer[0] = ###
index = 3 data = 00011
answer[0] = ####
index = 4 data = 00001
answer[0] = #####

------------------------------
arr1[1] = 10100, arr2[1] = 00001
index = 0 data = 10101
answer[1] = #
index = 1 data = 01010
answer[1] =  #
index = 2 data = 00101
answer[1] = # #
index = 3 data = 00010
answer[1] =  # #
index = 4 data = 00001
answer[1] = # # #

.....

 

 

문제 풀이가 이전에 풀었던 방법과는 다르게 속도면에서나 가독성에서나 좋다고 생각됩니다.

 

한번씩 공부해보시고 풀어보시면 다른 문제에대해서도 쉽게 해결할 수 있을거라고 생각됩니다.