[Python] 백준 10431번 - 줄세우기

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

 

 

나의 답 - 틀린 버전

import sys

P = int(input())

for _ in range (P):

    cnt = 0
    
    li = sys.stdin.readline().split()

    print(li[0],end=" ")

    li = li[1:]

    for i,value in enumerate (li):
        
        for ci, compare in enumerate(li[:i]):
            if value < compare:
                li.remove(value)
                li.insert(ci,value)
                cnt += i-ci
                break
    print(cnt)

 

순서대로 검사를 한다.

자기 자신보다 앞에 있는 큰 숫자중에 가장 앞에 있는 수 앞으로 가야하니,

이 숫자를 발견하며 그 앞에 삽입을 한 후 삭제를 하는 방식으로 했다. 

근데, 테스트 케이스는 맞았는데 틀렸다고 나왔다..

 

그래서 왜 틀렸나 보니까 이 문제는 삽입정렬로 풀어야 하는 문제 !

remove를 하고 insert를 하는 도중에 인덱스 오류가 나올 수 있다고 한다.

 

GPT 답변

코드가 일부 테스트 케이스에서 틀릴 수 있는 이유는 list.remove(value)와 list.insert(ci, value)를 사용하면서 리스트의 길이가 변하고, 그로 인해 인덱스가 예상치 못한 방식으로 바뀌기 때문입니다. 이로 인해 코드가 예상대로 동작하지 않을 수 있습니다.

이 문제는 학생들을 줄세우는데, 삽입 정렬 방식을 사용하여 이동 횟수를 세는 문제입니다. 한 가지 방법은 직접 리스트를 조작하는 대신, 삽입 정렬 방식을 사용하여 이동 횟수를 세는 것입니다.

 

나의 답 - chatGPT 응용한..

import sys

P = int(input())

for _ in range(P):

    cnt = 0
    
    li = sys.stdin.readline().split()

    print(li[0], end=" ")

    li = list(map(int, li[1:]))

    for i in range(1, len(li)):
        value = li[i]
        j = i
        while j > 0 and li[j-1] > value:
            li[j] = li[j-1]
            j -= 1
            cnt += 1
        li[j] = value
    
    print(cnt)

 

그래서 삭제하고 insert하는 부분을 바꿔줬다.

삭제를 하는 대신 삽입정렬을 사용했따.

 

value를 담아두고, 삽입할 위치를 찾으면 위치 뒤에 있는 숫자들은 한 칸씩 뒤로 보내고 count

whle문 다 돈 후에 삽입할 위치에 값 넣기.. !

 

Kotlin 버전 답

mport java.util.*

fun main() {
    val scanner = Scanner(System.`in`)
    val P = scanner.nextInt()

    for (i in 0 until P) {
        var cnt = 0

        val caseNumber = scanner.nextInt()
        print("$caseNumber ")

        val li = IntArray(20) { scanner.nextInt() }

        for (j in 1 until li.size) {
            val value = li[j]
            var k = j
            while (k > 0 && li[k - 1] > value) {
                li[k] = li[k - 1]
                k -= 1
                cnt += 1
            }
            li[k] = value
        }

        println(cnt)
    }
}

 

느낀 점

삽입정렬 정말 헷갈린다.. 

remove 보다 정렬을 ... 사용해보기 !