1. 씨름선수
문제
풀이
import java.util.*;
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;
}
}
class Main {
public int 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++;
}
}
return cnt;
}
public static void main(String[] args) {
Main T = new Main();
Scanner kb = new Scanner(System.in);
int n = kb.nextInt();
ArrayList<Body> arr = new ArrayList<>();
for(int i = 0; i < n; i++) {
int h = kb.nextInt();
int w = kb.nextInt();
arr.add(new Body(h, w));
}
System.out.println(T.solution(arr, n));
}
}2. 회의실 배정
문제
개념
회의가 끝나는 시간을 기준으로 오름차순 -> 회의가 빨리 끝나는 것 부터 회의를 할 수 있게 해야 함.
끝나는 시간들이 모두 같으면 시작하는 시간으로도 오름차순 정렬해서 비교해야 한다.
풀이
import java.util.*;
class Time implements Comparable<Time> {
public int s, e;
Time(int s, int e) {
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;
}
}
}
class Main {
public int 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;
}
}
return cnt;
}
public static void main(String[] args) {
Main T = new Main();
Scanner kb = new Scanner(System.in);
int n = kb.nextInt();
ArrayList<Time> arr = new ArrayList<>();
for(int i = 0; i < n; i++) {
int x = kb.nextInt();
int y = kb.nextInt();
arr.add(new Time(x, y));
}
System.out.println(T.solution(arr, n));
}
}3. 결혼식
문제
개념
가는 시간과 오는 시간이 겹치는 경우 가는 시간을 먼저 처리해줘야 오답이 생기지 않는다.
시간 순으로 정렬을 하고 두번째로 e, s 알파벳순으로 정렬을 해야 한다.
풀이
import java.util.*;
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 ob) {
if(this.time == ob.time) {
return this.state - ob.state;
} else {
return this.time - ob.time;
}
}
}
class Main {
public int 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);
}
return answer;
}
public static void main(String[] args) {
Main T = new Main();
Scanner kb = new Scanner(System.in);
int n = kb.nextInt();
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'));
}
System.out.println(T.solution(arr));
}
}4. 최대수입스케쥴(PriorityQueue)
문제
풀이
import java.util.*;
class Lecture implements Comparable<Lecture> {
public int money;
public int time;
Lecture(int money, int time) {
this.money = money;
this.time = time;
}
@Override
public int compareTo(Lecture ob) {
return ob.time - this.time;
}
}
class Main {
static int n, max = Integer.MIN_VALUE;
public int solution(ArrayList<Lecture> arr) {
int answer = 0;
PriorityQueue<Integer> pQ = new PriorityQueue<>(Collections.reverseOrder());
Collections.sort(arr);
int j = 0;
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();
}
}
return answer;
}
public static void main(String[] args) {
Main T = new Main();
Scanner kb = new Scanner(System.in);
n = kb.nextInt();
ArrayList<Lecture> arr = new ArrayList<>();
for(int i = 0; i < n; i++) {
int m = kb.nextInt();
int d = kb.nextInt();
arr.add(new Lecture(m, d));
if(d > max) {
max = d;
}
}
System.out.println(T.solution(arr));
}
}5. 다익스트라 알고리즘
문제
풀이
import java.util.*;
class Edge implements Comparable<Edge> {
public int vex;
public int cost;
Edge(int vex, int cost) {
this.vex = vex;
this.cost = cost;
}
@Override
public int compareTo(Edge ob) {
return this.cost - ob.cost;
}
}
class Main {
static int n, m;
static ArrayList<ArrayList<Edge>> graph;
static int[] dis;
public void solution(int v) {
PriorityQueue<Edge> pQ = new PriorityQueue<>();
pQ.offer(new Edge(v, 0));
dis[v] = 0;
while(!pQ.isEmpty()) {
Edge tmp = pQ.poll();
int now = tmp.vex;
int nowCost = tmp.cost;
if(nowCost > dis[now]) {
continue;
}
for(Edge ob : graph.get(now)) {
if(dis[ob.vex] > nowCost + ob.cost) {
dis[ob.vex] = nowCost+ob.cost;
pQ.offer(new Edge(ob.vex, nowCost + ob.cost));
}
}
}
}
public static void main(String[] args) {
Main T = new Main();
Scanner kb = new Scanner(System.in);
n = kb.nextInt();
m = kb.nextInt();
graph = new ArrayList<ArrayList<Edge>>();
for(int i = 0; i <= n; i++) {
graph.add(new ArrayList<Edge>());
}
dis = new int[n + 1];
Arrays.fill(dis, Integer.MAX_VALUE);
for(int i = 0; i < m; i++) {
int a = kb.nextInt();
int b = kb.nextInt();
int c = kb.nextInt();
graph.get(a).add(new Edge(b, c));
}
T.solution(1);
for(int i = 2; i <= n; i++) {
if(dis[i] != Integer.MAX_VALUE) {
System.out.println(i + " : " + dis[i]);
}
else {
System.out.println(i + " : impossible");
}
}
}
}6. 친구인가(Union & Find)
풀이
import java.util.*;
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;
}
}
public static void main(String[] args) {
Scanner kb = new Scanner(System.in);
int n = kb.nextInt();
int m = kb.nextInt();
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 a = kb.nextInt();
int b = kb.nextInt();
int fa = Find(a);
int fb = Find(b);
if(fa == fb) {
System.out.println("YES");
}
else {
System.out.println("NO");
}
}
}7. 원더랜드(크루스칼 : Union & Find)
풀이
import java.util.*;
class Edge implements Comparable<Edge> {
public int v1;
public int v2;
public int cost;
Edge(int v1, int v2, int cost) {
this.v1 = v1;
this.v2 = v2;
this.cost = cost;
}
@Override
public int compareTo(Edge ob) {
return this.cost - ob.cost;
}
}
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;
}
}
public static void main(String[] args) {
Scanner kb = new Scanner(System.in);
int n = kb.nextInt();
int m = kb.nextInt();
unf = new int[n + 1];
ArrayList<Edge> arr = new ArrayList<>();
for(int i = 1; i <= n; i++) {
unf[i] = i;
}
for(int i = 0; i < m; i++) {
int a = kb.nextInt();
int b = kb.nextInt();
int c = kb.nextInt();
arr.add(new Edge(a, b, c));
}
int answer = 0;
Collections.sort(arr);
for(Edge ob : arr) {
int fv1 = Find(ob.v1);
int fv2 = Find(ob.v2);
if(fv1 != fv2) {
answer += ob.cost;
Union(ob.v1, ob.v2);
}
}
System.out.println(answer);
}
}8. 원더랜드(프림 : PriorityQueue)
풀이
import java.util.*;
class Edge implements Comparable<Edge> {
public int vex;
public int cost;
Edge(int vex, int cost) {
this.vex = vex;
this.cost = cost;
}
@Override
public int compareTo(Edge ob) {
return this.cost - ob.cost;
}
}
class Main {
public static void main(String[] args) {
Scanner kb = new Scanner(System.in);
int n = kb.nextInt();
int m = kb.nextInt();
ArrayList<ArrayList<Edge>> graph = new ArrayList<ArrayList<Edge>>();
for(int i = 0; i <= n; i++) {
graph.add(new ArrayList<Edge>());
}
int[] ch = new int[n + 1];
for(int i = 0; i < m; i++) {
int a = kb.nextInt();
int b = kb.nextInt();
int c = kb.nextInt();
graph.get(a).add(new Edge(b, c));
graph.get(b).add(new Edge(a, c));
}
int answer = 0;
PriorityQueue<Edge> pQ = new PriorityQueue<>();
pQ.offer(new Edge(1, 0));
while(!pQ.isEmpty()) {
Edge tmp = pQ.poll();
int ev = tmp.vex;
if(ch[ev] == 0) {
ch[ev] = 1;
answer += tmp.cost;
for(Edge ob : graph.get(ev)) {
if(ch[ob.vex] == 0) {
pQ.offer(new Edge(ob.vex, ob.cost));
}
}
}
}
System.out.println(answer);
}
}
가보자고