[백준 10431] 줄 세우기(python)

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

10431번: 줄세우기

줄 세우기 문제

자기 앞에 자기보다 키 큰 학생과 자리를 바꾸는 횟수를 구하는 문제

말만 길지 은근 낚시 문제

내가 푼 정답 코드

def Bubblesort(List): #정렬할 list, 원소 수 N
    global cnt
    for i in range(len(List)-1, 0, -1) : # 범위의 끝
        for j in range(i) :
            if List[j] > List[j+1] : #현재 항이 다음 항보다 클 경우
                List[j], List[j+1] = List[j+1], List[j] #서로의 위치를 바꿔라
                cnt += 1

T = int(input())
for _ in range(T):
    N, *x = map(int,input().split())
    cnt = 0
    Bubblesort(x)
    print(N, cnt)

그냥 말만 복잡하게 써놔서 직접 구현을 시도하게 만든 문제인데, 자세히 문제를 읽어보면 버블정렬에 대한 설명을 하고 있는 것을 알 수 있다.

문제 해석하면 애들을 정렬할 건데 버블 정렬로 정렬해서 몇번 정렬을 하면 끝나니? 를 묻고 있는 문제이다.

기본 버블 정렬 코드만 가져다가 cnt만 붙여주면 풀 수 있다.

반응형

---

느낀 점

낚시용 문제가 아니었나 싶은게 처음에 문제만 읽고 이게 무슨소리지 생각하느라 시간을 많이 썼는데 결국 직접 구현 할 수 도 있지만, 그냥 버블 정렬 해봐가 문제 요구사항이었다.

문제를 먼저 읽고 아는 지식 내에서 비슷한 알고리즘이 있는지 생각해보고 적용해보는 연습을 해볼 필요가 있겠다는 것을 느꼈다.