문제 11508번: 2+1마트에서 물건을 3개 사면 가장 싼 1개는 무료로 준다. 구매하고자 하는 N개의 물건 가격이 주어질 때, 최대한 혜택을 받았을 때 지불해야 하는 금액의 합을 구하는 문제.www.acmicpc.net 풀이 문제에서 주어진 조건은 "유제품을 세 개 사면, 가장 싼 하나를 무료로 받을 수 있다" 이다. 따라서, 최대한 비싼 제품에 대해 할인을 적용하려면 비싼 제품들끼리 묶는 것이 가장 유리하다. 즉, 유제품의 가격을 내림차순으로 정렬한 뒤, 세 개씩 묶었을 때 세 번째 제품을 무료로 처리하면 된다. 코드 fun main() { var ans = 0 val cost = IntArray(readln().toInt()) { readln().toInt() }.sortedDesc..

문제 1758번: 알바생 강호강호는 알바를 하며 팁을 받지만, 팁 기록을 조작할 수 없고, 팁이 많은 사람에게 먼저 팁을 받는다. 주어지는 팁 액수들로 받을 수 있는 최대 팁의 합을 구하는 문제.www.acmicpc.net 풀이 음수인 팁은 받을 수 없기 때문에, 가장 많은 팁을 주려는 사람부터 순서대로 받는 것이 전체 팁의 합을 최대로 만드는 방법이다. 따라서 손님들이 제시한 팁 금액을 내림차순으로 정렬한 뒤, 순서에 따라 실제 받을 수 있는 팁을 계산한다. 이때 계산 결과가 0보다 작으면 팁을 받을 수 없으므로 제외하고, 모든 가능한 팁의 합을 더해 최종 결과를 구한다. 코드 fun main() { val arr = IntArray(readln().toInt()) { readln().toIn..

문제 9237번: 이장님 초대농부 상근이는 마을 이장님을 초대해 자신이 심은 나무를 자랑하려고 한다. 모든 나무가 완전히 자란 이후에 이장님을 초대하려고 한다. 즉, 마지막 나무가 다 자란 다음날 이장님을 초대할 것이다.www.acmicpc.net 풀이 그리디 유형의 문제다. 자라는데 가장 오래 걸리는 나무부터 먼저 심는 것이 최적의 선택이다. 따라서 입력받은 나무의 성장 시간을 내림차순(역순) 으로 정렬한 뒤, 각 나무를 심는 순서에 따라 필요한 날짜를 계산해준다. 모든 나무 중에서 가장 늦게 자라는 나무의 날짜를 계산하여 값을 출력한다. 코드 fun main() { val num = readln().toInt() val arr = readln().split(' ').map { it.t..

문제 2910번: 빈도 정렬첫째 줄에 메시지의 길이 N과 C가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ C ≤ 1,000,000,000) 둘째 줄에 메시지 수열이 주어진다.www.acmicpc.net 풀이 LinkedHashMap 자료구조를 활용해 해결할 수 있다. LinkedHashMap은 일반 HashMap과 달리 입력된 순서를 그대로 기억하는 맵으로 정렬 시 등장 순서를 따로 비교할 필요가 없다. 입력받은 값을 빈도에 따라 정렬한 뒤, flatMap을 사용해 최종 출력 리스트를 만들어준다. flatMap은 리스트의 각 요소를 여러 개의 요소로 펼쳐서 새로운 리스트를 만들어 준다. 여기서는 빈도수만큼 반복해 하나의 리스트로 합친다. 코드 fun main() { val (n, c) = r..

문제 11000번: 강의실 배정 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si < Ti ≤ 109) www.acmicpc.net 풀이 LectureTime 데이터 클래스를 정의하여 Comparable 인터페이스를 구현한다. 시작시간을 기준으로 오름차순 정렬하도록 고 만약 시작시간이 같다면 종료시간을 기준으로 정렬한다. 입력받은 시간을 LectureTime 배열에 저장하고 이 배열을 정렬해준다. 우선순위 큐를 선언하고 첫번째 수업의 종료 시간을 큐에 넣는다. 배열을 순회하면서 만약 현재 강의의 시작 시간이 우선순위 큐의 최상단의 강의의 종료 시간보다 작거나 같으면 해당 강의는 해당 강의실에서 진행 가능하므로 우선순위 큐에서 poll(..