의도한 풀이는 O(RC)이지만, 보다 더 좋은 별해들을 별도로 설명한다.1)O(RC)
대기 번호는 (1,1)에서 시작하여 (1,2), (1,3), (1,4), (1,5) ,.... 순으로 증가하다가 (1,R)에서 방 향을 바꿔 (2,R) , (3,R) ... 순으로 나아가게 된다. 이렇게 대기번호를 한 단계씩 늘려가면서 시뮬레이션을 통해 대기번호에 따른 좌표를 구할 수 있다.2)O(R+C)
위에서 설명한 규칙을 보면, 처음에 위로 R-1 만큼 올라간 뒤, 오른쪽으로 C-1 만큼 가고, 밑으로 R-1 만큼 내려온 뒤 왼쪽으로 C-2 만큼 가고, …, 규칙적이게 번호가 매겨진다.대기번호가 C-1,R-1,C-2,R-2,C-3,R-3, … 씩 지났을 때 방향을 바꾸게 된다. 이를 이용하여 1)에서 설명한 시뮬레이션을 묶음 단위로 할 수 있다. 이를 통해 보다 더 빨리 답을 구해낼 수 있다.
3) O(lg(Max(R,C))
대기 번호의 방향이 C-1,R-1,C-2,R-2,C-3,R-3, … 묶음 단위로 바뀐다는 특징을 보았을 때, 이는 1씩 줄어듦을 확인할 수 있다. 이를 통해, 주어진 K 가 몇 번째 묶음 단위에 속하는지 이진 탐색(Binary Search)을 통해 빠르게 구할 수 있다.K가 어느 묶음에 속하는지 알아낸 뒤에는, 그 묶음 속에서 해당 대기번호가 어디에 속하는지 계산할 수 있다.
4)O(1)
3)과 거의 유사하지만, 주어진 K 가 몇 번째 묶음 단위에 속하는지를 이진 탐색(Binary Search) 대신 이차방정식을 풀어 구할 수 있다. 이차방정식은 상수 시간안에 해결할 수 있 으므로 상수 시간 안에 해결 가능하다.