백준

[백준, 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] 1414번 : 불우이웃돕기

🔗 문제 링크 https://www.acmicpc.net/problem/1414 😮 문제 해결 방법 문제의 입력이 인접행렬 방식으로 들어오고, 알파벳과 0으로 들어온다. 따라서, 입력이 이어진 랜선의 길이이기 때문에 숫자로 변환하고 그래프를 만들어준다. 모든 컴퓨터에 대해 랜선 그래프를 만들어 줬으므로 모든 컴퓨터가 이어질 수 있게 가장 짧은 랜선을 구하면 된다. 따라서, 최소신장트리를 구하는 프림 혹은 크루스칼 알고리즘을 이용해 구현하면 문제를 해결할 수 있다. 알파벳을 숫자로 변환환다. 컴퓨터에 대해 랜선 정보를 연결한다(정점과 간선을 이용해 그래프 생성) 프림 알고리즘을 수행한다. 어떤 컴퓨터에서 시작하더라도 모두 이어져야하므로 상관이 없다. 최소 길이 랜선을 구하고 전체 랜선 길이에서 빼준다. 🚩..

[백준, Java] 19621번 : 회의실 배정 2

🔗 문제 링크 https://www.acmicpc.net/problem/19621 😮 문제 해결 방법 문제의 제한 조건에서 K 번째 회의는 K-1 , K+1번째 회의와 겹친다고 했기 때문에 K 기준으로 회의를 참석하는 경우 K-1, K+1회의는 참석할 수 없다. 반대로 회의에 참가하지 않는 경우 K-1, K+1 회의는 참가할 수 있다. 따라서, 첫 회의를 기준으로 참가하는 경우와 불참하는 경우로 DFS를 이용한 완전탐색으로 문제를 해결했다. 회의의 최대 개수가25개까지 주어지므로 DFS를 이용한 완전탐색이 가능하다. 첫 번째 회의 기준으로 참가와 불참 경우로 탐색을 진행한다. 첫 번째 회의에 참가하는 경우 2번째 회의는 참가하지 못하기 때문에 3번째 회의에 참가하도록 depth + 2를 해주고 현재 회의..

[백준, Java] 9934번 : 완전 이진 트리

🔗 문제 링크 https://www.acmicpc.net/problem/9934 😮 문제 해결 방법 상근이가 도시를 방문한 조건을 살펴보면 가장 왼쪽에 있는 도시까지 방문한 후 그 부모를 방문 한 뒤 다시 오른쪽을 탐색한다. 즉, inorder 중위 순회 방식과 동일하다. 상근이가 방문한 도시의 트리 모양을 표현해줘야 하는 것이 목적이므로, 노드 번호가 1, 2, 3 순차적으로 증가하는 완전 이진 트리를 새로 만들어줬다. 새로 만든 트리를 이용해 중위 순회를 한 후 방문한 도시들을 스택에 저장한다. 입력으로 받은 도시와 스택에 저장한 도시가 동일한 순서이기 때문에 입력으로 받은 도시와 스택에 저장한 도시를 하나의 클래스로 매핑해준 뒤 새로 만든 트리의 모양대로 만들어준다. 새로 만든 트리는 노드 번호가 ..