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

문제 링크 : https://softeer.ai/practice/info.do?idx=1&eid=625 

Softeer

정답 코드

import sys
input = sys.stdin.readline

N, M, Q = map(int, input().split())
seats = [[0 for _ in range(M)] for _ in range(N)]
ids = [[0, 0, 0] for _ in range(10001)]

dr = [-1, 1, 0, 0]
dc = [0, 0, -1, 1]

def isValid(nr, nc):
    return 0 <= nr < N and 0 <= nc < M

def calDistance(sr, sc):
    minDistance = 1001
    for r in range(N):
        for c in range(M):
            if seats[r][c]:
                currentDistance = (r - sr) ** 2 + (c - sc) ** 2
                if currentDistance < minDistance:
                    minDistance = currentDistance
    return minDistance

def canSeat(personId):
    maxDistance = 0
    for r in range(N):
        for c in range(M):
            if seats[r][c]:
                continue
            validSeat, tmpSeat = 0, 0
            for d in range(4):
                nr = r + dr[d]
                nc = c + dc[d]
                if isValid(nr, nc):
                    validSeat += 1
                    if seats[nr][nc]:
                        continue
                    tmpSeat += 1
            if validSeat == tmpSeat:
                tmpDistance = calDistance(r, c)
                if tmpDistance > maxDistance:
                    maxDistance = tmpDistance
                    ids[personId] = [1, r, c]
    if maxDistance:
        seats[ids[personId][1]][ids[personId][2]] = 1
        return True
    return False

for q in range(Q):
    inAndOut, tmp = input().split()
    personId = int(tmp)
    if inAndOut == "In":
        if ids[personId][0] == 0:
            if canSeat(personId):
                print(f"{personId} gets the seat {ids[personId][1]+1, ids[personId][2]+1}.")
            else:
                print("There are no more seats.")
        elif ids[personId][0] == 2:
            print(f"{personId} already ate lunch.")
        else:
            print(f"{personId} already seated.")
    else:
        if ids[personId][0] == 0:
            print(f"{personId} didn't eat lunch.")
        elif ids[personId][0] == 2:
            print(f"{personId} already left seat.")
        else:
            print(f"{personId} leaves from the seat {ids[personId][1]+1, ids[personId][2]+1}.")
            seats[ids[personId][1]][ids[personId][2]] = 0
            ids[personId][0] = 2

코드 설명

1. 다른 사람이 앉은 자리와 현재 앉을 자리에 대한 계산이 필요하다.

2. 계산을 할 때 상하좌우 그리고 현 위치에 누가 앉아있는지 확인한다.

3. 안전도는 가장 가까이 앉아 있는 사람을 기준으로 구한다.

4. 안전도가 가장 높은 지점을 찾아서 사람을 앉힌다.

5. 사람이 앉았는지 떠났는지 아직 앉지 않았는지를 ids[personId][0]이 0인지, 1인지, 2인지를 통해서 확인한다.

 

느낀점

굉장히 빡구현(브루트포스 brute force 알고리즘?)이라는 느낌이 들었고 다시 풀어보라고 해도 오래 걸릴 것 같은 문제이다. 만약에 이런 문제가 코딩테스트에 나온다면 마지막에 풀 생각이다. 아니면 틀렸다고 봐야할지 싶다. 하지만 중요한 것은 꺾이지 않는 마음이기에 이 문제를 외울 각오로 여러 번 다시 풀어볼 생각이다. 소프티어 좌석관리 문제 알아? 아 그거 이렇게 이렇게 하면 풀 수 있어~