반응형
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개월만에 알고리즘 스터디원들이 모여 재미있게 진행했다.
- 앞으로는 조금 더 자주 볼 수 있기를 기대한다.
반응형
'Algorithm' 카테고리의 다른 글
| Baekjoon 백준 알고리즘 - 분산처리 ( 1009 ) (0) | 2024.10.28 |
|---|---|
| Baekjoon 백준 알고리즘 - 한 줄로 서기 ( 2852 ) (0) | 2024.10.14 |
| Baekjoon 백준 알고리즘 - 풍선 터뜨리기 ( 2346 ) (0) | 2024.06.23 |
| Baekjoon 백준 알고리즘 - DNA ( 1969 ) (1) | 2024.04.14 |
| (python) forloop 와 list comprehension 의 차이 (0) | 2024.04.11 |