Baekjoon 백준 알고리즘 - 한 줄로 서기 ( 1138 )

 

1.문제 소개

• 구현/그리디 문제유형이다.
• https://www.acmicpc.net/problem/1138

 

 

2.코드

# Main Idea :
# 	- 정답을 편하게 구하기 위해 자료구조를 만든다
# 		(lt,height)
# 		* lt = 왼쪽 방향으로 키가 큰 사람 수 
# 		* height = 키 
# 	- lt,height 순서로 정렬 한다.
# 	- 정답 배열을 만든다
# 	- 정답 배열에 lt 조건 대로 height 를 저장한다
# 	- lt 조건에 맞는지 체크하면서, 정답 배열에 들어갈 위치(cursor)를 구한다.
# 	- 정답 배열에 원소 추가
# 		- 위치(cursor) 기준으로 오른쪽 배열 복제.
# 		- 정답배열 위치(cursor)에 원소를 추가하고 + 오른 쪽 배열 복제본 복사 

def set_test_case():
    n = int(input())
    input_str = input().split(" ")
    arr = []
    input_str = list(map(int,input_str))
    for i,v in enumerate(input_str):
        arr += [(v,(i+1))]

    return arr

def solution():
    # 테스트 케이스 입력
    arr = set_test_case()

    # 왼쪽 방향 자기보다 키 큰 사람의 수 기준으로 정렬
    sorted_arr = sorted(arr, key=lambda x: x[1], reverse=True)
    # 키 큰 사람의 수가 동일할 경우 키가 큰 사람 기준으로 내림 차순 정렬
    sorted_arr = sorted(sorted_arr, key=lambda x: x[0], reverse=False)
    # 정답 배열 선언
    answer = [0] * len(sorted_arr)


    for item in sorted_arr:
        cursor = 0
        height = item[1]
        cnt = item[0]
        #lt 조건에 맞는지 체크하면서, 정답 배열에 들어갈 위치(cursor)를 찾음
        while cursor < len(arr) and answer[cursor] > 0 and cnt > 0 :
            if answer[cursor] > height :
                cnt -=1
            cursor += 1
        # 정답 배열에 원소 추가
        right_part = answer[cursor:-1]
        answer[cursor] = height
        answer[cursor+1:] = right_part

    # 정답 출력
    answer = list(map(str,answer))
    print(" ".join(answer))


if __name__ == '__main__':
    solution()

 

3.코멘트

• 단순히 입력 케이스 배열에서 규칙을 찾아 정답을 구할 수 있는 방법으로 접근하려면 더 어렵다. 유형대로 그리디하게 풀어야 한다.
• 그 동안 서로 많이 바빠서 4개월만에 알고리즘 스터디원들이 모여 재미있게 진행했다.
• 앞으로는 조금 더 자주 볼 수 있기를 기대한다.