반응형
programmers.co.kr/learn/courses/30/lessons/60059
풀이 방법
자물쇠를 3배씩 영역을 늘리고
키를 90도씩 돌리니까 4가지의 키모양이 나올거에요
왜 3배를 늘리나면
이렇게 한칸씩 이동하면서 키를 넣어봐야해요
그렇기때문에 영역을 확장시켜주고
이렇게 움직이면서
딱 맞는 순간이 있다면
성공한 케이스가 되기때문이죠
문제조건을 잘봐야해요!!
저도 풀다가 놓친부분이 있어서 다시 봣어요..
조건
돌기끼리는 만나면 안됌
키와 자물쇠의 크기는 다를 수 있음 (키 <= 자물쇠)
열쇠를 위치를 옮겨가며 비교할때는
n-m+1 부터 시작해서 2n-1까지만 비교하면 다 비교할 수 있어요
2n-1을 넘어가면 그냥 빈공백에 더하는거라서 의미가없고 자물쇠가 엄청크고 키가작다면 비효율적인 계산이죠
돌기가 1 홈이 0 이기때문에
더하기로 겹치는 부분은 다 더해주고
겹친 상태에서 0혹은 2가 있다면 실패한 케이스로 취급햇어요
0이 나오는 경우는 아무것도 겹치지않았을 때
2가 나오는 경우는 돌기끼리 겹쳤을 때
이기때문에 실패케이스죠
검사하는 범위는
3배씩 확장했기때문에
n~2n까지의 인덱스만 검사해줬구요
전체적인로직은
1. 키를 돌린다
2. 겹치는 부분범위를 검사하고
3. 3배확장한 자물쇠와 키를 더한다
4. n~2n사이(진짜 자물쇠영역)에 0 혹은 2가 있다면 실패
-> 2번으로
5.1 겹치는 부분범위가 끝나도 못찾음 -> 1으로
5.2 찾으면 리턴
// 열쇠를 90도 돌리고
// 자물쇠의 모서리부터 하나씩 비교하면서 체크하기
// 어케해야할지.. -> 자물쇠의 3개배크기 배열생성
// 겹치는 부분 이동하면서 완전탐색
// 돌기끼리 만나면 안됌
// 키의 크기와 자물쇠의 크기는 다를수 있음
// 2020 카카오 블라인드
// 자물쇠와 열쇠
private func solutionP60059(_ key:[[Int]], _ lock:[[Int]]) -> Bool {
let m = key.count
let n = lock.count
var keyList = key
var newArr: [[Int]] = []
var newKey: [[Int]] = []
(1...3*n).forEach { _ in newArr.append([Int](repeating: 0, count: 3*n)) }
(1...m).forEach { _ in newKey.append([Int](repeating: 0, count: m)) }
func arrPrint(list: [[Int]]) {
for arr in list {
print(arr)
}
print("-----")
}
// 시계방향 90도회전
func rotation(key: [[Int]]) -> [[Int]] {
var tempKey = newKey
for i in 0..<m {
for j in 0..<m {
tempKey[i][j] = key[m-1-j][i]
}
}
return tempKey
}
// 3배에 자물쇠 적용
func fetchNewArr() {
for i in n..<2*n {
for j in n..<2*n {
newArr[i][j] = lock[i-n][j-n]
}
}
}
// 알맞는지 검사
// 2인경우는 돌기끼리 만난경우, 0인경우는 빈칸이 있는경우
func checkKey(lock: [[Int]]) -> Bool {
for i in n..<2*n {
for j in n..<2*n {
if lock[i][j] == 0 || lock[i][j] == 2 {
return false
}
}
}
return true
}
// 키에 맞는지 더하기
// row: 시작행 col: 시작열
// 3배자물쇠에 시작점으로부터 row,col만큼 떨어진곳에서 키 맞춰보기
func addKey(arr: inout [[Int]], row: Int, col: Int) {
for i in 0..<m {
for j in 0..<m {
arr[i+row][j+col] += keyList[i%m][j%m]
}
}
}
fetchNewArr()
for _ in 1...4 {
keyList = rotation(key: keyList)
// arrPrint(list: keyList)
for i in n-m+1..<2*n { // 2n밑으로는 빈칸이라서 검사할 필요가 없음(시작점도 m-n+1위로는 할필요없음)
for j in n-m+1..<2*n {
var arr = newArr
addKey(arr: &arr, row: i, col: j)
// arrPrint(list: arr)
if checkKey(lock: arr) {
return true
}
}
}
}
return false
}
반응형
'iyOmSd > Title: Algorithm풀이' 카테고리의 다른 글
[Swift Algorithm] 프로그래머스 42861 섬 연결하기 (0) | 2020.12.21 |
---|---|
[Swift Algorithm] 프로그래머스 49189 가장 먼 노드 (0) | 2020.12.11 |
[Swift Algorithm] 프로그래머스 68646 풍선 터트리기 (월간 코드 챌린지 시즌1) (0) | 2020.11.24 |
[Swift Algorithm] 프로그래머스 17676 추석 트래픽 (2018 카카오 블라인드) (0) | 2020.11.18 |
[Swift Algorithm] 프로그래머스 17687 N진수 게임 (2018 카카오 블라인드) (0) | 2020.11.14 |