Python 백준 14562번 - 나는 행복합니다~, (메모리 초과 해결)

문제

“나는 행복합니다~ 한화라서 행복합니다~”

행복한 이 노래 가사! 그렇다. 욱제는 한화 이글스의 열렬한 이다. 욱제는 여름방학을 맞아 치킨과 맥주를 챙겨 야구장을 방문했다! 하지만 이게 웬걸? 치맥에 정신이 팔린 욱제는 그만 자신의 관중석 위치가 담긴 티켓을 잃어버리고 말았다. 욱제가 유일하게 기억하는 것이라고는 자신의 관중석 번호 K뿐이다.

당신은 한화 이글스의 감독이다. 열혈 팬인 욱제의 방문에 깊은 감동을 받은 당신은 욱제가 잃어버린 자리를 찾아주려고 한다. 오늘 경기가 펼쳐지는 잠실구장은 세로 길이가 N, 가로길이가 M인 N*M 크기의 관중석을 가지고 있다. 관중석의 왼쪽 위는 (0, 0), 오른쪽 아래는 (N-1, M-1)으로 표시된다. 각 관중석에는 번호가 아래 그림처럼 매겨져 있다. (0, 0)에서부터 0번으로 시작하여 오른쪽으로, 끝에 다다르면 그 아래에서 또 오른쪽으로 숫자가 증가해나가는 식이다.

당신은 관중석의 크기와 욱제 자리의 번호를 알고 있다. 욱제가 잃어버린 자리는 어디일까? 자리를 찾아서 욱제에게 알려주도록 하자!

 

입력

첫째 줄에 관중석의 크기를 나타내는 N, M과 잃어버린 관중석 번호를 나타내는 K가 주어진다. (1 <= N, M <= 30,000, 0 <= K <= N*M-1)

출력

자리의 좌표를 (n,m) 출력하면 된다.

 

첫 번째 시도

해당 코드를 보면 이차원 리스트(배열)를 선언한 후 해당 리스트에 값을 추가하면서 만약 해당 자리(seat)가 나오면 출력하도록 생각하였고 그렇게 코드를 작성하였다.

그러나 문제가 발생했다. 메모리 초과에러가 발생하여 어떤 게 문제인지 생각을 해보았다.

생각을 해보니 입력값에서 30000 * 30000 짜리의 이중 리스트(배열)를 만드는 것이 문제라고 거의(?) 확신하였고, 이렇게 선언해놓고 로컬에서 최악의 경우를 시도해보니 콘솔에서 너무 오래 걸리는 것을 확인하였다.

 

두 번째 시도

해당 문제를 이차원 리스트가 아닌, 수학적으로 계산하여 인덱스를 접근하고자 하였다.

입력 예시의 가로(row : 행)와 세로(column : 열)를 보니 행을 기준으로 입력이 되는 것을 확인하였다. 자리(seat)는 반드시 이중 리스트 안에 존재하는 수 일 것이고, 가로를 기준으로 자른다면 O(1)의 시간 안에 찾아낼 수 있을 것이라고 생각이 들었다. 그래서 코드를 보면 좌석의 범위를 찾아내어, 그 범위 안에서 인덱스를 추출하도록 작성하였다.

import sys
 
input_numbers = list(map(int, list(sys.stdin.readline().split())))
 
counter = 1
column = 0
flag = False
seat = input_numbers[2]
 
while flag != True:
    if seat < (input_numbers[1]*counter):
        row = counter
        break
    counter += 1
 
for x in range((row-1)*input_numbers[1], row*input_numbers[1]):
    if x == seat:
        print(row-1, column)
        break
    column += 1