728x90
반응형
leetcode.com/problems/walking-robot-simulation/
Walking Robot Simulation - LeetCode
Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.
leetcode.com
안녕하세요 후르륵짭짭 입니다.
일단 아주 개 고생한 문제 입니다 ㅎㅎㅎㅎㅎ
시뮬레이션 문제인데,, 단순하게 시뮬레이션으로 접근하면
코가 박살나는 ㅎㅎㅎ
일단 어렵습니다 ㅎㅎㅎ 예외처리 할게 많아서 ㅎㅎㅎ
또 단순이 완전 탐색을 하면 시간 초과가 생겨서 Hash를 써야합니다.
** 문제 내용 **
로봇의 시작 위치는 (0,0) 에서 시작하고 아래의 규칙으로 이동하는 겁니다.
- -2: turn left 90 degrees =. -2 라면 왼쪽으로 90도 회전
- -1: turn right 90 degrees = -1 이라면 오른쪽으로 90도 회전
- 1 <= x <= 9: move forward x units = 이동량은 1 ~9 값
장애물은 (obstacles[i][0] - 좌표 X, obstacles[i][1] - 좌표 Y) 로 주어지는데, 이 부분은 통과 할 수 없습니다.
따라서 그 이전의 값으로 위치가 정해집니다. (the robot stays on the previous grid square instead)
그래서 X 만큼 이동하면서 0,0에서 부터 (x*x) + (y*y) - 유클리드 거리 공식 까지 값이 최대일 때를 반환하는 겁니다.
** 성공한 코드 **
더보기
class Solution {
func robotSim(_ commands: [Int], _ obstacles: [[Int]]) -> Int {
var currentX : Int = 0
var currentY : Int = 0
var direction : String = "N"
var maxEuclid : Int = 0
var obx:[Int:[Int]] = [:]
var oby:[Int:[Int]] = [:]
for array in obstacles{
if obx[array[0]] == nil{
obx[array[0]] = [array[1]]
}else{
obx[array[0]]?.append(array[1])
}
if oby[array[1]] == nil{
oby[array[1]] = [array[0]]
}else{
oby[array[1]]?.append(array[0])
}
}
for element in commands {
if element == -1 {
if direction == "N"{
direction = "E"
}
else if direction == "S"{
direction = "W"
}
else if direction == "W"{
direction = "N"
}
else if direction == "E"{
direction = "S"
}
}
else if element == -2{
if direction == "N"{
direction = "W"
}
else if direction == "S"{
direction = "E"
}
else if direction == "W"{
direction = "S"
}
else if direction == "E"{
direction = "N"
}
}
else{
if direction == "N"{
movePoint(element, "N", ¤tX, ¤tY, obx , oby)
}
else if direction == "S"{
movePoint(element, "S", ¤tX, ¤tY, obx , oby)
}
else if direction == "W"{
movePoint(element, "W", ¤tX, ¤tY, obx , oby)
}
else if direction == "E"{
movePoint(element, "E", ¤tX, ¤tY, obx , oby)
}
}
// print(currentX , currentY , direction)
maxEuclid = max(maxEuclid , currentX * currentX + currentY * currentY)
}
return maxEuclid
}
func movePoint(_ times : Int,_ command : String , _ X : inout Int , _ Y : inout Int ,_ obx:[Int:[Int]] = [:], _ oby:[Int:[Int]] = [:]){
if command == "N"{
let filter = obx[X]?.filter({ (element) -> Bool in
return element > Y
}).sorted(by: <).first
// print(filter)
if filter != nil && Y + times >= filter!{
Y = filter! - 1
}
else{
Y = Y + times
}
}
else if command == "S"{
let filter = obx[X]?.filter({ (element) -> Bool in
return element < Y
}).sorted(by: >).first
// print(Y , filter)
if filter != nil && Y - times <= filter!{
Y = filter! + 1
}
else{
Y = Y - times
}
}
else if command == "W"{
let filter = oby[Y]?.filter({ (element) -> Bool in
return element < X
}).sorted(by: >).first
// print(filter)
if filter != nil && X - times <= filter!{
X = filter! + 1
}
else{
X = X - times
}
}
else if command == "E"{
let filter = oby[Y]?.filter({ (element) -> Bool in
return element > X
}).sorted(by: <).first
// print(filter)
if filter != nil && X + times >= filter!{
X = filter! - 1
}
else{
X = X + times
}
}
}
}
진심 ㅋㅋㅋ 엄청 하드 코딩입니다 ㅎㅎㅎ
그그그그그혀혀혀혐 ㅎㅎㅎㅎㅎ
그런데 여기서 중요한 것은 좌표 찾는 빠른 방법을 Hash를 이용했다는 겁니다.
그리고 탐색을 할 때, filter 를 사용해서 좌표 보다 앞에 있는 것들을 찾아주고 양수로 움직일 때는 오름차순으로 정렬
음수로 이동 할 때는 내림차순으로 정렬해서 첫번째 요소를 기준으로 예외 처리를 해줬습니다.
시뮬레이션 문제인데,,, 상당히 고생 했습니다.... 거의 3시간 반 정도 사용한 것 같습니다
** 시간 초과 한 초드 **
완전 탐색의 최후는 언제나 시간초과 입니다 ㅎㅎㅎㅎ
더보기
class Solution2 {
func robotSim(_ commands: [Int], _ obstacles: [[Int]]) -> Int {
var currentX : Int = 0
var currentY : Int = 0
var direction : String = "N"
var maxEuclid : Int = 0
for element in commands {
if element == -1 {
if direction == "N"{
direction = "E"
}
else if direction == "S"{
direction = "W"
}
else if direction == "W"{
direction = "N"
}
else if direction == "E"{
direction = "S"
}
}
else if element == -2{
if direction == "N"{
direction = "W"
}
else if direction == "S"{
direction = "E"
}
else if direction == "W"{
direction = "S"
}
else if direction == "E"{
direction = "N"
}
}
else{
if direction == "N"{
movePoint(element, "N", ¤tX, ¤tY, obstacles)
}
else if direction == "S"{
movePoint(element, "S", ¤tX, ¤tY, obstacles)
}
else if direction == "W"{
movePoint(element, "W", ¤tX, ¤tY, obstacles)
}
else if direction == "E"{
movePoint(element, "E", ¤tX, ¤tY, obstacles)
}
}
print(currentX , currentY , direction)
maxEuclid = max(maxEuclid , currentX * currentX + currentY * currentY)
}
return maxEuclid
}
func movePoint(_ times : Int,_ command : String , _ X : inout Int , _ Y : inout Int ,_ obstacles : [[Int]]){
var endX : Int = X
var endY : Int = Y
var minX = 0
var maxX = 0
var minY = 0
var maxY = 0
if command == "N"{
endY = Y + times
minX = min(X,endX)
maxX = max(X, endX)
minY = min(Y + 1,endY)
maxY = max(Y + 1,endY)
}
else if command == "S"{
endY = Y - times
minX = min(X,endX)
maxX = max(X, endX)
minY = min(Y - 1,endY)
maxY = max(Y - 1,endY)
}
else if command == "W"{
endX = X - times
minX = min(X - 1,endX)
maxX = max(X - 1, endX)
minY = min(Y,endY)
maxY = max(Y,endY)
}
else if command == "E"{
endX = X + times
minX = min(X + 1,endX)
maxX = max(X + 1, endX)
minY = min(Y,endY)
maxY = max(Y,endY)
}
// print(minX , maxX , minY , maxY)
for element in obstacles {
if element[0] >= minX && element[0] <= maxX && element[1] >= minY && element[1] <= maxY {
if command == "N"{
Y = element[1] - 1
}
else if command == "S"{
Y = element[1] + 1
}
else if command == "W"{
X = element[0] + 1
}
else if command == "E"{
X = element[0] - 1
}
return
}
}
X = endX
Y = endY
}
}
728x90
반응형
'Xcode > Swift - Algorithm' 카테고리의 다른 글
| Swift ) 프로그래머스(Lv2) - 튜플 (Dictionary) (0) | 2020.09.03 |
|---|---|
| Swift) 프로그래머스(Lv2) - 타겟 넘버 (BFS 와 Remove(:at)에 대한 고찰) (0) | 2020.09.02 |
| Swift) 프로그래머스(Lv2) - 괄호 변환 (Stack & Recursion) (0) | 2020.08.31 |
| Swift) 프로그래머스(Lv2) - 큰 수 만들기 (Stack) (0) | 2020.08.31 |
| Swift) 프로그래머스(Lv2) - 소수 찾기 (Brut-Force) (0) | 2020.08.30 |
댓글