Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | ||||
4 | 5 | 6 | 7 | 8 | 9 | 10 |
11 | 12 | 13 | 14 | 15 | 16 | 17 |
18 | 19 | 20 | 21 | 22 | 23 | 24 |
25 | 26 | 27 | 28 | 29 | 30 | 31 |
Tags
- 3dgs
- Python
- 미지의 공간탈출
- 토스
- 삼성빈출
- 그래프탐색
- 20006
- 20922
- 시계토끼제니쌤
- 그리디
- 토스독학
- 삼성코테기출
- 토스만능문장
- 그래프
- DP
- mcp란
- mcp튜토리얼
- 시뮬레이션
- 토익스피킹
- 28215
- 백준
- 토스유튜브
- 코테
- BFS
- 최단거리추적
- 너비우선탐색
- 그리디알고리즘
- mcp사용법
- 구현
- 수학
Archives
- Today
- Total
Victory in my life
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하면 주르르 나온다는거... 꿀팁이다 ㅎ
'CodingTest > Baekjoon' 카테고리의 다른 글
Baekjoon 14940 | 쉬운 최단거리 (Python) (0) | 2025.02.26 |
---|---|
Baekjoon 2178 | 미로 탐색(Python) (0) | 2025.02.25 |
Baekjoon 20006 | 랭킹전 대기열(Python) (0) | 2025.02.24 |
Baekjoon 1913 | 달팽이(Python) (0) | 2025.02.21 |
Baekjoon 14916 | 거스름돈 (Python) (0) | 2025.02.19 |