Algorithm/그리디(Greedy)

[백준, Java] 5186번 : 파티를 열어라!!!

🔗 문제 링크 https://www.acmicpc.net/problem/5186 😮 문제 해결 방법 최대한 많은 차를 이용해 최대한 많은 친구들을 집에 보내줘야 최소한으로 집에서 재울 수 있다. 최대한 많은 친구들을 보내야하기 때문에 “차의 좌석수가 많은 순으로 내림차순" 정렬을 했다. 또한, 운전할 수 있는 친구들을 먼저 배치해주기 위해서 술을 마시지 않은 (S)기준으로 정렬했다. 자동차의 경우 우선순위 큐를 이용해 하나씩 빼면서 태울 수 있는 운전자를 배치한다. 배치된 운전자는 차에 탔다는 체크(ride)를 해주고 운전자 인원수를 1 증가시킨다. 운전자가 배치되는 경우 “태울 수 있는 좌석 - 1 (운전자)”를 지역별 태울 수 있는 인원수 배열(avilable)에 저장한다. 최대한 많은 운전자를 배치..

[백준, Java] 10775번 : 공항

🔗 문제 링크 https://www.acmicpc.net/problem/10775 😮 문제 해결 방법 문제에서 비행기가 순서대로 도착할 예정이고 각 비행기의 값은 1부터 해당 값까지의 게이트에 도킹할 수 있는 것을 의미한다. 자신의 순서에 비행기가 도킹할 수 없을 때까지 개수를 세준다. 비행기가 도킹할 수 있는 게이트를 찾기 위해서 Union-Find를 이용한다. 게이트 배열을 자신의 게이트로 초기화를 하고, 해당 값의 비행기가 도킹되면 다음에 도킹될 동일한 값의 비행기는 현재 게이트보다 하나 작은 게이트로 도킹되어야 한다. 예를 들어, 게이트가 4개이고 아무 비행기도 게이트에 도킹되지 않았다면 게이트 배열은 1,2,3,4값을 가질 것이다. 3번 비행기가 3번 게이트에 도킹되면 이 후에 들어오는 3번 비..

[백준, Java] 1052번 : 물병

🔗 문제 링크 https://www.acmicpc.net/problem/1052 😮 문제 해결 방법 문제에서 같은 양이 들어있는 물병끼리 하나로 합칠 수 있고 처음에는 모든 물병에는 물이 1L가 들어있다고 제시되어 있다. 처음부터 두 개의 물병을 한 개의 병으로 합쳐가면, 2L → 4L → 8L 이런식으로 증가할 수 밖에 없다. 이는 물병이 2의 제곱 값이 되어야 병이 하나로 합쳐지는 것을 알 수 있다. N개의 물병을 K개의 물병으로 합치는 경우 최소 개수의 물병을 사기 위해선 남은 물병(N) 보다 작으면서 가장 큰 2의 제곱 값을 매번 구해 빼주는 작업을 K-1번 해주고, 그래도 물병이 남아있다면 마지막(K번째)에는 남은 물병으로 한 병을 만들어야 하므로 남은 물병보다 크면서 가장 작은 2의 제곱값을 ..

[프로그래머스, Java] 단속카메라

🔗 문제 링크 https://programmers.co.kr/learn/courses/30/lessons/42884 🤔 문제 고속도로를 이동하는 모든 차량이 고속도로를 이용하면서 단속용 카메라를 한 번은 만나도록 카메라를 설치하려고 합니다. 고속도로를 이동하는 차량의 경로 routes가 매개변수로 주어질 때, 모든 차량이 한 번은 단속용 카메라를 만나도록 하려면 최소 몇 대의 카메라를 설치해야 하는지를 return 하도록 solution 함수를 완성하세요. 📌 제한사항 차량의 대수는 1대 이상 10,000대 이하입니다. routes에는 차량의 이동 경로가 포함되어 있으며 routes[i][0]에는 i번째 차량이 고속도로에 진입한 지점, routes[i][1]에는 i번째 차량이 고속도로에서 나간 지점이 적..

[ 백준, Java] 1339번 : 단어 수학

🔗 문제 링크 https://www.acmicpc.net/problem/1339 🤔 문제 민식이는 수학학원에서 단어 수학 문제를 푸는 숙제를 받았다. 단어 수학 문제는 N개의 단어로 이루어져 있으며, 각 단어는 알파벳 대문자로만 이루어져 있다. 이때, 각 알파벳 대문자를 0부터 9까지의 숫자 중 하나로 바꿔서 N개의 수를 합하는 문제이다. 같은 알파벳은 같은 숫자로 바꿔야 하며, 두 개 이상의 알파벳이 같은 숫자로 바뀌어지면 안 된다. 예를 들어, GCF + ACDEB를 계산한다고 할 때, A = 9, B = 4, C = 8, D = 6, E = 5, F = 3, G = 7로 결정한다면, 두 수의 합은 99437이 되어서 최대가 될 것이다. N개의 단어가 주어졌을 때, 그 수의 합을 최대로 만드는 프로그..