[ 기록용 ]
- 씨름 선수 문제
키/몸무게가 본인보다 큰 사람이 있으면 탈락함
N명의 지원자가 주어지면 위의 선발원칙으로 최대 몇 명의 선수를 선발할 수 있는지 알아내는 프로그램
1) 먼저 키 순서대로 정렬함
2) 몸무게를 비교하는데, 처음 값을 max로 넣어줌
3) 다음부터는 몸무게만 비교하면됨 / 이전보다 어차피 키는 작으니 몸무게가 max값보다 작으면 탈락
4) 몸무게가 max보다 크면 통과해서 cnt++ 해주고, max값 업데이트
* 키, 몸무게를 넣어주기 위해 Body 클래스 생성 -> sort할때, '키' 기준으로 sort할 수 있도록 compareTo 메소드 오버라이딩함
class Body implements Comparable<Body>{
public int h, w;
Body(int h, int w){
this.h =h;
this.w = w;
}
@Override
public int compareTo(Body o){
return o.h - this.h;
}
}
public class main
{
public void solution(ArrayList<Body> arr, int n){
int cnt = 0;
Collections.sort(arr);
int max = Integer.MIN_VALUE;
for(Body ob : arr){
if(ob.w > max){
max = ob.w;
cnt++;
}
}
}
// tip: arguments are passed via the field below this editor
public static void main(String[] args)
{
ArrayList<Body> arr = new ArrayList<>();
}
}
- 회의실 배정
회의의 시작시간과 끝나는 시간이 주어질때, 최대 사용할 수 있는 회의실 수
* 회의의 시작시간과 끝나는 시간의 조건은 (시작시간 <= 끝나는 시간)
3 3 / 1 3/ 2 3 -> 끝나는 시간만으로 정렬할때 답이 1개일 수 있으므로, 끝나는시간 정렬후, 같으면 시작시간 순으로 정렬 필요
- 끝나는 시간이 빠른걸로 정렬했을 때, 최적의 해를 구한다고 가정함 > greedy
lass Time implements Comparable<Time>{
public int s, e;
Time(int s, int we{
this.s =s;
this.e = e;
}
@Override
public int compareTo(Time o){
if(this.e == o.e)
return this.s - o.s; // 오름차순
else
return this.e-o.e;
}
}
public class main
{
public void solution(ArrayList<Time> arr, int n){
int cnt = 0;
Collections.sort(arr);
int et = 0;
for(Time ob : arr){
if(ob.s >= et){
cnt++;
et = ob.e;
}
}
}
}- 결혼식
오는시간/가는시간이 주어질 때, 피로연장에 동시에 존재하는 최대인원 구하기
1) 시간과 state(오는시간인지 가는시간인지) 를 따로 저장함
2) 누군가가 오는시간과 가는시간이 같을 때, 동시에 존재하는게 아니므로(가는시간에는 그 사람이 없다고 판단) start와 end가 같으면 end를 먼저 비교해줌
3) count를 증가시켜가며 max 값 비교
class Time implements Comparable<Time>{
public int time;
public char state;
Time(int time, char state}{
this.time =time;
this.state = state;
}
@Override
public int compareTo(Time o){
if(this.time == o.time)
return this.state - o.state; // 오름차순
else
return this.time-o.time;
}
}
public class main
{
public void solution(ArrayList<Time> arr){
int answer = Integer.MIN_VALUE;
Collections.sort(arr);
int cnt = 0;
for(Time ob : arr){
if(ob.state == 's'){
cnt ++;
}
else{
cnt --;
}
answer = Math.max(answer, cnt);
}
}
// tip: arguments are passed via the field below this editor
public static void main(String[] args)
{
ArrayList<Time> arr = new ArrayList<>();
for(int i=0; i<n; i++){
int st = kb.nextInt();
int et = kb.nextInt();
arr.add(new Time(st, 's'));
arr.add(new Time(et, 'e'));
}
}
}
- 최대수입스케쥴
> priorityQueue 활용
각 기업은 D일 안에 와서 강연을 해 주면 M만큼의 강연료를 주기로 했다.
각 기업이 요청한 D와 M를 바탕으로 가장 많을 돈을 벌 수 있도록 강연 스케쥴을 짜야 한다
1) day를 기준으로 내림차순 정렬을 함
2) 요청한 day의 max값을 구해서 max값부터 비교 시작
* max = 3이면 3일째 강연이 가능한 강의부터 큐에 넣어줌
3) priorityQueue는 가장 큰값을 리턴할 수 있도록 설정해줌 -> reverseOrder() 사용
4) 같은 날에 되는 강연의 금액을 priorityqueue에 넣어줌
5) 다른 날이 되면(현재 날짜보다 작은 날짜) break걸어줌
6) 그날 가장 큰 값을 빼서 answer에 더해줌(priorityQueue 활용해서 poll)
class Lecture implements Comparable<Time>{
public int money,time;
Lecture(int money, int time}{
this.money = money;
this.time =time;
}
@Override
public int compareTo(Lecture o){
return ob.time - o.time; // 오름차순
}
}
public class main
{
public void solution(ArrayList<Lecture> arr){
int answer = 0;
PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder()); // default는 제일 작은값을 우선순위로함, reverseorder하면 제일 큰값을 우선순위로
Collections.sort(arr);
int j = 0;
//max는 day max값
for(int i = max; i>=1; i--){
for(;j<n; j++){
if(arr.get(j).time < i)
break;
pq.offer(arr.get(j).money);
}
if(!pq.isEmpty())
answer+= pq.poll();
}
}
- 친구인가(Union & Find)
서로소 집합
첫 번째 줄에 반 학생수인 자연수 N(1<=N<=1,000)과 숫자쌍의 개수인 M(1<=M<=3,000)이 주어지고,
다음 M개의 줄에 걸쳐 숫자쌍이 주어진다.
마지막 줄에는 두 학생이 친구인지 확인하는 숫자쌍이 주어진다.
> 같은 집합에 있는지 확인
public class main
{
static int[] unf;
public static int Find(int v){
if(v==unf[v])
return v;
else
return unf[v] = Find(unf[v]);
}
public static void Union(int a, int b){
int fa = Find(a);
int fb = Find(b);
if(fa!=fb)
unf[fa] = fb;
}
// tip: arguments are passed via the field below this editor
public static void main(String[] args)
{
unf = new int[n+1];
for(int i=1; i<=n; i++)
unf[i]= i;
for(int i=1; i<=m; i++){
int a = kb.nextInt();
int b = kb.nextInt();
Union(a,b);
}
int fa = Find(a);
int fb = Find(b);
if(fa == fb)
answer = "YES";
else
answer = "NO";
}
}'코테 준비-문제풀기' 카테고리의 다른 글
| Dynamic Programming (0) | 2022.04.14 |
|---|---|
| 그리디 - JAVA 프로그래머스 풀어보기[테스트용] / 체육복 (0) | 2022.04.14 |
| 해쉬- 학급회장/ 애너그램/ 매출액의 종류 * (0) | 2022.04.05 |
| 프로그래머스 - 전화번호 목록 (자바/java) (0) | 2022.02.23 |
| 프로그래머스 - 완주하지 못한 선수_해시맵(HashMap) 사용해 풀기 (0) | 2022.02.06 |