seat

1. 문제

2. 입출력

3. 입출력 예시

4. 문제 설계

1. 전형적인 달팽이 배열 문제
2. 문제의 크기가 1000이므로 O(N^2) 즉, 완전탐색으로 문제를 해결함
3. 문제를 해결한 알고리즘은 2차원 배열의 테두리에 여유 공간을 두어서 배열 index 에러를 방지하고, 입력한 K의 값이 R * C보다 큰 경우 좌석을 배정받을 수 없으므로 해당 경우를 예외처리 함.
4. 문제에서는 왼쪽 아래가 (1, 1)이지만 실제 배열에서는 왼쪽 아래가 (1, 6)이므로 (1, 6)부터 탐색을 시작함
5. 위 방향 이동인 경우 바로 위 인덱스(y축 이동)가 false일 경우에만 현재 좌석에 true를 줄 수 있고, 그렇지 않은 경우 현재 좌석에서 탐색을 멈춤
6. 오른쪽 방향 이동인 경우 바로 다음 인덱스(x축 이동)가 false일 경우에만 현재 좌석에 true를 줄 수 있고, 그렇지 않은 경우 현재 좌석에서 탐색을 멈춤
7. 아래 방향 이동인 경우 바로 아래 인덱스(y축 이동)가 false일 경우에만 현재 좌석에 true를 줄 수 있고, 그렇지 않은 경우 현재 좌석에서 탐색을 멈춤
8. 왼쪽 방향 이동인 경우 바로 전 인덱스(x축 이동)가 false일 경우에만 현재 좌석에 true를 줄 수 있고, 그렇지 않은 경우 현재 좌석에서 탐색을 멈춤
9. 위 5 ~ 8번 과정을 수행하면서 좌석 번호를 1번 부터 증가시키고, 좌석 번호가 K값과 일치 할 때까지 위 과정을 반복하고 그 때의 (x, y) 좌표를 계속해서 기억해줌으로써 문제를 해결함

5. 전체 코드

//
//  main.swift
//  Seat
//
//  Created by 이영재 on 2022/02/20.
//MARK: - seat

//MARK: - Frameworks
import Foundation

//MARK: - Types
struct Seat {
    //MARK: - Properties
    var R: Int  //좌석의 가로크기
    var C: Int  //좌석의 세로크기
    var array: Array<Array<Bool>>   //공연장 좌석
    
    //MARK: - Initializer
    init(_ R: Int, _ C: Int) {
        self.R = R
        self.C = C
        self.array = Array(repeating: Array(repeating: false, count: self.C + 10), count: self.R + 10)
    }
}

//MARK: - Functions
func solution() -> Void {
    //MARK: - input
    guard let input = readLine()?.components(separatedBy: " ") else { return }
    guard let K = Int(readLine() ?? "0") else { return }
    let R = input.map { Int($0) }[0] ?? 0
    let C = input.map { Int($0) }[1] ?? 0
    
    var seat: Seat = Seat(R, C)
    var seatX: Int = 1
    var seatY: Int = seat.C
    
    for i in 0...(seat.R + 1) {
        seat.array[0][i] = true
        seat.array[seat.C + 1][i] = true
    }
    
    for i in 1...seat.C {
        seat.array[i][0] = true
        seat.array[i][seat.R + 1] = true
    }
    
    //MARK: - process
    if K > seat.R * seat.C {
        print(0)
    } else {
        var x: Int = 1
        var y: Int = seat.C
        var seatCount: Int = 1
        
        while seatCount < K {
            //위
            for i in stride(from: y, through: 1, by: -1) {
                if seatCount >= K {
                    break
                }
                
                if !seat.array[i - 1][x] {
                    seat.array[i][x] = true
                    seatCount += 1
                    seatY -= 1
                } else {
                    y = i
                    break
                }
            }
            if seatCount >= K {
                break
            }
            
            //오른쪽
            for i in x...seat.R {
                if seatCount >= K {
                    break
                }
                
                if !seat.array[y][i + 1] {
                    seat.array[y][i] = true
                    seatCount += 1
                    seatX += 1
                } else {
                    x = i
                    break
                }
            }
            if seatCount >= K {
                break
            }
            
            //아래
            for i in y...seat.C {
                if seatCount >= K {
                    break
                }
                
                if !seat.array[i + 1][x] {
                    seat.array[i][x] = true
                    seatCount += 1
                    seatY += 1
                } else {
                    y = i
                    break
                }
            }
            if seatCount >= K {
                break
            }
            
            //왼쪽
            for i in stride(from: x, through: 1, by: -1) {
                if seatCount >= K {
                    break
                }
                
                if !seat.array[y][i - 1] {
                    seat.array[y][i] = true
                    seatCount += 1
                    seatX -= 1
                } else {
                    x = i
                    break
                }
            }
            if seatCount >= K {
                break
            }
        }
        
        //MARK: - output
        print("\(seatX) \((seat.C - seatY + 1))")
    }
}
solution()

 

전체코드는 여기에서 확인할 수 있습니다.