[백준] 10431번 줄세우기

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

 

풀이

이 문제는 오름차순으로 insertion sort를 물어보는 문제와 동일하다. 새로 입력받은 숫자를 기존 리스트의 맨 끝 idx부터 비교하여
입력받은 숫자보다 큰 경우 idx를 1칸씩 당겨가면서 비교한다.
그리고 입력받은 숫자보다 작은 숫자가 나오면 그 뒤에 새로 입력받은 숫자를 삽입한다.
이 경우 기존 숫자들은 1칸씩 밀리게 되기 때문에 이 때 이동이 발생하는 회수를 묻는 문제이다.

문제의 테스트 케이스는 최대 1000개 입력 받는 숫자는 20이기 때문에 20*20*1000으로 400000정도 연산이 수행되기 때문에 위 방법으로 풀어도 요구 시간인 1초안에 풀 수 있게된다.

 

 

data = list(map(int, input().split()))
for j in range(2, 21):

코드에서는 한번에 20개의 숫자를 입력받기 때문에 새로 입력받는 대신 list의 범위를 1씩 증가시켰다.
처음 1개는 정렬된 상태로 판단하고 idx 2번부터 20번까지 정렬 (0번에는 test_case 번호가 들어있기 때문에 실제 데이터는 1~20)

 

        for k in range(j, 1, -1): 
            if data[k] < data[k-1]:
                data[k], data[k-1] = data[k-1], data[k]
                answer += 1

현재 범위 j부터 2번 idx까지 검사하면서  현재 값이 이전 값보다 작으면 순서를 바꿔주었다. (이전 값까지 판별하기 때문에 범위는 2번 idx까지)
순서가 바뀔때마다 answer을 1씩 증가해주면 된다.

 

 

전체 코드

n = int(input())

for i in range(n):
    data = list(map(int, input().split()))
    answer = 0
    for j in range(2, 21):
        for k in range(j, 1, -1): 
            if data[k] < data[k-1]:
                data[k], data[k-1] = data[k-1], data[k]
                answer += 1
    print(f"{i+1} {answer}")

 

 

Copilot 활용

insertion sort는 단순하고 정확한 이름이 있는 알고리즘이기 때문에 copilot에게 insertion sort의 기본 예제를 만들어달라고 요청했다.

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key

# Example usage
arr = [5, 2, 8, 12, 1]
insertion_sort(arr)
print("Sorted array:", arr)

Copilot이 만들어준 코드는 예제가 이미 정해져있고 결과물 출력하는 부분이 다르기 때문에 해당 부분을 수정했다.

 

def insertion_sort(arr, n):
    count = 0
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            count += 1
            j -= 1
        arr[j + 1] = key
    print(f"{n+1} {count}")

# Example usage
n = int(input())
for i in range(n):
    arr = list(map(int, input().split()))
    insertion_sort(arr[1:], i)

n을 입력받아서 n번 데이터를 받으면서 만들어준 함수를 호출했고 결과물에 테스트 케이스 번호 + 정답을 출력하기 위해서
함수 인자로 테스트 케이스 번호를 넣어줬다. (answer을 return 받아서 main에서 출력해도 상관없음)

 

기존에 풀었던 코드보다 더 빠른 시간에 정답을 냈다. 
확실히 어떻게 사용하냐에 따라서 더 쉽게 코드를 짤 수 있을 것 같다.