알고리즘 (6월 7일)

1. 문제 (코딩도장, 다음 입사문제)

https://codingdojang.com/scode/408?answer_mode=hide 

코딩도장

---

2. 생각

1차원의 점들이 주어졌을 때, 그 중 가장 거리가 짧은 것의 쌍을 출력하는 함수를 작성하시오. 

 

예를들어 S={1, 3, 4, 8, 13, 17, 20} 이 주어졌다면, 결과값은 (3, 4)가 될 것이다.

 

1. 임의의 x 값들을 입력받아 ArrayList에 저장한다.
2. sort 메소드를 이용하여 ArrayList 의 원소들을 오름차순으로 정렬한다.
3. for문을 이용하여 첫 번째 원소부터 차례차례 다음 원소끼리의 거리를 계산한다.
4. 계산된 거리가 최소 값일 경우 계산된 거리 값을 최소 값으로 지정하고, 해당 x 값을 기억한다.
5. 결과를 출력한다.

---

3. 풀이 및 코드 분석

import java.util.Scanner;
import java.util.ArrayList;
import java.util.Comparator;

public class Main {
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		ArrayList<Integer> points = new ArrayList<>();
		String n;
		
		// x 좌표 값들 입력 받기
		while(true) {
			System.out.println("x 좌표 값을 입력하시오: (입력을 그만하고 싶으면 !을 입력하시오)");
			n = scan.next();
			
			if(n.equals("!")) {
				break;
			}else {
				points.add(Integer.parseInt(n));
			}
		}
		
		// 오름차순 정리
		points.sort(Comparator.naturalOrder());
		
		// 최소 거리 구하기
		int minimumDist = points.get(1)-points.get(0), point=0, dist;
		
		for(int i=1; i<points.size()-1; i++) {
			dist = points.get(i+1) - points.get(i);
			
			if(dist<minimumDist) {
				point = i;
				minimumDist = dist;
			}
		}
		
		// 결과 출력
		System.out.printf("(%d, %d) 사이 거리가 %d이며, 제일 짧은 거리를 갖고 있습니다.\n", points.get(point), points.get(point+1), minimumDist);
	}
}

---

4. 메모

• 문제를 풀기 전에 ArrayList를 오름차순으로 정렬함으로서 최소 거리를 계산하는 과정에서 모든 원소를 비교할 필요 없이 바로 오른쪽에 위치한 원소와 비교함으로서 불필요한 계산을 줄일 수 있었다.