반응형
![](https://blog.kakaocdn.net/dn/0aqNZ/btsFJG2flar/Vs4QrLgKaGMeUQLp8FS3g1/img.png)
문제
![](https://blog.kakaocdn.net/dn/bV3AEN/btsFGUlNqqV/WZyw9OmeGr38bALye9Rvj0/img.png)
풀이
sort함수를 사용할 때,
- greater<> 내림차순
- less<> 오름차순
잊지말도록!
#include <algorithm> // sort함수를 사용하기 위한 헤더 파일
sort(v.begin(), v.end(), compare);
sort(v.begin(), v.end(), greater<int>()); // 내림차순
sort(v.begin(), v.end(), less<int>()); // 오름차순
아래는 정렬 시 시간복잡도에 대해서 자세하게 적어두었다.
이 문제에 대한 코드 설명도 있으니 꼭 읽어보시기를 추천드린다! 👍👍
아래의 글을 두 줄 요약하자면, sort함수는 퀵정렬을 이용해서 시간복잡도가 O(nlogn)으로 더 효율적이고 빠르다.
만약, 이중 for문을 이용해 정렬을 구현하면 시간복잡도는 O(n2) 으로 상대적으로 느리고, 시간초과가 발생한다.
[백준] 2751번 : 수 정렬하기 2 (C++) + 시간초과 & 런타임 에러(OutofBounds) 해결
문제 풀이 첫 번째 코드 - 실패 ➡ 시간복잡도: O(n2), int 배열 사용 // O(n^2), 시간초과 & 배열의 크기가 커 오류 발생 #include #include using namespace std; int main() { int N, num, temp; int arr[1000001]; cin >> N; for (in
jigoo-log.tistory.com
코드
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main() {
long long n, num;
vector<long long> v;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> num;
v.push_back(num);
}
sort(v.begin(), v.end(), greater<int>());
for (int i = 0; i < n; i++) {
cout << v.at(i) << "\n";
}
return 0;
}
결과
11931번: 수 정렬하기 4
첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.
www.acmicpc.net
반응형
'Programming > C++ - 백준' 카테고리의 다른 글
[백준] 10825번 : 국영수 (C++) (2) | 2024.03.14 |
---|---|
[백준] 11650번 : 좌표 정렬하기 | Sort 함수와 Compare & Array와 Vector 풀이 (C++) (0) | 2024.03.14 |
[백준] 11866번 : 요세푸스 문제 0 (C++) (0) | 2024.03.13 |
[백준] 10845번 : 큐 (C++) (0) | 2024.03.11 |
[백준] 10828번 : 스택 (C++) (0) | 2024.03.11 |
댓글