[Python 3] BOJ 30619: 내 집 마련하기

 

 

오늘 풀어볼 문제는 '내 집 마련하기' 이다.

예전에 서강대학교 프로그래밍 대회에서 1번 문제로 나왔었던 문제인데, 조금 복잡했던 구현 문제이다.

 

우선적으로 조금 어려운 부분은, '문제를 정확하게 읽어야 된다'는 점이다.

문제에 주어진 표현은 i번째 집에 A_i번 사람이 배정되어있다고 하는데, 

즉 문제에 표현된 방식은 1번과 같은, 집 기준이다.

하지만 문제에서 sorting 해야하는 것은 L번 사람부터 R번 사람, 즉 사람 기준이다.

그렇기 때문에, 기준을 사람으로 변경해주어야 한다.

먼저 이후 정렬을 통해서, 작은 집의 번호를 가진 사람이 작은 집에 살고, 큰 집의 번호를 가진 사람이 높은 번호의 집에 살아야 최적의 세금 감면 효과가 이루어지기 때문에, 오름차순으로 L번 사람부터 R번 사람의 집들을 정렬한다.

이후 다시 수열 A를 작성해야 하기 때문에, 다시 집 기준으로 기준점을 옮긴다.

 

여기서 효과적으로 사용할 수 있는 파이썬의 함수는 바로 enumerate이다. 

enumerate는 특정 리스트를 (인덱스, 값)으로 변경시켜준다.

즉,

data=[a,b,c]
new_data=enumerate(data)
for i in new_data:
	print(i)

를 하면,

(0,'a')
(1,'b')
(2,'c')

가 출력된다.

이를 이용해서, 서로의 인덱스와 값을 변경해주어서 쉽게 기준을 변경할 수 있다.

from copy import deepcopy
n=int(input())
data=[0]+list(map(int,input().split()))
house=[0 for _ in range(n+1)]
for index,person in enumerate(data):
    house[person]=index
m=int(input())
for _ in range(m):
    left,right=map(int,input().split())
    temp=deepcopy(house)
    temp=temp[:left]+sorted(temp[left:right+1])+temp[right+1:]

    answer=[0 for _ in range(n+1)]
    for i,person in enumerate(temp):
        answer[person]=i
    print(*answer[1:])