백준 2565 - 전깃줄 JAVA

문제

 

입출력, 테스트케이스

해당 문제를 처음 접했을 때는 점화식을 구하기 보다 구현으로 해결하려고 했었다. 그래서 아래와 같이 Comparator를 두 번이나 오버라이딩 해서 썼다. 하지만,,, 결과는 9퍼에서 틀림!

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args) throws NumberFormatException, IOException {
		// 전깃줄 최소로 없애서 교차하지 않게 만들기
		// 1 <= 전깃줄 갯수 <=100, 1 <= 위치의 번호 <= 500 -> boolean 배열선언 최대 boolean[500][500]
		// boolean으로 해도 됨.
		// 같은 위치에 두 개 이상 전깃줄 X
		// 특정 전깃줄이 엮여 있는 갯수를 각각 넣어둬야 할까?
		// 정렬을 해보자

		int arr[][];
		int N;
		StringTokenizer stz;
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		arr = new int[N][3]; // 전깃줄 배열 저장
		int answer = 0;
		for (int i = 0; i < N; i++) {
			stz = new StringTokenizer(br.readLine());
			int from = Integer.parseInt(stz.nextToken());
			int to = Integer.parseInt(stz.nextToken());
			arr[i] = new int[] { from, to, 0 };
		}
		Arrays.sort(arr, new Comparator<int[]>() {

			@Override
			public int compare(int[] o1, int[] o2) {
				return o1[0] - o2[0]; // o1, o2의 인덱스 들이가 같을 일이 없음
			}
		});

		for (int i = 0; i < N; i++) {
			for (int j = i + 1; j < N; j++) {
				if (arr[i][1] > arr[j][1]) { // 겹치는 횟수 저장
					arr[i][2]++;
					arr[j][2]++;
				}
			}
		}
		Arrays.sort(arr, new Comparator<int[]>() {

			@Override
			public int compare(int[] o1, int[] o2) {
				return o2[2] - o1[2]; // 겹치는 순으로 내림차순 배열 정렬
			}
		});


		for (int i = 0; i < N; i++) {
			if (arr[i][2] != 0) {
				answer++;


				for (int j = 0; j < N; j++) {
					if (((arr[i][1] > arr[j][1] && arr[i][0] < arr[j][0])
							|| (arr[i][1] < arr[j][1] && arr[i][0] > arr[j][0]))&& arr[i][2]!=0 && arr[j][2]!=0) { // 겹치는 횟수 저장
						arr[i][2]--;
						arr[j][2]--;
					}
				}
			}
		}

		System.out.println(answer);

	}
}

다시 한 번 마음을 다 잡고 문제를 다시 읽고 나니 정렬 후에 LIS를 구하는 문제로 보였다.

<문제 접근/풀이 과정>
1. 1 <= 전깃줄 갯수 <=100, 1 <= 위치의 번호 <= 500 -> int 배열 선언 넉넉함.
2. 같은 위치에 두 개 이상의 전깃줄 연결 X
3. 정렬을 해보자.
4. 정렬을 하고 나니 가장 긴 부분 수열 구하기 문제로 변모하였다.
5. 음~ 웰 논이네!? 

코드는 아래의 두 소스코드와 같은 코드이므로 참고하면 좋을 것 같다.(2, 3번째 링크)

또한 배열 정렬 시 lambda식 사용한 버전과 사용하지 않은 버전으로 구현 해봤다.

자바는 정렬할 때 comparable의 compareTo나 Comparator의 Compare 메서드를 오버라이딩 해야하므로 내용을 모르거나 헷갈린다면( 해당 게시글을 참고하면 좋겠다! - 1번째 링크)

2022.02.20 - [프로그래밍공부(ProgrammingStudy)/자바(JAVA)] - (JAVA/자바)compareTo와 Comparator 그리고 정렬

(JAVA/자바)compareTo와 Comparator 그리고 정렬

2022.03.31 - [알고리즘공부(AlgorithmStudy)/문제풀이(ProblemSolving)] - 백준 11053 - 가장 긴 증가하는 부분 수열 JAV

백준 11053 - 가장 긴 증가하는 부분 수열 JAV

2022.03.31 - [알고리즘공부(AlgorithmStudy)/문제풀이(ProblemSolving)] - 백준 11054 가장 긴 바이토닉 부분 수열 - JAVA

백준 11054 - 가장 긴 바이토닉 부분 수열 - JAVA

<람다식 적용하지 않은 코드>

package boj;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.StringTokenizer;

public class Boj_2565 {
	public static void main(String[] args) throws NumberFormatException, IOException {
		// 전깃줄 최소로 없애서 교차하지 않게 만들기
		// 1 <= 전깃줄 갯수 <=100, 1 <= 위치의 번호 <= 500 -> boolean 배열선언 최대 boolean[500][500]
		// boolean으로 해도 됨.
		// 같은 위치에 두 개 이상 전깃줄 X
		// 특정 전깃줄이 엮여 있는 갯수를 각각 넣어둬야 할까?
		// 정렬을 해보자

		int arr[][];
		int dp[] = new int[501]; // 겹치는 줄 갯수 넣는 dp;
		int N;
		StringTokenizer stz;
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		arr = new int[N+1][3]; // 전깃줄 배열 저장
		int answer = 0;
		for (int i = 1; i <= N; i++) {
			stz = new StringTokenizer(br.readLine());
			int from = Integer.parseInt(stz.nextToken());
			int to = Integer.parseInt(stz.nextToken());
			arr[i] = new int[] { from, to, 1 };
		}
		Arrays.sort(arr, new Comparator<int[]>() {

			@Override
			public int compare(int[] o1, int[] o2) {
				return o1[0] - o2[0]; // o1, o2의 인덱스 들이가 같을 일이 없음
			}
		});

	

		for (int i = 1; i <= N; i++) {
			for (int j = i; j >= 0; j--) {
				if(arr[i][1] > arr[j][1]) { 
					arr[i][2] = Math.max(arr[i][2], arr[j][2]+1);
				}
			}
			answer = Math.max(arr[i][2], answer);
		}


		System.out.println(N - answer);

	}
}

<람다식 적용한 코드>

package boj;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.StringTokenizer;

public class Boj_2565 {
	public static void main(String[] args) throws NumberFormatException, IOException {
		// 전깃줄 최소로 없애서 교차하지 않게 만들기
		// 1 <= 전깃줄 갯수 <=100, 1 <= 위치의 번호 <= 500 -> boolean 배열선언 최대 boolean[500][500]
		// boolean으로 해도 됨.
		// 같은 위치에 두 개 이상 전깃줄 X
		// 특정 전깃줄이 엮여 있는 갯수를 각각 넣어둬야 할까?
		// 정렬을 해보자

		int arr[][];
		int dp[] = new int[501]; // 겹치는 줄 갯수 넣는 dp;
		int N;
		StringTokenizer stz;
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		arr = new int[N+1][3]; // 전깃줄 배열 저장
		int answer = 0;
		for (int i = 1; i <= N; i++) {
			stz = new StringTokenizer(br.readLine());
			int from = Integer.parseInt(stz.nextToken());
			int to = Integer.parseInt(stz.nextToken());
			arr[i] = new int[] { from, to, 1 };
		}
		Arrays.sort(arr, (a, b) -> a[0] - b[0]);
	

		for (int i = 1; i <= N; i++) {
			for (int j = i; j >= 0; j--) {
				if(arr[i][1] > arr[j][1]) { 
					arr[i][2] = Math.max(arr[i][2], arr[j][2]+1);
				}
			}
			answer = Math.max(arr[i][2], answer);
		}


		System.out.println(N - answer);

	}
}

 

람다식을 사용했을 때 메모리 사용량(18,240kb), 시간(228ms)이 모두 많이 소요되었다. 해당 원인에 대해서는 공부를 해봐야겠다.