[백준/Python] 1138 한 줄로 서기

 

처음에 생각했던 방법은 처음 나온 0의 인덱스를 제일 처음에 놓고,

그 다시 people을 처음부터 끝까지 돌면서 자기보다 작은 숫자가 몇개 있나 세서,

그 수랑 people에 있는 수가 같은 수의 인덱스를 두번째에 놓고···

하는 방법이었는데, 뭔소린지 모르시겠죠?

당연함.. 나도 모르겠음ㅠ

 

암튼 그래서 인덱스랑 자기보다 큰 사람이 왼쪽에 몇명있는지를 dictionary로 해서 해보려고 했어요,,

근데 아무리 생각해도 계속 비교하느라고 for문을 돌면 너무 시간이 오래 걸릴 거 같은 거에요

그래서 막 이진탐색을 해? 그럼 sorting을 해야돼? 이렇게까지? 이러면서 삽질 오지게 하다가

결국 구글링을 했어요^^ 3시간만에^^ 진짜 혼자 풀어보고 싶었는데......^^ㅎ;

 

 

대략적인 아이디어는 앞 번호부터 앞 자리에 채우는 방식이었는데,

" 그리디 알고리즘 "을 사용하는 것이었어요

 

첫번째 입력 예제를 활용해 선택해보면

[0, 0, 1, 0]

[0, 2, 1, 0]

[0, 2, 1, 3]

[4, 2, 1, 3]

으로 첫 번째 사람 왼쪽에는 2명의 키 큰 사람이 있으므로 result[2] 에 인덱스를 넣어줍니다

두번째, 세번째, ··· 마지막 사람까지 인덱스를 넣어주는데,

만약 result[i]에 이미 다른 사람이 있다? 그러면 result[i+1] ··· 해서 가장 가까운 오른쪽에 있는 곳에 넣어주면 됩니다

 

뭔소린지 모르시겠져? 설명을 너무 못하져,,

코드 먼저 보고, 코드를 하나하나 차근차근 푼 사진을 올릴게요,,,

N = int(input())
people = list(map(int, input().split()))
result = [0] * N

for i in range(N):
    cnt = 0
    for j in range(N):
        # 조건 1
        if cnt == people[i] and result[j] == 0:
            result[j] = i + 1
            break
        # 조건 2
        elif result[j] == 0:
            cnt += 1
            
for i in result:
    print(i, end=' ')

풀이과정

1. people을 순서대로 돌리는 첫 번째 for문

 

2. result에 인덱스를 넣는 두 번째 for문

2-1. (조건1) 0의 갯수가 people[i]과 같고, result[j]에 아무것도 없다면, result[j]에 인덱스(i+1) 넣기

2-2. (조건2) 아직 0의 갯수가 people[i]과 같지 않지만, result[j]가 0이라면, cnt를 1 증가

2-3. (조건3) cnt와 people[i]가 같은데, result[j]에 이미 다른 사람이 서있다면, if문을 빠져나와서 j만 1 증가

 

자세한 풀이

 

알게된 것

1. 그리디 알고리즘

그리디 알고리즘은 탐욕법 이라고도 하는데, 매 순간 선택지 중 가장 최적의 해만 고르는 방법!

그래서 최적의 해를 보장할 순 없습니다~

이 문제에서 그리디 알고리즘을 사용할 수 있었던 이유는,

순서대로 오른쪽 사람으로 가면서, 가장 최적의 위치를 찾아 줄을 세워야하기 때문입니다

(위에서 아이디어 설명하면서 얘기했던 "앞 번호부터 앞 자리에" 랑 같은 맥락)

---

요즘 코테 푸는 폼이 너무 많이 죽어서 슬프다....

한 3시간 삽질하다 구글링 했는데 그 코드 이해하는데 1시간 걸림

시간 투자를 좀 더 해야될 거 같다....