백준 1083번 sort풀이 with python(파이썬)

오늘 푼 문제는 1083번입니다

코드를 3번정도 틀린 후에 맞았습니다.

1. 정답코드 

#저는 일단 습관 처럼 input을 sys.stdin.readline으로 바꿔줍니다.
#연산이 더 빨라서 이용하다보니 그냥 처음부터 해놓는게 편하더라고요.
import sys
input=sys.stdin.readline
#입력값들 받는 부분
N=int(input())
num=[int(i) for i in input().split()]
S=int(input())
#반복문
while True:
    #무한 반복문을 끝낼 방법을 생각하다가 만든 컨트롤 변수입니다.
    control=False
    #아래는 가장 큰 수를 구해서 S보다 작으면 index로 순서를 바꿔주는 겁니다.
    for i in range(N):
        count=0
        index=i
        for j in range(i,N):
            if num[index]<num[j] and j-i<=S:
                index=j
                control=True
                count=j-i
        if(index!=i):
            change=num[index]
            del num[index]
            num.insert(i,change)
            S-=count
            break
    #바뀐부분이 없이 for문이 진행됐을 경우 무한 반복도 종료합니다.
    if control==False:
        break
# 
for i in range(N):
    print(num[i],end=' ')

정답을 맞춘 코드인데 .. 책의 도움을 받아서 풀었습니다.

책의 저자도 처음에는 단순히 i번째와 i+1번째를 비교해서 바꿔주는 식으로 만들었지만

그렇게하면 틀린 답이 나오게 됩니다.

저도 처음에 단순하게 바꿔서 풀었는데 그 코드를 보여드리겠습니다.

 

2. 오답코드

import sys
input=sys.stdin.readline
 
N=int(input())
num=[]
num=input().split()
k=int(input())
count=0
while True:
    if count==k:
        break
    for i in range(N-1):
        if(num[i]<num[i+1]):
            b=num[i]
            c=num[i+1]
            num[i]=c
            num[i+1]=b
            count+=1
            break
for i in range(N):
    print(num[i],end=' ')

솔직히 너무 쉽게 풀린다 생각해서 틀릴 것을 직감하긴했습니다.

근데 예제도 똑같이 나오길래 일단 질러보았는데 역시나 틀렸습니다라고 나오더라고요

그래서 곰곰히 생각을 하다가 책의 힌트도 봐가면서 얻은 아이디어가

바꿀 수 있는 횟수보다 작은 공간안에서의 가장 큰 수를 찾아서 바꿔주는 것이 여기서 필요한

아이디어였습니다.

 

그래서 제가 그 아이디어를 통해서 만든 코드가

 

3. 아이디어를 얻은 후 오답코드

import sys
input=sys.stdin.readline
 
N=int(input())
num=[int(i) for i in input().split()]
S=int(input())
while True:
    count=0
    for i in range(N):
        count=0
        change=0
        index=0
        for j in range(i,N):
            if num[i]<num[j] and j-i<=S:
                count=j-i
                change=num[j]
                index=j
        if(change!=0):
            del num[index]
            num.insert(i,change)
            S-=count
            break
    if count==0:
        break
for i in range(N):
    print(num[i],end=' ')