728x90 버블 썸네일형 리스트형 [백준알고리즘] 1517번: 버블 소트 -Python [백준알고리즘] 1517번: 버블 소트 -Python https://www.acmicpc.net/problem/1517 1517번: 버블 소트 첫째 줄에 N(1≤N≤500,000)이 주어진다. 다음 줄에는 N개의 정수로 A[1], A[2], …, A[N]이 주어진다. 각각의 A[i]는 0≤|A[i]|≤1,000,000,000의 범위에 들어있다. www.acmicpc.net 당연히 일반적인 방법으로 문제를 해결할 경우 시간 초과가 발생할 것이란 것을 알고 있었다. 그런데 그거 외에는 방법을 모르겠어서.. 각각의 값마다 앞의 인덱스에서 자신보다 큰 값의 개수를 새는 것까지는 생각했는데 결국 O(N^2)을 벗어날 수 없었다. # 여기서 앞에 존재하는 큰 값의 개수를 세는, 역순으로 존재하는 수의 개수를 찾는 .. 더보기 이전 1 다음