백준 15760 python

랜덤 픽업 문제.

처음 보고 initial code를 짜서 제출해봤으나 당연히 시간초과로 실패..

initial code(틀린 부분 수정)

n = int(input())
lst = [int(input()) for _ in range(n)]

leng = len(lst)-1
last = sorted(lst)
result = 0

while lst != last:
    result += 1
    for i in range(leng):
        if lst[i+1] < lst[i]:
            tmp = lst[i+1]
            lst[i+1] = lst[i]
            lst[i] = tmp

print(result)

last code

n = int(input())
lst = [int(input()) for _ in range(n)]

leng = len(lst)
last = sorted(lst)
result = 0

num_idx_dict = dict()
num_idx_dict_last = dict()

for i in range(leng):
    num_idx_dict[lst[i]] = i
    num_idx_dict_last[last[i]] = i

for i in num_idx_dict:
    result = max(result,num_idx_dict[i] - num_idx_dict_last[i])    

print(result+1)

code를 짠 방법은 inital code의 작동방식을 보며 구현했다. 최종적으로 정렬된 배열과 초기 배열을 비교했을 때 moo가 한번 실행될 때마다 작은 숫자가 오른쪽에서 왼쪽으로 1번씩 이동한다.

배열 / moo 시행 횟수
1 5 3 8 2, 1   
1 3 5 2 8, 2
1 3 2 5 8, 3
1 2 3 5 8, 4 

output : 4

다만 다른 사람들의 결과를 비교해보았을 때 좀 더 효율적인 코드가 존재하기는 하나 그저 구현방식의 차이일 가능성이 높기 때문에 확인 후 개선하는 작업을 하지는 않았다. 아마 개선을 한다면 num_idx_dict_last을 만들지 않고, iterator을 같이 저장하는 식으로 코드 개선을 할 수 있을 것 같긴 한데 설명을 하기에는 현재 코드가 편해보인다.

여담

1. 개선해보실 분은 개선해보는 것도 효율성 연습에 도움이 될 것 같기도..?
   (아마 맨처음 푸신 분도 비슷하게 코드를 짰다가 개선한 것 같다.)

2. 나중에 알고봤더니 문제 자체의 input을 잘못봤더라..ㅋㅋㅋㅋ.. last code와 똑같은 원리로 제출한 코드에는 그냥 모든 수가 lst에 들어가는 줄 알았는데 다시 읽어보니 첫 번째 수가 lst의 크기였다.. 제출했을 때 로직이 맞는데 이상하다?? 하면서 한 5번 추가로 제출했었는데 그래도 계속 틀려서 문제를 차근히 다시 읽어보니 input 부분에서 틀렸다는 사실을 발견했다... 웃긴거는 그상태에서도 40%까지 통과를 한다는 사실이 legeno...ㅋㅋㅋㅋㅋㅋㅋㅋ