Baekjoon 1138 | 한 줄로 서기(Python)

📌문제

SILVER2 / 구현 / 그리디 알고리즘

https://www.acmicpc.net/problem/1138

📌문제 분석 및 설계

 

문제와 예제를 보니 자신보다 작은 사람이 왼쪽에 몇 명 있는지를 고려해야 한다는 점을 발견했다.

 

1️⃣ 키가 1인 사람의 자리 결정

• 키가 1인 사람은 자신보다 작은 사람이 없으므로,
  → 자신보다 키가 큰 사람 수에 해당하는 인덱스에 배치된다.

2️⃣ 키가 큰 사람들의 자리 결정 (키 ≥ 2)

• 키가 2 이상인 사람들은 왼쪽에 있는 작은 사람의 수를 고려해야 한다.
• 자신보다 작은 사람이 이미 배치되어 있다면, 원래 있어야 할 자리보다 더 뒤로 가야 한다.

3️⃣ 예제 상황 분석

• 예를 들어, 키가 3번인 친구가 줄을 설 차례이고,
  • 왼쪽에 키가 큰 사람이 1명 있다.
  • 현재 줄의 상태가 (비어있음), 2, 1, (비어있음) 이라면,
  • 원래 index 1에 3번 친구가 배치되어야 하지만,
  • 이미 작은 키(2)가 차지하고 있으므로 index+1로 이동.
  • 그런데 그 자리에도 작은 키(1)가 있으므로 index+2가 최종 자리.

4️⃣ 핵심 설계 로직

• 자기보다 키가 큰 사람 수(k)를 기준으로 초기 자리 설정
• 왼쪽에서 작은 키의 사람을 발견할 때마다 k를 증가
• 이렇게 하면 자신의 자리를 자연스럽게 찾을 수 있다.

💡 즉, 자기보다 작은 사람이 이미 자리를 차지하고 있다면, 그만큼 자신의 자리도 뒤로 이동해야 한다!

 

그 외 고려한 사항은 

• line을 초기화 할때 0이 아닌 N+1로 한것이다. 왜냐하면 나의 시스템에서 0으로 초기화를 하면 자기보다 작은 사람 카운팅할때 카운팅되기 때문에 n+1로 설정했다.

 

📌소스 코드

n=int(input())
tall_i=list(map(int,input().split()))
line=[n+1]*n

for i,t_i in enumerate(tall_i):
    if i==0:
        line[t_i]=i+1
    else:
        turn=0
        low_cnt=0
        k=t_i+1
        while turn<k:
            if line[turn]<i+1:
                low_cnt+=1
                k+=1
            turn+=1
        line[t_i+low_cnt]=i+1

for t in line:
    print(t,end=' ')

 

지피티한테 보여주니 기존 코드에서 while 내부에서 loop를 계속 증가시키는 방식이 아니라, 한 번만 스캔하면서 배치하여 연산량을 줄여서 코드를 더 간단하게 아래와 같이 만들어줬다. 하지만 나는 이해가 촘 안가기도하고.. 그렇다 ...

 

n = int(input())
tall_i = list(map(int, input().split()))
line = [-1] * n  # 초기값을 -1로 설정

for i in range(n):
    count = tall_i[i]  # 왼쪽에 있어야 할 큰 키 사람 수
    for j in range(n):
        if line[j] == -1:  # 빈자리일 때만 count 감소
            if count == 0:  # 왼쪽에 있어야 할 사람 수를 모두 찾았으면 배치
                line[j] = i + 1
                break
            count -= 1

print(*line)

 

그리고 새로 안 건 *line하면 주르르 나온다는거... 꿀팁이다 ㅎ