[Baekjoon] 10431. 줄세우기

문제 바로가기

🔍 나의 코드

# 줄세우기

t = int(input()) #테스트 케이스 수

for _ in range(t):

    height = list(map(int, input().split()))[1:] #20명의 키 정보
    cnt = 0 #물러서는 횟수

    for i in range(20):
        while i>0: # height의 2번째 학생부터 정렬
            if height[i] < height[i-1]: # 앞의 학생보다 작은경우
                height[i], height[i-1] = height[i-1], height[i] # 앞의 학생과 자리를 바꾼다.
                cnt += 1 # 물러서는 횟수 +1
                i -= 1 #그 다음 앞에 있는 학생과 비교하기위해
            else: break # 앞의 학생보다 큰 경우(정렬할 필요가 없는 경우) 
    
    print(_+1, cnt)

코드 풀이

버블정렬을 이용하였지만 살짝 다른 방식으로 풀었다.
서로 인접한 두 원소를 비교한 후, 교환할때마다 물러서는 횟수를 카운트해주었다.

7 4 5 1 3

인덱스[1]과 앞의 원소들간의 비교를 시작한다. [1]이 [0]보다 크므로 교환
4 7 5 1 3

인덱스[2] (숫자5) 와 앞의 원소들간의 비교를 시작한다.
[2]가 [1]보다 크므로 교환
숫자 5는 숫자 4보다 크므로 교환하지 않는다.
4 5 7 1 3

인덱스[3] (숫자1) 와 앞의 원소들간의 비교를 시작한다.
...

🔍 다른 코드

굳이 위 처럼 하지않고 버블정렬 정석대로 풀어도 결과는 같다.

def bubble_sort(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):
    height = list(map(int, input().split()))[1:] #20명의 키 정보
    cnt = 0 #물러서는 횟수

    bubble_sort(height)
    print(_+1, cnt)

Reference

Comment

원래는 중첩 for문으로 풀려다가 안풀려서 다른 사람의 코드를 보고 '버블정렬'이라는 힌트를 얻어 다시 풀어보았다.
문제 설명이 길어서 핵심을 못찾았던것 같다.
문제에서 설명한 알고리즘대로 풀려고 하지 말자.