반응형
1. 씨름 선수
설명
현수는 씨름 감독입니다. 현수는 씨름 선수를 선발공고를 냈고, N명의 지원자가 지원을 했습니다.
현수는 각 지원자의 키와 몸무게 정보를 알고 있습니다.
현수는 씨름 선수 선발 원칙을 다음과 같이 정했습니다.
“A라는 지원자를 다른 모든 지원자와 일대일 비교해서 키와 몸무게 모두 A지원자 보다 높은(크고, 무겁다) 지원자가
존재하면 A지원자는 탈락하고, 그렇지 않으면 선발된다.”
N명의 지원자가 주어지면 위의 선발원칙으로 최대 몇 명의 선수를 선발할 수 있는지 알아내는 프로그램을 작성하세요.
입력
첫째 줄에 지원자의 수 N(5<=N<=30,000)이 주어집니다.
두 번째 줄부터 N명의 흰돌 능력치와 검은돌 능력치 정보가 차례로 주어집니다.
각 선수의 흰돌능력치가 모두 다르고, 검은돌 능력치도 모두 다릅니다. 능력치 값은 1,000,000이하의 자연수입니다.
출력
첫째 줄에 바둑 선수로 뽑히는 최대 인원을 출력하세요.
예시 입력 1
5
172 67
183 65
180 70
170 72
181 60
예시 출력 1
3
import java.util.*;
class Person{
int height,weight;
Person(int height, int weight){
this.weight=weight;
this.height=height;
}
}
public class Main {
static Queue<Person> q;
public static void main(String[] args){
int answer=0;
Scanner in=new Scanner(System.in);
int n = in.nextInt();
int[] arr = new int[n];
q = new LinkedList<>();
for(int i=0;i<n;i++){
int height=in.nextInt();
int weight=in.nextInt();
q.offer(new Person(height, weight));
}
for(Person p : q) {
boolean flag=true;
for(Person x : q){
if(p.weight<x.weight && p.height<x.height){
flag=false;
break;
}
}
if(flag) answer++;
}
System.out.println(answer);
}
}
package greedy.ch09_2;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
class Person {
int h;
int w;
public Person(int h, int w) {
this.h = h;
this.w = w;
}
}
public class Greedy01 {
public static void main(String[] args) {
Scanner kb = new Scanner(System.in);
Queue<Person> pq = new LinkedList<Person>();
int n = kb.nextInt();
for (int i = 0; i < n; i++) {
int h = kb.nextInt();
int w = kb.nextInt();
Person p = new Person(h, w);
pq.offer(p);
}
System.out.println(solution(pq));
}
public static int solution(Queue<Person> pq) {
int answer = 0;
for (int i = 0; i < pq.size(); i++) {
Person p = pq.poll();
int n = 0;
for (Person t : pq) {
if (p.h < t.h && p.w < t.w) {
n = 0;
break;
} else {
n++;
}
}
if (n == pq.size())
answer++;
pq.offer(p);
}
return answer;
}
}
+) 세련된 풀이
import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;
class Body implements Comparable<Body>{
//interface
public int h,w;
Body(int h, int w) {
this.h=h;
this.w=w;
}
@Override
//비어있는 interface를 정의하는 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);
//arr 기준 정렬
int max=Integer.MIN_VALUE;
for(Body ob : arr) {
//내림차순 정렬된 body for문
if(ob.w>max) {
//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));
}
}
#이중 for문 돌지 않도록
-> 정렬 후, max 값을 이용해 비교
#list 두번 돌려서 풀이
import java.util.*;
class Person{
public int h, w;
Person(int h, int w){
this.h=h;
this.w=w;
}
}
public class Main {
public static void main(String[] args){
Scanner in=new Scanner(System.in);
ArrayList<Person> list = new ArrayList<>();
int n = in.nextInt();
for(int i=0;i<n;i++){
list.add(new Person(in.nextInt(), in.nextInt()));
}
System.out.println(solution(list));
}
static int solution(ArrayList<Person> list){
int answer=0;
e: for(Person p : list){
for(Person s : list){
if(p.h<s.h && p.w<s.w){
continue e;
}
}
answer++;
}
return answer;
}
}
+) 02.22
import java.util.Scanner;
import java.util.*;
class Person implements Comparable<Person>{
public int height;
public int weight;
Person(int height, int weight){
this.height=height;
this.weight=weight;
}
@Override
public int compareTo(Person o){
if(o.height==this.height){
return this.weight-o.weight;
}else return this.height-o.height;
}
}
public class Main {
public static void main(String[] args){
Scanner in=new Scanner(System.in);
int n = in.nextInt();
Person[] arr= new Person[n];
for(int i=0;i<n;i++){
int height= in.nextInt();
int weight= in.nextInt();
Person person = new Person(height, weight);
arr[i]=person;
}
Main main = new Main();
System.out.println(main.solution(arr));
}
public int solution(Person[] arr){
int answer=0;
Arrays.sort(arr);
for(int i=0;i<arr.length;i++){
int cnt=0;
for(int j=0;j<arr.length;j++){
if(i==j) continue;
if(arr[i].height<arr[j].height&&arr[i].weight<arr[j].weight) {
break;
}
cnt++;
}
if(cnt==arr.length-1) answer++;
}
return answer;
}
}반응형
'Java > Java 알고리즘 인프런' 카테고리의 다른 글
| [Ch.09 - Greedy] 03. 결혼식 ### (0) | 2022.07.16 |
|---|---|
| [Ch.09 - Greedy] 02. 회의실 배정 (0) | 2022.07.15 |
| [리뷰] 해결 못한 알고리즘 다시 풀기 -2 (0) | 2022.07.08 |
| 해당 날짜의 날씨보다 따뜻한 날씨가 오는데 걸리는 기간 (0) | 2022.07.06 |
| String에 char 추가하기 (0) | 2022.06.30 |
