문제
설명
현수는 씨름 감독입니다. 현수는 씨름 선수를 선발공고를 냈고, 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힌트
출력설명
(183, 65), (180, 70), (170, 72) 가 선발됩니다. (181, 60)은 (183, 65)보다 키와 몸무게 모두 낮기 때문에 탈락이고, (172, 67)은 (180, 70) 때문에 탈락입니다.
내 코드
import java.util.*;
public class Main9_1 {
static int[] height, weight;
static int n;
public int GD() {
int answer=0;
for(int i=0; i<n; i++) {
int h = height[i];
int w = weight[i];
boolean flag=true;
for(int j=0; j<n; j++) {
if(height[j] > h && weight[j] > w) flag=false;
}
if(flag) answer++;
}
return answer;
}
public static void main(String[] args) {
Main9_1 T = new Main9_1();
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
height = new int[n];
weight = new int[n];
for(int i=0; i<n; i++) {
height[i] = sc.nextInt();
weight[i] = sc.nextInt();
}
System.out.println(T.GD());
}
}
n이 큰 숫자(최대가 3만)가 들어온다면 무조건 time limit 나는 O(n^2)의 코드다 ^^ (테스트 케이스에서는 통과했음)
나는 Greedy Algorithm 처음이니까 그럴 수 있음.
첫 문제인 만큼 가볍게 넘어가면서 배우고, 흡수한다는 생각하며 넘어갔다.
선생님 풀이
import java.util.*;
class Body implements Comparable<Body>{
public int h, w;
public Body(int h, int w) {
this.h = h;
this.w = w;
}
@Override
public int compareTo(Body o) {
return o.h - this.h;
}
}
public class Main9_1 {
public int Solution(ArrayList<Body> arr, int n) {
int answer=0;
Collections.sort(arr);
int max = Integer.MIN_VALUE;
for(Body ob : arr) {
if(ob.w > max) {
max = ob.w;
answer++;
}
}
return answer;
}
public static void main(String[] args) {
Main9_1 T = new Main9_1();
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
ArrayList<Body> arr = new ArrayList<>();
for(int i=0; i<n; i++) {
int h = sc.nextInt();
int w = sc.nextInt();
arr.add(new Body(h, w));
}
System.out.println(T.Solution(arr, n));
}
}
Body라는 클래스를 만들어 특정 멤버 변수의 값을 기준으로 정렬한다.
섹션 6에서 한 번 다뤘던 방법이라 어렵지 않았다. (그렇지만 외우지 못했으니까 이번에 외우자..)
https://rookie-programmer.tistory.com/85
[Inflearn] 자바 알고리즘 문제풀이 #06-07 7. 좌표 정렬
문제 설명 N개의 평면상의 좌표(x, y)가 주어지면 모든 좌표를 오름차순으로 정렬하는 프로그램을 작성하세요. 정렬기준은 먼저 x값의 의해서 정렬하고, x값이 같을 경우 y값에 의해 정렬합니다.
rookie-programmer.tistory.com
알고리즘 공부 처음이었지만 여러 가지 방법을 알게 되고, 생각해 보고, 적용해 볼 수 있게 해주셔서 정말 감사하다. 넘나 명강의...✨
결과
'Algorithm > Inflearn' 카테고리의 다른 글
| [Inflearn] 자바 알고리즘 문제풀이 #09-03 3. 결혼식(Greedy Algorithm) (0) | 2023.05.19 |
|---|---|
| [Inflearn] 자바 알고리즘 문제풀이 #09-02 2. 회의실 배정(Greedy Algorithm) (0) | 2023.05.12 |
| [Inflearn] 자바 알고리즘 문제풀이 #08-15 15. 피자 배달 거리(삼성 SW역량평가 기출문제 : DFS활용) (0) | 2023.05.01 |
| [Inflearn] 자바 알고리즘 문제풀이 #08-14 14. 섬나라 아일랜드(BFS) (0) | 2023.04.28 |
| [Inflearn] 자바 알고리즘 문제풀이 #08-13 13. 섬나라 아일랜드(DFS) (0) | 2023.04.28 |
