소프티어

시간 초과의 가능성

안녕하세요, 파이썬으로 문제 풀이 후 궁금한 점 있어서 글을 남깁니다. 풀이는 유튜브에 업로드 된 해설의 코드를 그대로 사용하였습니다. 문제에서 4중 for문을 사용하는데, Worst case의 경우 하나의 입력문에 대해 (20)^4=16*10^4 번의 연산을 거친다고 이해하였습니다. 여기에 Q의 최댓값이 3*10^4라면 최대 연산량이 (3*10^4)*(16*10^4)=48*10^8 의 연산량을 가지는 것이 아닌가요? 파이썬에서 1초 당 10^8 정도의 연산을 할 수 있다고 알고 있는데, 그렇다면 이 경우에는 해당 풀이가 시간 초과가 날 것이라 판단해야 하는것이 아닌지 궁금합니다. 제가 시간 복잡도 계산이 미숙하여 실수했을 수도 있을 것 같습니다. 이 문제의 경우 시간 초과가 나지 않을 것이라는 것을 어떻게 판단해야 할까요?

반례랑 왜 틀렸는지 알고 싶습니다...

import sys input = sys.stdin.readline # N행 M열 # 거리가 같으면 가로 길이부터 세로 순서로 N, M, Q = map(int, input().split()) # id의 0번 인덱스가 IN, id의 1번 인덱스가 OUT inAndOut = [[0, 0] for _ in range(1001)] # 대각선으로 일단 위치를 스택에 넣는다. seats = [] whereSeat = dict() dr = [-1, 1, 0, 0] dc = [0, 0, -1, 1] def isValid(nr, nc): return 0 <= nr < N and 0 <= nc < M def findSeat(io, id): now = inAndOut[id] if io == "In": if now[0]: if now[1]: return f"{id} already ate lunch." return f"{id} already seated." # 자리 찾기 # 찾은 자리 넣기 # 자리가...

좌석관리, 런타임에러가 나옵니다...

예제 테스트케이스는 잘 돌아갑니다. 제가 만든 테스트케이스들도 잘 돌아가고요. 근데 제출을 하면 1번 빼고는 나머지는 전부 런타임에러입니다. 메모리 관리를 못한건가요...? 계산해봐도 그건 아닌거 같은데 ㅠㅠ 도와주세요 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.HashSet; import java.util.LinkedList; import java.util.StringTokenizer; public class Main { static int[][] map; static LinkedList list; static HashSet isIn, isOut; static int N, M; public static void main(String[] args) throws Exception { // TODO Auto-generated method s...

[21년 재직자 대회 예선] 좌석관리

입력 예제 2번을 보면 4 X 4 2차원 배열을 가지고 (1,1)을 가지고 가장 안전한(먼) 좌석을 추천하는 것으로 이해하고 있는데요. (1, 1) -> (4, 4) -> (1, 4) 순으로 출력이 되는데... (1, 1) -> (4, 4) -> (1, 3) 이 아닌가 해서요. (4, 4) -> (1, 4) 거리는 3, (4, 4) -> (1, 3)은 3.16으로 더 안전한 좌석이지 않나 해서요 제가 잘못 이해 한 것인지....조언 좀 부탁드립니다. 미리 감사합니다.

[21년 재직자 대회 예선] 좌석관리

아래 코드를 제출한 후 상세보기를 보니까 모든 테케가 오답인데요. 반례 알려주시면 감사하겠습니다. 혹시 제가 출력을 잘못하고 있는건가요? import sys N,M,Q = input().split(' ') N = int(N) M = int(M) Q = int(Q) in_queue = [] in_dict = {} out_queue = [] dx = [-1,1,0,0] dy = [0,0,-1,1] def print_map(): for i in map: print(i) def cal_seat(user_id): max_safe = 0 max_x = 0 max_y = 0 no_seat = True for i in range(N): for j in range(M): if map[i][j] == 0: flag = False for tmp in range(4): nx = i+dx[tmp] ...

[21년 재직자 대회 예선] 좌석관리 질문

푸신 분께 여쭈어 봅니다. 좌석의 우선순위를 어떤 식으로 갱신해줘야 하는가요? 자리를 앉을 때, 나갈 때 어떤식으로 전체 좌석의 우선순위를 갱신해 주셨나요?? 해설 혹은 모범 답안이 있으면 참고해 보겠습니다. 감사합니다.