HackerRank New Year Chaos
리스트 원소가 오름차순 정렬되도록 해야 하는데 조건이 있다.
1. 각 원소는 뒤에 원소랑 자리 교환을 할 수 있다.
2. 각 원소는 자리 교환을 2번만 할 수 있다
자리 교환 최소 횟수를 출력한다. 만약 원소가 자리 교환을 2번 초과한다면 Too chaotic을 출력한다
일일이 정렬하지 않아도 Too chaotic인 경우를 index와 원소 값을 통해 알 수 있다. 이때 바로 Too chaotic을 출력하고 종료한다
버블 정렬을 활용해야 한다
정렬 flag를 하나 두고 False로 유지된다면 정렬된 상태이므로 횟수를 출력하고 종료한다
시간 초과가 자꾸 났는데 정렬이 필요 없는 상황에선 종료해주면 된다
Big O가 n^2이기 때문에 10만^10만이면 상당히 느리다.
#!/bin/python3
def minimumBribes(q):
length = len(q)
swapped = False
for i, v in enumerate(q):
if v - 1 > i + 2:
print("Too chaotic")
return
count = 0
for i in range(length - 1):
for j in range(length - 1):
if q[j] > q[j + 1]:
count += 1
q[j], q[j + 1] = q[j + 1], q[j]
swapped = True
if swapped:
swapped = False
else:
print(count)
return
if __name__ == '__main__':
t = int(input().strip())
for t_itr in range(t):
n = int(input().strip())
q = list(map(int, input().rstrip().split()))
minimumBribes(q)
Author And Source
이 문제에 관하여(HackerRank New Year Chaos), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@samnaka/HackerRank-New-Year-Chaos저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)