[ BOJ 3649 ] 로봇 프로젝트 ( JAVA )

문제

상근이와 선영이는 학교 숙제로 로봇을 만들고 있다. 로봇을 만들던 중에 구멍을 막을 두 레고 조각이 필요하다는 것을 깨달았다.

구멍의 너비는 x 센티미터이고, 구멍에 넣을 두 조각의 길이의 합은 구멍의 너비와 정확하게 일치해야 한다. 정확하게 일치하지 않으면, 프로젝트 시연을 할 때 로봇은 부수어질 것이고 상근이와 선영이는 F를 받게 된다. 구멍은 항상 두 조각으로 막아야 한다.

지난밤, 상근이와 선영이는 물리 실험실에 들어가서 레고 조각의 크기를 모두 정확하게 재고 돌아왔다. 구멍을 완벽하게 막을 수 있는 두 조각을 구하는 프로그램을 작성하시오.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다.

각 테스트 케이스의 첫째 줄에는 구멍의 너비 x (1 ≤ x ≤ 20, x는 정수)가 주어진다. x의 단위는 센티미터이다.

다음 줄에는 물리 실험실에 있는 레고 조각의 수 n이 주어진다. (0 ≤ n ≤ 1000000)

다음 n개의 줄에는 레고 조각의 길이 ℓ이 주어진다. ℓ은 양의 정수이며, 단위는 나노미터이다. 블록의 길이는 10 센티미터 (100000000 나노미터)를 넘지 않는다.

출력

각 테스트 케이스마다 한 줄에 하나씩, 구멍을 완벽하게 막을 수 있는 두 조각이 없다면 'danger'를 출력한다. 막을 수 있는 경우에는 'yes ℓ1 ℓ2'를 출력한다. (ℓ1 ≤ ℓ2)

정답이 여러 개인 경우에는 |ℓ1 - ℓ2|가 가장 큰 것을 출력한다.

 

시간 제한 : 5초

메모리 제한 : 256MB 

---

테스트 케이스의 개수가 정해지지 않은 문제이므로, 입력이 더이상 주어지지 않을 때까지 수행해야 합니다.
( 이 부분에서 몇가지 예외가 발생하였습니다.)

 

NumberFormatException

while(true){
	// 첫번째 입력 값을 x로 바로 바꾸고 있습니다.
	// 입력 값이 없는 경우에 숫자로 바꿀 수 없으므로 NumberFormatException 발생
	int x = Integer.parseInt(bufferedReader.readLine());		
	...
}

• 첫번째 입력값을 x 초기화 부분에 바로 사용하여서 입력값의 유효성을 검증하지 못했습니다.
• 다음과 같이 첫번째 입력에 대한 부분을 분리하여 해결하였습니다. 

while(true){
    String input = bufferedReader.readLine();	// 첫번째 입력값을 X 초기화 부분과 분리
    if(input.isEmpty()) break;	// 첫번째 입력값이 유효한지 체크
    int x = Integer.parseInt(input) * NANO_PARAM;
    ...
}

• input 변수를 생성하여 첫번째 입력 부분과 x 초기화 부분을 분리하였습니다.
• String 클래스의 isEmpty() 메서드를 이용하여 유효성을 검사하였습니다.
• 실행 결과 NullPointerException가 발생하였습니다.

NullPointerException

• 참조변수의 초기화가 제대로 되지 않은 경우에 주로 발생하는 예외입니다.
• 하지만 제 코드를 살펴보니 참조변수에 대한 초기화가 되지 않은 부분은 없었습니다.
• 입력값을 처리하는 부분에서 문제가 있을 거라고 생각하였고, isEmpty()가 null에 대한 검증을 하지 않는다는 것을 발견했습니다.

    /**
     * Returns {@code true} if, and only if, {@link #length()} is {@code 0}.
     *
     * @return {@code true} if {@link #length()} is {@code 0}, otherwise
     * {@code false}
     *
     * @since 1.6
     */
    public boolean isEmpty() {
        return value.length == 0;
    }

• String 클래스의 isEmpty() 메서드입니다.
• 이 부분에서 입력 값이 없는( null ) 경우 예외가 발생하였던 것입니다.
• 유효성을 확인하는 부분에 null 임을 검증하는 코드를 추가하여 이를 해결하였습니다.

while(true){
	String input = bufferedReader.readLine();
	if(input == null || input.isEmpty()) break;	// input 이 null인지 확인하는 코드 추가

	int x = Integer.parseInt(input) * NANO_PARAM;
}

알고리즘

1. 우선 x와 레고 블럭의 단위가 다르기 때문에 x값에 10,000,000을 곱했습니다.
   ( 주어진 x의 범위가 최대 20이므로 int 형을 사용하였습니다. )
2. 레고 블럭들을 int형 배열에 저장하고, 오름차순으로 정렬하였습니다.  ( int legos[] // 레고 블럭 배열 ) 
3. 레고 블럭 배열의 양쪽 끝 인덱스 ( 0 과 n-1 )는 각각 길이가 가장 짧은 블럭과 가장 긴 블럭을 나타냅니다.
   인덱스를 각각 left, right로 표현하였습니다. ( left = 0, right = n-1 )
   

4. 투포인터 알고리즘 

이후, left와 right에 해당하는 블럭의 길이를 더하였습니다. ( legoLengthSum )

int legoLengthSum = legos[left] + legos[right];

legoLengthSum이 구멍의 길이와 같다면 ?

• 문제의 조건에 맞는 블럭들을 찾은 것입니다.
• legoLengthSum ==  x * 10,000,000 인 경우, 절댓값 차이가 가장 큰 순으로 조사하고 있으므로 문제의 조건에 맞음

legoLengthSum이 구멍보다 작다면 ?

• left를 하나 키워줍니다. ( left++ )
• legos[ left ] <= legos[ left + 1 ] 이므로 legos[ left + 1 ] + legos[ right ] 의 길이는 이전보다 길거나 같아집니다.

legoLengthSum이 구멍보다 크다면 ? 

• right를 하나 줄입니다. ( right-- )
• legos[ right ] >= right[ right -1 ] 이므로 legos[ left ] + legos[ right - 1 ]의 길이는 이전보다 짧거나 같아집니다.

int legos[] = new int[n];	

/* 레고 블록 입력 받는 부분*/

Arrays.sort(legos);		// 블럭을 오름차순 정렬

int left = 0;			// 가장 작은 블럭
int right = n - 1;		// 가장 큰 블럭 
boolean isDanger = true;	// 만족하는 두 블럭을 찾지 못하는 경우 위험한 상황

while (left < right) {

	int legoLengthSum = legos[left] + legos[right];	// 양쪽 블럭의 합을 계산

if (legoLengthSum == x) {	// 두 블럭의 합이 x인 경우 
	isDanger = false;	// 블럭을 찾았으므로 위험하지 않음
	break;			// 더이상 조사할 필요가 없으므로 반복을 빠져나갑니다.
	}

	if (legoLengthSum < x) {	// 두 블럭의 합이 x보다 작은 경우
	left++;				// left를 증가시킴 ( 짧은 쪽을 늘린다. ) 
	}

	if (legoLengthSum > x) {	// 두 블럭의 합이 x보다 큰 경우
	right--;			// right를 감소시킴 ( 큰 쪽을 줄인다. )
	}
}

소스 코드

import java.io.*;
import java.util.Arrays;

/**
 * 로봇 프로젝트
 */
public class BOJ3649 {

    static final int NANO_PARAM = 10000000;
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bufferedWriter = new BufferedWriter(new OutputStreamWriter(System.out));

        while (true) {
            String input = bufferedReader.readLine();
            if(input == null || input.isEmpty()) break;

            int x = Integer.parseInt(input) * NANO_PARAM;
            int n = Integer.parseInt(bufferedReader.readLine());

            int[] legos = new int[n];

            for (int i = 0; i < n; i++) {
                legos[i] = Integer.parseInt(bufferedReader.readLine());
            }

		Arrays.sort(legos);		// 블럭을 오름차순 정렬

		int left = 0;			// 가장 작은 블럭
		int right = n - 1;		// 가장 큰 블럭 
		boolean isDanger = true;	// 만족하는 두 블럭을 찾지 못하는 경우 위험한 상황

		while (left < right) {

			int legoLengthSum = legos[left] + legos[right];	// 양쪽 블럭의 합을 계산

			if (legoLengthSum == x) {	// 두 블럭의 합이 x인 경우 
				isDanger = false;	// 블럭을 찾았으므로 위험하지 않음
				break;			// 더이상 조사할 필요가 없으므로 반복을 빠져나갑니다.
			}

			if (legoLengthSum < x) {	// 두 블럭의 합이 x보다 작은 경우
				left++;			// left를 증가시킴 ( 짧은 쪽을 늘린다. ) 
			}

			if (legoLengthSum > x) {	// 두 블럭의 합이 x보다 큰 경우
				right--;		// right를 감소시킴 ( 큰 쪽을 줄인다. )
			}
		}

            bufferedWriter.append( isDanger ? "danger\n" : "yes " + (legos[left] + " " + legos[right] +"\n"));
        }

        bufferedWriter.flush();
    }
}

---

https://www.acmicpc.net/problem/3649

3649번: 로봇 프로젝트