본문 바로가기
반응형

Sort6

백준 18870 좌표 압축 https://www.acmicpc.net/problem/18870 18870번: 좌표 압축 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다. X1, X2, ..., XN에 좌 www.acmicpc.net EXPLANATION 문제를 다시 설명하자면 입력값들을 입력될 수 있는 값의 범위를 정의역의 크기를 가지는 것이 아니라 실제로 입력된 값만의 범위를 정의역의 크기로 가지도록 만드는 것, 물론 오름차순으로 순서를 유지하면서. ex) [2 4 -10 4 -9] 좌표 압축 이 문제를 푸는 방법은 나중에 세그먼트트리 문제를 해결할 때 입력되는 좌표값의 정.. 2022. 6. 4.
백준 1181 단어 정렬 https://www.acmicpc.net/problem/1181 1181번: 단어 정렬 첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다. www.acmicpc.net EXPLANATION find 함수를 이용해 중복되는 단어를 찾아 제외시키면서 배열을 초기화하고 sort함수를 이용해 재배열하면된다. CODE #include #include #include using namespace std; bool compareWith(string a, string b) { if(a.length() == b.length()) //단어 길이가 같으면 사전 순으로 r.. 2022. 6. 4.
백준 11650 좌표 정렬하기, 11651 좌표 정렬하기 2 https://www.acmicpc.net/problem/11650 11650번: 좌표 정렬하기 첫째 줄에 점의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 i번점의 위치 xi와 yi가 주어진다. (-100,000 ≤ xi, yi ≤ 100,000) 좌표는 항상 정수이고, 위치가 같은 두 점은 없다. www.acmicpc.net https://www.acmicpc.net/problem/11651 11651번: 좌표 정렬하기 2 첫째 줄에 점의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 i번점의 위치 xi와 yi가 주어진다. (-100,000 ≤ xi, yi ≤ 100,000) 좌표는 항상 정수이고, 위치가 같은 두 점은 없다. ww.. 2022. 6. 4.
백준 1427 소트인사이드 https://www.acmicpc.net/problem/1427 1427번: 소트인사이드 첫째 줄에 정렬하려고 하는 수 N이 주어진다. N은 1,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net EXPLANATION sort(str.begin(), str.end(), greater()); 를 이용하여 내림차순하는 문제. CODE #include #include using namespace std; int main(void) { string str; cin>>str; sort(str.begin(), str.end(), greater()); cout 2022. 6. 4.
백준 2108 통계학 https://www.acmicpc.net/problem/2108 2108번: 통계학 첫째 줄에 수의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 단, N은 홀수이다. 그 다음 N개의 줄에는 정수들이 주어진다. 입력되는 정수의 절댓값은 4,000을 넘지 않는다. www.acmicpc.net EXPLANATION 문제에서 첫째 줄에는 산술평균을 출력한다. 소수점 이하 첫째 자리에서 반올림한 값을 출력한다. 둘째 줄에는 중앙값을 출력한다. 셋째 줄에는 최빈값을 출력한다. 여러 개 있을 때에는 최빈값 중 두 번째로 작은 값을 출력한다. 넷째 줄에는 범위를 출력한다. 라고 하였다. 산술 평균은 전체 누적합을 입력값의 개수로 나누면 되고 중앙값과 최댓값과 최솟값의 차이인 범위는 입력값을 받은 배열을 오름차.. 2022. 6. 4.
백준 2750 수 정렬하기 1, 2751 수 정렬하기 2 https://www.acmicpc.net/problem/2750 2750번: 수 정렬하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net https://www.acmicpc.net/problem/2751 2751번: 수 정렬하기 2 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net EXPLANATION 시간 복잡도 O(n^2)도 되냐 아니면 O(nlogn)만 되냐의.. 2022. 6. 3.
반응형

티스토리툴바