[코드트리 조별과제] 사다리 타기

 

어려움이라고 적혀있어서 상당히 쫄아

이거 얼마나 걸릴까 싶었지만 생각 정리해서 푸니까 금방 풀었다.

약간 버블 sort와 비슷하다는 생각이 들었는데

 

결론적으로 누가 어디로 가는지 확인한 다음

그 결과를 기반으로 얼마나 움직여야 하는지

backtracking 하면 된다. 

 

결과적으로 가야 하는 자리가 현재 자리에서

왼쪽인지 오른쪽인지에 따라 swap 방향을 다르게 해 주면 된다.

import sys

# 입력 처리 단계
n, m = list(map(int, sys.stdin.readline().split()))
lines = []
people = [i for i in range(1, n+1)]
for _ in range(m):
    lines.append(list(map(int, sys.stdin.readline().split())))
lines.sort(key=lambda line: line[1])

# 결과 도출 하기
result = people[:]
for a, b in lines:
    result[a-1], result[a] = result[a], result[a-1]

# swap 진행하기
count = 0
for idx, num in enumerate(result):
    target = people.index(num)
    if idx < target:
        while idx != target:
            people[target-1], people[target] = people[target], people[target-1]
            target -= 1
            count += 1
    elif idx > target:
        while idx != target:
            people[target+1], people[target] = people[target], people[target+1]
            target += 1
            count += 1
print(count)

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석