[Java]Study_0310:다음 입사문제

* 1차원의 점들이 주어졌을 때, 그 중 가장 거리가 짧은 것의 쌍을 출력하는 함수를 작성하시오.
* 단, 점들의 배열은 모두 정렬되어있다고 가정한다.
* Ex)S={1,3,4,8,13,17,20}이 주어졌다면, 결과값은(3,4)가 될 것이다.

수학적으로 접근을 해보자.

먼저,예제에 나와있는 리스트는 정렬이 되어있다.

모든 리스트가 정렬되지 않을테니, 첫번째로, 리스트를 정렬시켜주는 함수가 필요하다.

정렬된 리스트에서, 각각 S1,S2,S3,...Sn이라고한다면, (S1,S2), (S2,S3), (S3,S4),...,(S(n-1),Sn)이렇게 비교해서

가장 거리가 짧은 쌍을 찾아내면된다.

문제에서 배열이 모두 정렬되어있다고 가정했으니,각각의 거리가 짧은 쌍을 찾아내기만 하면 된다.

 

먼저 숫자들을 입력해서, 배열을 만들 수 있게 코딩해보자.

	Scanner sc = new Scanner(System.in); 
        int[] pointArray = new int[101]; 
        boolean setting = true; 
        int choose;

        while(setting) {
            System.out.println("************************************");
            System.out.println("*　1. 점 생성 　2. 점 목록 　3. 거리 계산　 *");
            System.out.println("************************************");
            choose = sc.nextInt();
            System.out.println("");

            if(choose == 1) {
                if(pointArray[1] == 0) {
                    System.out.println("NOTICE : 최대 100번째 수 까지 입력 가능합니다.");
                    System.out.println("NOTICE : 입력 취소를 원할 경우 '0'을 입력하세요.");
                    for(int pointNum = 1; pointNum <= 100; pointNum++) {
                        System.out.print(pointNum +"번째 수를 입력하세요 > ");
                        int inputNum = sc.nextInt();
                        if(inputNum == 0) {
                            break;
                        } else if(pointNum == 1 || pointArray[pointNum-1] < inputNum) {
                            pointArray[pointNum] = inputNum;
                        } else {
                            System.out.println("이전에 입력한 점의 수(" +pointArray[pointNum-1] +")보다 더 큰 수를 입력해야 합니다.");
                            pointNum--;
                        }
                    }
                    System.out.println("점 세팅을 완료합니다.");
                } else {
                System.out.println("이미 입력된 점(들)이 있기 때문에 프로그램 재가동이 필요합니다.");
                System.out.println("시스템을 종료합니다.");
                setting = false;
            }
        }

Scanner를 이용해서 숫자를 입력하게하고, 최대 100가지의 숫자를 입력할 수 있게 코딩해보았다.

이전에 입력한 숫자와 같거나 작게된다면, 다시 입력할 수 있게 해놓았다.

	else if(choose == 2) {
                for(int pointNum = 1; pointNum < 100; pointNum++) {
                    if(pointArray[pointNum] != 0) {
                        System.out.println(pointNum +"번째 점 : " +pointArray[pointNum]);
                    }
                }
            }

2.점 목록버튼은 생성한 숫자들을 모두 보여줄 수 있는 기능을 하였다. pointArray에있는 point가 0이 아니라면 모두 출력하게끔 코딩했다.

 	else if(choose == 3) {
                System.out.println("점 거리 계산을 시작합니다.");
                System.out.println(".");
                int[] pointDistance = new int[100];
                for(int count = 1; count < 100; count++) {
                    if(pointArray[count + 1] != 0) {
                        pointDistance[count] = (pointArray[count + 1] - pointArray[count]);
                    }
                    }

                System.out.println("모든 점들 사이의 가장 가까운 거리들을 추출합니다.");
                System.out.println(".");
                int minDistance = pointDistance[1];
                for(int count = 2; count < 100; count++) {
                    if(minDistance > pointDistance[count]) {
                        if(pointDistance[count] != 0) {
                            minDistance = pointDistance[count];
                        }
                    }
                }

                System.out.println("가장 가까운 거리들의 쌍을 모두 출력합니다.");
                System.out.println(".");

                System.out.println("가장 가까운 거리:"+minDistance);

                for(int count = 1; count < 100; count++) {
                    if(minDistance == pointDistance[count]) {
                        System.out.println("(" +pointArray[count] +", " +pointArray[count+1] +")"); 
                    }
                }

3번 거리계산 버튼은, 점 목록간의 거리를 비교해서 가장 가까운 거리들을 모두 출력하게끔 코딩했다.

 

https://github.com/THKim94/JavaStudy/blob/main/src/study/Study_0310_DaumTest.java

GitHub - THKim94/JavaStudy

깃허브에 코딩 공유해놓았으니 참고해주세요.