[Swift] 2020 KAKAO BLIND RECRUITMENT 자물쇠와 열쇠

Problem

코딩테스트 연습 - 자물쇠와 열쇠

---

Solution

자물쇠와 열쇠의 구멍을 비교하지 않고도 결과를 반환할 수 있는 경우를 먼저 처리해줍니다.

 

1.자물쇠와 구멍과 열쇠의 돌기가 각 각 1개일 경우 True

 

2.자물쇠의 구멍이 열쇠의 돌기보다 많을 경우 False

 

만약 2개의 경우 모두 해당하지 않는다면

 

자물쇠와 열쇠의 각 구멍과 돌기가 어느 부분에 있는지를 알아내야 하는데요.

 

그렇다면 어떻게 알아내야 할까요?

 

저는 아래와 같이 자물쇠와 열쇠를 X,Y 좌표로 생각을 해보았습니다.

지문에 나와 있는 그림을 보면 열쇠 돌기는 (0,1),(1,2),(2,2) 이고

 

자물쇠 구멍은 (2,1),(1,2)가 되겠죠?

 

(코드로 알아내는 방법은 아래 소스코드에서 findSpinOrSlots 함수를 참고해주세요!)

---

 

이렇게 열쇠와 자물쇠 구멍을 알아냈다면 

 

열쇠를 회전했을때의 돌기 위치를 설정해줘야 합니다.

 

아래는 처음 열쇠의 위치를 0도일때 기준으로 시계방향으로 90도 돌리면 위에서 우측그림이 되고 

 

시계방향으로 180도 방향으로 돌리면 아래에서 좌측그림 , 시계방향으로 270도 돌리면 아래에서 우측 그림입니다.

이렇게 보면 시계방향으로 90도 회전할때마다 생기는 규칙이 있는데요.

 

y에 가장 최댓값을 빼준 뒤 절댓값으로 바꿔주고 x와 y의 위치를 바꿔주는 것입니다.

 

예를 들어 0도일때 각 돌기의 위는 (0,1), (1,2), (2,2)  입니다.

 

먼저 첫번째 0,1 을 y에 가장 최댓값이 2를 빼준 뒤 절댓값으로 바꿔주면 -> 0,1

 

그 다음 x와 y의 위치를 바꿔주면 -> 1,0

 

1,2도 마찬가지로 진행하면 -> 0,1

 

2,2도 마찬가지로 진행하면 -> 0,2

 

로 (1,0), (0,1), (0,2)가 되고 보면 시계방향으로 90도 돌린 위에서 우측 그림의 돌기 위치가 되었죠?

 

이런식으로 각 회전방향에 따른 돌기의 위치를 저장해줍니다.

 

(아래 소스코드에서 rotate 함수를 참고해주세요!)

---

 

이렇게 모든 회전방향의 돌기 위치를 구했다면 각 회전방향에 따른 돌기 위치가 자물쇠의 구멍 위치와 일치하는지 확인해봐야겠죠?

 

가장 먼저 자물쇠의 칸수만큼을 열쇠 돌기위치의 x와 y에 각 각 빼줍니다.

 

그럼 초기 세팅은 아래와 같은 위치가 될 것입니다.

 

여기서부터는 각 y와 x에 +1을 해주면서 자물쇠와 비교해야하는데요 

 

열쇠가 M * M칸이고 자물쇠가 N*N칸이라면 각 x와 y가 M+N의 -1 만큼을 이동해야 모든 위치를 확인할 수 있을 것입니다.

 

아래의 GIF를 참고해주시면 이해가 쉬우실거에요!

 

 

이렇게 모든 회전한 열쇠의 돌기의 위치와 자물쇠의 구멍의 위치를 비교해주다가 만약 일치하는게 나오면

 

true를 반환하고 없다면 false를 반환해주시면 됩니다.

 

(아래 소스코드의 moveAll 함수를 참고해주세요)

 

주의하실 점은 만약 2차원 배열 [[2,1],[1,2]]와 [[1,2],[2,1]]이 있다면 이것은 같은 것일까요?

 

정답은 X입니다.

 

그러므로 각 열쇠의 위치를 y 기준으로 정렬해준뒤 x 기준으로 정렬해주시면 됩니다.

 

(아래 소스코드의 sortKeyspins을 참고해주세요.)

---

Source Code

	import Foundation
	var M = Int()
	var N = Int()
	func solution(_ key:[[Int]], _ lock:[[Int]]) -> Bool {
	(M,N) = (key.count,lock.count)
	if lock.filter({$0.contains(0)}).count == 1 && key.filter({$0.contains(1)}).count == 1{
	return true
	}
	if lock.filter({$0.contains(0)}).count > key.filter({$0.contains(1)}).count {
	return false
	}
	let keySpins = findSlotOrSpins(keyOrLock: key,n:1)
	let lockSlots = findSlotOrSpins(keyOrLock: lock,n:0)
	var rotatedKeySpins = [keySpins]
	for _ in 0...2 {
	rotatedKeySpins.append(rotate(keySpins: rotatedKeySpins.last!))
	}
	for keyspins in rotatedKeySpins {
	var sortKeyspins = keyspins
	sortKeyspins.sort(by: {$0[1] == $1[1] ? $0[0] < $1[0] : $0[1] < $1[1]})
	if moveAll(sortKeySpins: sortKeyspins, lockSlots: lockSlots) {
	return true
	}
	}
	return false
	}
	func findSlotOrSpins(keyOrLock:[[Int]],n:Int) -> [[Int]] {
	var locations = [[Int]]()
	for (y,location) in keyOrLock.enumerated() {
	if location.contains(n){
	for (x,number) in location.enumerated() {
	if number == n {
	locations.append([x,y])
	}
	}
	}
	}
	return locations
	}
	func rotate(keySpins:[[Int]]) -> [[Int]] {
	var rotatedKeySpins = [[Int]]()
	for spin in keySpins {
	let map = spin.map{String($0)}
	let x = Int(map[0])!
	let y = Int(map[1])!
	rotatedKeySpins.append([y,abs(x-M+1)])
	}
	return rotatedKeySpins
	}
	func moveAll(sortKeySpins:[[Int]],lockSlots:[[Int]]) -> Bool {
	var start = sortKeySpins.map{[$0[0] - M,$0[1] - M]}
	for _ in 1...N+M-1 {
	start = start.map{[$0[0] + 1,$0[1]]}
	if start.filter({0...N-1 ~= $0[0] && 0...N-1 ~= $0[1]}) == lockSlots {
	return true
	}
	for _ in 1...N+M-1 {
	start = start.map{[$0[0],$0[1] + 1]}
	if start.filter({0...N-1 ~= $0[0] && 0...N-1 ~= $0[1]}) == lockSlots {
	return true
	}
	}
	start = start.map{[$0[0],$0[1] - (N+M-1)]}
	}
	return false
	}

view raw 자물쇠와 열쇠.swift hosted with ❤ by GitHub

 

---

새롭게 알게된 것

 

1차적으로 정렬한 것을 유지한 채 또 다른 조건으로 정렬하는 법

 

sort(by: {$0[1] == $1[1] ? $0[0] < $1[0] : $0[1] < $1[1]})