문제 설명
N명의 지원자가 있고, 각자 키, 몸무게를 가지고 있다.
한 지원자가 다른 지원자에 비해 키와 몸무게 모두 작으면 탈락한다.
이 조건을 만족하며 선발할 수 있는 최대 인원 수를 구하라.
입력 & 출력
입력
5
172 67
183 65
180 70
170 72
181 60
출력
3해결 전략
- 키 내림차순으로 정렬
- 몸무게는 순서대로 비교하며 지금까지 본 몸무게 최대값보다 크면 선발
- 키와 몸무게 모두 큰 경우만 제외되므로, 키 정렬 + 몸무게만 비교하면 O(N)에 해결 가능
코드 구현
import java.util.*;
class Body implements Comparable<Body> {
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 Problem1 {
public int solution(ArrayList<Body> arr) {
Collections.sort(arr);
int cnt = 0, max = Integer.MIN_VALUE;
for (Body b : arr) {
if (b.w > max) {
max = b.w;
cnt++;
}
}
return cnt;
}
public static void main(String[] args) {
Problem1 T = new Problem1();
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));
sc.close();
}
}시간 복잡도
- 정렬: O(N log N)
- 순회 비교: O(N)
- 총합: O(N log N)
출처: 인프런 자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비
https://www.inflearn.com/course/자바-알고리즘-문제풀이-코테대비/dashboard
자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비 강의 | 김태원 - 인프런
김태원 | , 자바(Java) 알고리즘 문제풀이 채점사이트를 통해 기초부터 준비해보세요! 💪 [사진] 이 강의는 [사진] 자바(Java)로 코딩테스트 준비를 하고 계신 분께 추천드려요! 문제는 기초~ 중급
www.inflearn.com
'코딩테스트 > 자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비' 카테고리의 다른 글
| 섹션 9 Greedy - 3. 결혼식 (1) | 2025.06.10 |
|---|---|
| 섹션 9 Greedy - 2. 회의실 배정 (0) | 2025.06.10 |
| 섹션 8 DFS, BFS - 14. 피자 배달 거리(삼성 SW역량평가 기출문제 : DFS활용) (2) | 2025.06.09 |
| 섹션 8 DFS, BFS - 13. 섬나라 아일랜드(BFS) (1) | 2025.06.09 |
| 섹션 8 DFS, BFS - 13. 섬나라 아일랜드 (0) | 2025.06.09 |