Python으로 푸는 SW Expert Academy 1208. Flatten

SW Expert 아카데미 1208. Flatten

 문제에서는 높은 곳의 상자를 낮은 곳에 옮기는 방식으로 최고점과 최저점의 간격을 줄이는 작업을 Python으로 구현해내려고 한다.

평탄화 작업을 위해서 상자를 옮기는 작업 횟수에 제한이 걸려 있다.

제한된 횟수만큼 옮기는 작업을 했을 때, 최고점과 최저점의 차이를 어떻게 구해낼 수 있을까.

문제 보러 가기

github에서 코드 보기

문제에서 제시한 조건

1. 한 번에 한 개의 상자만 옮길 수 있다. 이 작업을 덤프라고 한다.

2. 덤프 횟수는 제한이 있다.

3. 가로 길이는 항상 100이며 모든 위치에서 상자의 높이는 1이상 100이하로 주어진다.

4. 주어진 덤프 횟수 이내에 평탄화가 완료되면 더 이상 덤프를 수행할 수 없으므로 그 때의 최고점과 최저점의 높이 차를 반환한다.

5. 가장 높은 곳과 가장 낮은 곳의 차이는 최대 1 이내가 된다.

문제 풀기 전 결정 사항

- 덤프 횟수가 1000 이하라면 최대 1000번의 2차원 배열을 조작하여 덤프 작업을 진행해야 한다는 의미이다. 이것은 매우 비효율적이라고 생각한다.

- 모든 테스트 케이스를 입력받아서 문제를 풀면 너무 많은 메모리를 사용하므로, 메모리 사용을 줄이기 위해 yield 키워드로 generator를 사용하여 각각의 케이스별로 input 데이터를 처리하여 결과 값을 출력한다.

(Generator는 한번에 끝나지 않고 여러번에 걸쳐 입출력을 받을 수 있어 대용량 처리 함수 제작에 편리하다!)

문제 풀이 방법 

- 이 문제는 상자를 하나하나 옮기는 코드를 짤 필요가 없다.  문제에서 가로 길이는 항상 100으로 주어졌으므로, 각 층별로 최대 100개의 상자가 놓여있다는 점을 활용해야 한다.

- 그렇기 때문에 각 층마다 100개의 상자중에 몇개의 상자가 놓여있는지 계산하여 최상층의 상자를 최하층 빈 공간에 얼마나 넣을 수 있는지 숫자를 계산해 나가며풀어야 한다.

수도 코드

count_per_level = {}

while dump_count:

if box_count == vacancy:

...

if box_count > vacancy:

...

if box_count < vacancy:

...

파이썬 코드

max = 100
 
# dict : count per level (층 별 박스 수)
def calcualteBoxCount(dict, level):
    for i in range(1, level + 1):
        if str(i) in dict:
            dict[str(i)] += 1
        else:
            dict[str(i)] = 1
 
def solve(dump_count, cargo):
    global max
    count_per_level = {}
    top = 0 # 최상층
    chk_bottom = 1 # 체크중인 최저층
    bottom = 1 # 꽉 차 있는 최저층
 
    for level in cargo:
        # 최고 높이 쌓인 상자 수를 저장
        if level > top:
            top = level
        calcualteBoxCount(count_per_level, level)
 
    #dump 하기 (dump_count 이하 만큼 상자를 이동)
    while dump_count:
 
        box_count = count_per_level[str(top)] # 최상층에 놓여진 상자 수
        vacancy = max - count_per_level[str(chk_bottom)] # 남은 칸 수
 
        # 최하층이 꽉 찼을 경우 다음 최하층의 빈 칸을 검사한다
        if vacancy == 0:
            bottom = chk_bottom
            del count_per_level[str(chk_bottom)]  # 최하층도 삭제
            if top <= chk_bottom + 1:
                break
            else:
                chk_bottom += 1
                continue
 
        # 최상층이 꽉 찼을 경우 dump를 중단한다.
        if box_count == max:
            break
 
        # 옮길 상자 수 결정(옮길 상자 수는 dump_count를 넘지 못한다)
        if dump_count < box_count:
            box_count = dump_count
        result = box_count - vacancy
 
        # 옮길 상자의 수 == 빈 공간의 수
        if result == 0:
            dump_count -= box_count # 옮겨진 상자 수만큼 dump_count에서 차감
            count_per_level[str(top)] -= box_count
            count_per_level[str(chk_bottom)] += box_count
            del count_per_level[str(chk_bottom)]  # 채워진 최하층 삭제
            bottom = chk_bottom  # 채워진 최하층을 기록
 
            #최상층이 모두 비워져 있는지 체크
            if count_per_level[str(top)] == 0:
                del count_per_level[str(top)]
                top -= 1  # 다음 최상층에 옮길 상자가 있는지 확인할 수 있도록 top 값을 내려준다
            if top <= chk_bottom + 1:
                break
            chk_bottom += 1  # 다음 층에 빈 공간이 있는지 확인할 수 있도록 chk_bottom 값을 올려준다.
 
 
        # 옮길 상자 수 > 빈 공간의 수(양수)
        if result > 0:
            dump_count -= vacancy
            count_per_level[str(top)] -= vacancy # 상자를 옮겨서
            count_per_level[str(chk_bottom)] += vacancy # chk_bottom 빈공간을 채우고
            del count_per_level[str(chk_bottom)] # 최하층도 삭제
            bottom = chk_bottom # 꽉찬 최하층 체크
            if top <= chk_bottom + 1:
                break
            chk_bottom += 1 # 윗 층에 빈 공간이 있는지 확인한다.
 
 
        # 옮길 상자 수 < 빈 공간의 수(음수)
        if result < 0:
            dump_count -= box_count
            count_per_level[str(chk_bottom)] += box_count # 빈 공간을 채우고
            count_per_level[str(top)] -= box_count
            # 항상 최상위층이 비워지는 건 아니다, dump_count의 수에 따라서 안비워질수도 있음
            if count_per_level[str(top)] == 0:
                del count_per_level[str(top)] # 최상위층은 비웠으므로 삭제하고
                top -= 1  # 층 수를 내려서 그 다음 최상위 층에서 옮길 상자를 확인한다
            if top <= bottom:
                break
 
    return top - bottom
 
 
def gens():
    for i in range(10):
        dump_count = int(input())
        yield dump_count, list(map(int, input().strip().split()))
 
if __name__ == "__main__":
    num = 0
    for dump_count, cargo in gens():
        num += 1
        print('#{0} {1}'.format(num, solve(dump_count, cargo)))
 

#삼성 코딩 테스트 #1208 Flatten # Flatten python #python flatten #Flatten #삼성 기출 문제 #SW Expert Academy #삼성 flatten python #SW Expert flatten

#1208 flatten python #python 1208 flatten #파이썬 1208 flatten #1208 flatten 파이썬