[백준/파이썬][Silver III] Out of Place - 15594

[Silver III] Out of Place - 15594

문제 링크

성능 요약

메모리: 108384 KB, 시간: 88 ms

분류

그리디 알고리즘, 정렬

제출 일자

2025년 2월 13일 02:18:14

문제 설명

Feeling ambitious, Farmer John plans to attempt something that never seems to go quite right: he wants to take a photograph of his entire herd of cows.

To make the photograph look nice, he wants the cows to line up in a single row from shortest to tallest. Unfortunately, right after he has the cows line up this way, Bessie the cow, always the troublemaker, steps out of line and re-inserts herself at some other location in the lineup!

Farmer John would like to swap pairs of cows so the entire herd is again lined up properly. Please help him determine the minimum number of swaps he needs to make between pairs of cows in order to achieve this goal.

입력

The first line of input contains N$N$ (2≤N≤100$2 \leq N \leq 100$). The next N$N$ lines describe the heights of the cows as they are lined up after Bessie makes her move. Each cow height is an integer in the range 1…1,000,000$1 \ldots 1,000,000$. Cows may have the same height.

출력

Please output the minimum number of times Farmer John needs to swap pairs of cows in order to achieve a proper ordering. Swaps do not necessarily need to involve adjacent cows in the ordering.

풀이

rows = [0]

N = int(input())
for _ in range(N) :
    cow = int(input())
    if rows[-1] == cow :
        continue
    rows.append(cow)

rows_copy = rows.copy()
cnt = 0
ans = sorted(rows)
# 1번 풀이
while ans != rows :
    for i in range(2, len(rows)) :
        if rows[i-1] > rows[i] :
            rows[i-1], rows[i] = rows[i], rows[i-1]
            cnt += 1

print(cnt)

# 2번 풀이
cnt = 0
for x, y in zip(rows_copy, ans) :
    if x != y :
        cnt += 1

print(max(0, cnt-1))

1번 풀이는 문제에 따라 그냥 구현한 결과이다. 딱히 풀이는 필요하지 않다고 생각한다.

2번 풀이는 조금 더 생각한 사람의 결과이다. 만약 자리가 다르다면 움직이는 소들의 수는 $자리를 바꾸는 소 - 1$ 이 될것이다. 따라서 cnt에 수가 현재의 배치와 원하는 배치에 따라서 다른 소들의 수를 구하고 -1 을 해주면 정답이 나오게 된다. 이때 첫 배치가 원하는 배치이면 정답이 -1로 나오게 되므로 max 함수를 이용해 0 미만으로 떨어지지 않도록 한다.

지금 풀이가 2가지 방법 다 나타냈기 때문에 무작정 복사해서 붙이지 마시고, 한 번 정독 후 자신이 잘 이해가 되는 풀이로 찾아가시길 바란다