https://www.acmicpc.net/problem/2565
2565번: 전깃줄
첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는
www.acmicpc.net
<풀이 날짜>
2024-02-20(화)
<알고리즘 분류>
dp(LIS)
🌟 ArrayList 정렬 방식
여러가지 방식이 있으나 3번째 방식을 가장 선호한다.
lines.sort((s1, s2) -> Integer.compare(s1[0], s2[0]));
lines.sort(Comparator.comparingInt(s -> s[0]));
lines.sort((s1, s2) -> s1[0] - s2[0]);
🌟 LIS(longest increasing subsequence)
dp의 기본으로, 수를 저장하는 배열과 dp를 저장하는 배열 총 2가지 배열을 다루며 정답을 찾는다.
https://www.acmicpc.net/problem/11053
11053번: 가장 긴 증가하는 부분 수열
수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이
www.acmicpc.net
<정답 코드>
package boj;
/*
* 2024-02-20 (화)
* 14176 KB / 124 ms
*
* LIS를 통해 가장 긴 증가하는 수열을 찾은 뒤.
* 전체 전깃줄의 수에서 빼준다.
*
*/
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
public class BOJ_2565_전깃줄 {
static int N;
static ArrayList<int[]> lines;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
// N 개의 전깃줄
N = Integer.parseInt(br.readLine());
lines = new ArrayList<>();
for(int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
int from = Integer.parseInt(st.nextToken());
int to = Integer.parseInt(st.nextToken());
lines.add(new int[] {from, to});
}
// 람다식을 사용하여 lines 정렬
lines.sort((s1, s2) -> s1[0] - s2[0]);
// LIS를 dp 배열에 저장
int[] dp = new int[N];
for(int i = 0; i < lines.size(); i++) {
int max_n = 0;
for(int j = i; j >= 0; j--) {
if(lines.get(i)[1] >= lines.get(j)[1]) max_n = Math.max(max_n, dp[j]);
}
dp[i] = max_n + 1;
}
int answer = 0;
for(int i = 0; i < N; i++) {
answer = Math.max(answer, dp[i]);
}
answer = N - answer;
System.out.println(answer);
}
}
<Java vs C++>
동일 코드를 메모리, 실행 시간 비교한 결과

'Algorithm Study > java' 카테고리의 다른 글
| 프로그래머스 - [3차] 압축 (0) | 2024.04.02 |
|---|---|
| [프로그래머스] 전략망을 둘로 나누기 (풀이 : union-find & dfs) (0) | 2024.03.20 |
| Union-Find 알고리즘(서로소 집합, Disjoint-Set) (0) | 2024.03.20 |
| [프로그래머스] 메뉴 리뉴얼 - 2021 KAKAO BLIND RECRUITMENT (0) | 2024.03.19 |