구현(자리배정/S4) - 10157번

1. 문제

어떤 공연장에는 가로로 C개, 세로로 R개의 좌석이 C×R격자형으로 배치되어 있다. 각 좌석의 번호는 해당 격자의 좌표 (x,y)로 표시된다.

예를 들어보자. 아래 그림은 가로 7개, 세로 6개 좌석으로 구성된 7×6격자형 좌석배치를 보여주고 있다. 그림에서 각 단위 사각형은 개별 좌석을 나타내며, 그 안에 표시된 값 (x,y)는 해당 좌석의 번호를 나타낸다. 가장 왼쪽 아래의 좌석번호는 (1,1)이며, 가장 오른쪽 위 좌석의 번호는 (7,6)이다. 

(1, 6)						(7, 6)
			(4, 4)			(7, 4)
(1, 3)					(6, 3)
(1, 2)
(1, 1)	(2, 1)	(3, 1)				(7, 1)

이 공연장에 입장하기 위하여 많은 사람이 대기줄에 서있다. 기다리고 있는 사람들은 제일 앞에서부터 1, 2, 3, 4, . 순으로 대기번호표를 받았다. 우리는 대기번호를 가진 사람들에 대하여 (1,1)위치 좌석부터 시작하여 시계방향으로 돌아가면서 비어있는 좌석에 관객을 순서대로 배정한다. 이것을 좀 더 구체적으로 설명하면 다음과 같다.

먼저 첫 번째 사람, 즉 대기번호 1인 사람은 자리 (1,1)에 배정한다. 그 다음에는 위쪽 방향의 좌석으로 올라가면서 다음 사람들을 배정한다. 만일 더 이상 위쪽 방향으로 빈 좌석이 없으면 오른쪽으로 가면서 배정한다. 오른쪽에 더 이상 빈자리가 없으면 아래쪽으로 내려간다. 그리고 아래쪽에 더 이상 자리가 없으면 왼쪽으로 가면서 남은 빈 좌석을 배정한다. 이 후 왼쪽으로 더 이상의 빈 좌석이 없으면 다시 위쪽으로 배정하고, 이 과정을 모든 좌석이 배정될 때까지 반복한다. 

아래 그림은 7×6공연장에서 대기번호 1번부터 42번까지의 관객이 좌석에 배정된 결과를 보여주고 있다.

6	7	8	9	10	11	12
5	26	27	28	29	30	13
4	25	38	39	40	31	14
3	24	37	42	41	32	15
2	23	36	35	34	33	16
1	22	21	20	19	18	17

여러분은 공연장의 크기를 나타내는 자연수 C와 R이 주어져 있을 때, 대기 순서가 K인 관객에게 배정될 좌석 번호 (x,y)를 찾는 프로그램을 작성해야 한다. 

 

2. 입력

첫 줄에는 공연장의 격자 크기를 나타내는 정수 C와 R이 하나의 공백을 사이에 두고 차례대로 주어진다. 두 값의 범위는 5 ≤ C, R ≤ 1,000이다. 그 다음 줄에는 어떤 관객의 대기번호 K가 주어진다. 단 1 ≤ K ≤ 100,000,000이다.

7 6
11

 

7 6
87

 

100 100
3000

 

3. 출력

입력으로 제시된 대기번호 K인 관객에게 배정될 좌석번호 (x,y)를 구해서 두 값, x와 y를 하나의 공백을 사이에 두고 출력해야 한다. 만일 모든 좌석이 배정되어 해당 대기번호의 관객에게 좌석을 배정할 수 없는 경우에는 0(숫자 영)을 출력해야 한다. 

6 6

 

0

 

9 64

 

 

4. 코드

import sys

c, r = map(int, sys.stdin.readline().strip().split())
k = int(sys.stdin.readline())
# 입력 받은 크기의 0으로 이루어진 배열 생성
seats = [[0 for _ in range(r)] for _ in range(c)]

# 대기번호 k가 c*r 보다 크다면 0을 출력한다.
if k > c * r:
  print(0)
else:
  # 처음좌표
  x, y = 0, 0
  # 이동좌표
  moveX = [0,1,0,-1]
  moveY = [1,0,-1,0]
  # 대기번호
  no = 0
  # 이동좌표단계
  step = 0

  while True:
    no += 1
    # 대기번호가 같으면 결과값 출력
    if no == k:
      print(x + 1, y + 1)
      break
    
    seats[x][y] = no
    # 이동할 좌표
    a, b = x + moveX[step], y + moveY[step]
    # 이동할 좌표가 있다면
    if 0 <= a < c and 0 <= b < r and seats[a][b] == 0:
      x, y = a, b
    # 이동할 좌표가 없다면 이동좌표를 변경
    else:
      step = (step + 1) % 4
      x, y = x + moveX[step], y + moveY[step]
      a, b = x,y

 

5. 풀이설명

① 입력 받은 c×r의 크기의 0으로 이루어진 배열을 생성한다.

 

② 입력받은 k가 c×r보다 크면 결과값으로 0을 출력한다.

 

③ 초기 좌표와 이동좌표, 대기번호를 생성한다.

 

④ ①에서 생성한 배열seats에 대기번호 n을 대입하고 다음 좌표로 이동한다.

 

⑤ 다음 이동할 좌표가 0보다 크거나 같고 입력값 c, r 보다 작으며 0일경우 x, y 에 이동할 좌표 a.b를 대입힌다.

 

⑥ ⑤에서 이동할 좌표가 없을 경우 이동 좌표 단계 step을 다음 step으로 변경하여 x, y 에 대입하고 다시 a, b에 대입한다.

 

⑦ 대기번호 n이 입력값 k와 같으면 x+1, y+1을 결과값으로 출력하고 break문으로 종료한다.

 

 

 

6. 느낀점

구현하는데도 꽤 애먹었지만 시간초과가 계속 나와서 코드 정리하는데 시간이 많이 걸렸다.