백준) 10431 - 파이썬

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

(실버 5)

10431번: 줄세우기

입력

4
1 900 901 902 903 904 905 906 907 908 909 910 911 912 913 914 915 916 917 918 919
2 919 918 917 916 915 914 913 912 911 910 909 908 907 906 905 904 903 902 901 900
3 901 902 903 904 905 906 907 908 909 910 911 912 913 914 915 916 917 918 919 900
4 918 917 916 915 914 913 912 911 910 909 908 907 906 905 904 903 902 901 900 919

출력

1 0
2 190
3 19
4 171

생각

백준 사이트 기준에서는 예제 입력의 형태와 입력 문단을 읽고 어떻게 입력을 받을지 생각한다.

 

테스트 케이스 수가 주어진다고 했으므로 p변수를 통해 받게 했다.

 

그 후 테스트 케이스의 수만큼 리스트를 이용해서 데이터 값을 입력 받는다.

이 때 처음에 들어오는 숫자는 테스트 케이스의 번호 역할을 수행하고, result 리스트는 비어 있으므로 s[1] 값을 result 리스트에 대입 후, s는 번호를 제거한다.

 

그 후 result 값의 최댓값과 비교해서 나머지 s에 들어 있는 값이 작을 경우 그냥 추가, 클 경우에는 제일 처음에 입력 받게 설계하였다.

 

마지막으로 걸음 수 측정을 위해 움직인 count수에 값을 넣기 전 result 길이를 곱해서 걸음 수를 측정하려고 했다.

내 풀이

import sys
input=sys.stdin.readline
p=int(input())
result=list()
count=0
for i in range(p):
    s=list(map(int,input().split()))
    result.append(s[1])
    s.pop(1)
    for j in range(1,len(s)):
        if max(result)<s[j]:
            result.append(s[j])
        else:
            count+=1*len(result)
            result.insert(0,s[j])
    print("{} {}".format(i+1,count))

생각의 흐름대로 코드를 구현하려고 했다.

 

리플릿 사이트에서는 테스트 케이스는 통과하였으나, 백준 사이트에서는 틀렸다고 나왔다.

개선 코드

사실 문제를 유심히 읽어보면 Bubble sort 방식으로 정렬한다는 것을 알 수 있다.

 

Bubble sort는 인접한 2개의 값을 비교해서 내림차순 기준 작은 값을 비교한 값의 앞으로 보내는 과정을 반복해서 정렬하는 과정이다.

def Bubble_sort(li):
    cnt=0
    for i in range(len(li)-1,0,-1):
        for j in range(i):
            if li[j]>li[j+1]:
                li[j],li[j+1]=li[j+1],li[j]
                cnt+=1
    return cnt

p=int(input())
for _ in range(p):
    s=list(map(int,input().split()))
    c,people=s[0],s[1:]
    print(c,Bubble_sort(people))

다른 풀이들도 살펴 보았으나 아무래도 직관적으로 가장 잘 이해가 되는 풀이를 보았다.

 

Bubble_sort 함수를 정의하고 그를 통해서 조건에 맞게 출력하였다.

 

느낀 점

최근 들어서 실버 5 문제임에도 불구하고 제대로 구현하지 못하는 경우가 많아졌다.

 

아무래도 과정을 생각하는 방법, 요령이 부족하다고 판단해서 생각의 흐름도 같이 적자고 결심했다.

 

문제의 경우 걸음 수를 측정하라고 제시 하였으나, 그 부분에서 구현이 막혀서 마지막에 제대로 구현하지 못했다.

 

조건 출력에 대해서 더 공부할 필요가 있다.