정렬

문제 20920번: 영단어 암기는 괴로워 첫째 줄에는 영어 지문에 나오는 단어의 개수 $N$과 외울 단어의 길이 기준이 되는 $M$이 공백으로 구분되어 주어진다. ($1 \leq N \leq 100\,000$, $1 \leq M \leq 10$) 둘째 줄부터 $N+1$번째 줄까지 외울 단 www.acmicpc.net 풀이 문자열, 정렬, 해시를 사용한 집합과 맵 입력받은 문자열을 저장하고 정렬하는 방법이 필요한 문제 문자열이 입력된 횟수를 알아야 하므로 map을 사용해야 한다. 입력되는 수가 많지 않기 때문에 unordered_map을 사용한다. 문제에 맞게 정렬이 필요하므로 compare 함수를 생성해야 한다. compare 함수에는 문자열이 입력된 수, 문자열의 길이, 문자열의 사전 순서를 알아야 한..

문제 1826번: 연료 채우기 첫째 줄에 주유소의 개수 N(1 ≤ N ≤ 10,000)가 주어지고 두 번째 줄부터 N+1번째 줄 까지 주유소의 정보가 주어진다. 주유소의 정보는 두개의 정수 a,b로 이루어 져 있는데 a(1 ≤ a ≤ 1,000,000)는 성경 www.acmicpc.net 풀이 그리디, 정렬, 우선순위 큐 ✔ 정답 코드 1 연료가 높은 주유소가 top에 위치하도록 우선순위 큐에 넣는다. 우선순위 큐를 top에서 부터 방문하며, top이 현재 방문할 수 없는 주유소라면 벡터에 넣는다. 현재 방문할 수 있는 주유소가 top에 위치하였을 때, P에 더하고 벡터에 있는 값들을 다시 우선순위 큐에 넣는다. 이를 P가 L 이상일 때까지 반복 이렇게 하면 다음 방문할 주유소를 탐색할 때, 우선순위 큐..

문제 1449번: 수리공 항승 첫째 줄에 물이 새는 곳의 개수 N과 테이프의 길이 L이 주어진다. 둘째 줄에는 물이 새는 곳의 위치가 주어진다. N과 L은 1,000보다 작거나 같은 자연수이고, 물이 새는 곳의 위치는 1,000보다 작거나 www.acmicpc.net 풀이 그리디, 정렬 구멍이 정렬되어 들어오지 않으므로 정렬이 필수이다. // 정렬 필수 sort(hole.begin(), hole.end()); 구멍 start에서 테이프를 붙였을 때, 막을 수 있는 구멍의 거리는 start + L - 1까지이다. 이 거리보다 먼 구멍은 막을 수 없으므로, 새로운 테이프를 사용해야 한다. start + L - 1에서 다음 구멍 까지는 테이프를 붙이지 않아도 되므로, 다음 구멍이 start가 되어 다시 sta..

문제 1744번: 수 묶기 길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에 www.acmicpc.net 풀이 그리디, 정렬 수열의 음수와 양수를 나눠서 생각한다. 음수의 경우 가장 작은 수를 둘씩 묶어야 하고, 양수의 경우 가장 큰 수를 둘씩 묶어야 한다. 추가적으로, 0이 입력된 경우도 생각해야 한다. 음수의 경우, 가장 작은 수를 둘씩 묶어야 한다. 음수의 개수가 홀수인 경우 0이 입력되었다면, 음수 중 가장 큰 음수(절댓값이 가장 작은)는 0과 묶인다. 0이 입력되지 안않다면, 음수 중 가장 큰 음수(절댓값이 가장 작은)를 정답에 더한다. 양수의 경우..

문제 1946번: 신입 사원 첫째 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스의 첫째 줄에 지원자의 숫자 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개 줄에는 각각의 지원자의 서류심사 성 www.acmicpc.net 풀이 그리디, 정렬 먼저 서류심사 성적을 기준으로 정렬한다. 서류 성적 1등부터 7등을 0번부터 6등이라고 하자. 서류 면접 1 4 2 5 3 6 4 2 5 7 6 1 7 3 0번은 서류 성적이 1등 이므로, 면접 성적이 낮아도 서류 성적이 제일 높기 때문에 무조건 선발된다. 1번은 0번보다 서류 성적은 낮지만, 면접 성적이 높을 수 있다. 1번이 0번보다 면접 성적이 높다면 설발된다. 1번이 선발되었다고 가정하자. 마찬가지로, 2번은..

문제 2887번: 행성 터널 첫째 줄에 행성의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 다음 N개 줄에는 각 행성의 x, y, z좌표가 주어진다. 좌표는 -109보다 크거나 같고, 109보다 작거나 같은 정수이다. 한 위치에 행성이 두 개 이 www.acmicpc.net 풀이 최소 스패닝 트리, 크루스칼 알고리즘, 정렬 문제에서 행성 사이의 가중치 후보는 x좌표, y좌표, z좌표의 차의 절댓값이다. 행성의 수는 최대 100,000개 이므로 각 행성에서 다른 모든 행성에 대해 탐색한다면 시간초과와 메모리 초과가 발생한다. 그러므로, 행성 사이의 가중치 후보를 줄여서 계산해야 한다. 행성 사이의 거리는 x, y, z 좌표 차이 중 최솟값이므로, 각 좌표를 나눠서 처리한다. A, B, C 행성의 ..

문제 2473번: 세 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 3 이상 5,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 www.acmicpc.net 풀이 정렬, 두 포인터 문제이다. 먼저 용액을 두 포인터를 위해 정렬한다. 배열에서 세 용액 중 하나를 0에서부터 N - 1까지 선택한다. 선택한 용액 뒤의 배열에서 두 포인터를 실시하여, 선택한 용액과 start, end에서의 용액의 합의 절대값이 0과 가장 가까운 용액을 답으로 한다. 시간 복잡도는 O(N * N)으로 N은 5000이하이므로 시간초과는 발생하지 않는다. 코드 #include #include #include #incl..

문제 2230번: 수 고르기 N개의 정수로 이루어진 수열 A[1], A[2], …, A[N]이 있다. 이 수열에서 두 수를 골랐을 때(같은 수일 수도 있다), 그 차이가 M 이상이면서 제일 작은 경우를 구하는 프로그램을 작성하시오. 예를 들어 www.acmicpc.net 풀이 정렬, 두 포인터 문제이다. 입력받은 수열을 정렬한다. start와 end를 0에서부터 시작한다. start와 end에서의 수의 차이가 M이상이라면 답을 갱신한다. 차이를 더 줄이기 위해 start를 증가시킨다. 미만이라면 차이를 더 늘리기 위해 end를 증가시킨다. 코드 #include #include #include using namespace std; int nums[100000]; int main() { ios_base::s..

문제 풀이 정렬, 누적 합 문제이다. 각각의 컬러공의 크기 이하의 컬러공을 모두 탐색한다면 O(N * N)으로 시간초과이다. 컬러공을 한 번만 순회하여 문제를 해결해야 한다. 컬러공을 크기의 오름차순으로 정렬한다. 정렬한 컬러공을 처음부터 탐색하면서 현재 i까지의 크기의 합을 구한다. 그 합에서 지금까지 나온 공들 중에서 i번 공과 같은 색을 가진 공들을 뺀다. 그 합에서 지금까지 나온 공들 중에서 i번 공과 같은 무게를 가진 공들을 뺀다(크기 순으로 정렬되어 있으므로 i번 공보다 크기가 큰 공은 현재까지 합해지지 않았다). 이렇게 하면, i번 공과 색상과 크기가 모두 같은 공은 총 두 번 빠진다. 그러므로, 지금까지 나온 공들 중에서 i번 공과 같은 색과 같은 크기를 가진 공들은 한 번 더해줘야 올바른..

문제 풀이 정렬, 스위핑 문제이다. 현재 긋고 있는 선의 시작을 start, 끝을 end라고 하자. 선을 긋고 있을 때, 어떤 상황에서 다음 선을 한번에 그을 수 있을까? 만약 다음으로 그을 선의 시작이 end보다 작다면 그 선분은 한번에 그을 수 있다. 그리고 해당 선분의 끝이 end보다 크다면 해당 선분의 끝까지 한번에 그을 수 있다. 다음으로 그을 선의 시작이 end보다 크다면 그 선분은 한번에 그을 수 없으므로, 끊어서 그려야 한다. 선을 끊었다면, 다음으로 그을 선이 새로운 start와 end를 가진다. 코드 #include #include #include using namespace std; vector lines; int main() { ios_base::sync_with_stdio(0); ..