[BOJ_Python]31797. 아~파트 아파트

문제

https://www.acmicpc.net/problem/31797

 

사용 알고리즘

구현, 시뮬레이션

 

풀이

후기

1. 큰 어려움 없는 문제였다. 다만, 놓치기 쉬운 부분을 다시 깨닫게 해주는 문제이다.

처음에는 당연히 1 ~ 2N 사이의 숫자들로만 층이 구성된다고 생각하고 구현하였다.

하지만 계속 오답이였고, 이는 그런 조건이 없다는 것을 깨닫고 너무 당연하게 제한을 두었다는 걸 알게되었다.

처음에는 2N 크기의 리스트를 만들어서 풀었지만,

문제를 깨닫고 빈 리스트에 append 후, 층을 기준으로 정렬하는 방법을 사용했다.

 

2. 이후 술을 마실 사람을 찾는 방법은 두가지로 구현하였다.

2 - 1. 처음 떠오른 방식은 list형식의 인덱스로 접근하는 것이고, 시간효율성은 높지만 직관성이 조금 떨어진다.

2 - 2. 다른 방식은 deque를 사용하여 직접 접근하는 방식으로, 시간효율성은 낮지만 직관성이 높다.

 

코드

인덱스접근 방법

import sys
input = sys.stdin.readline

H, N = map(int, input().split())
hands = []

for i in range(1, N + 1):
    h1, h2 = map(int, input().split())
    hands.append((h1, i))
    hands.append((h2, i))
hands.sort()
print(hands[(H - 1) % (N * 2)][1])

 

deque를 사용한 직접접근 방법

from collections import deque

H, N = map(int, input().split())
hands = deque()

for i in range(N):
    H1, H2 = map(int, input().split())
    hands.append((H1, i + 1))
    hands.append((H2, i + 1))

hands = deque(sorted(hands))

for _ in range(H):
    hand = hands.popleft()
    hands.append(hand)

print(hands[-1][1])

 

결과