패스트캠퍼스 자바 알고리즘 문제

1. 나열된 수에서 최소값과 최대값 구하기

 

배열에 있는 수 중 맨 처음에 있는 값을 max와 min으로 가정하고, 배열의 마지막 숫자까지 비교하면서 더 큰 수나 더 작은 수가 나올 때까지 max와 min의 값으로 바꾸도록 한다.

그 때의 위치를 변수에 저장한다.

 

 

가장 큰 값은 101이고, 위치는 5번째입니다.
가장 작은 값은 2이고, 위치는 4번째입니다.

public static void main(String[] args) {
		
    int[] numbers = {10, 55, 23, 2, 79, 101, 16, 82, 30, 45};

    int min = numbers[0]; // 최소값 0번째부터 찾는다
    int max = numbers[0];

    int minPos = 0; // 순서
    int maxPos = 0;

    for(int i=1; i<numbers.length; i++)
    {
        if(min > numbers[i]) 
        {
            min = numbers[i];
            minPos = i+1; // 이렇게 하면 실제 순서에서 1이 더해지는데..
        }

        if(max < numbers[i]) // 모두 적용되므로 else if 쓰지 않는다
        {
            max = numbers[i];
            maxPos = i; // 왜 maxPos는 i+1이 아닌가??
        }

    }

    System.out.println("가장 큰 값은 " + max + "이고, 위치는 " + maxPos + "번째입니다.");
    System.out.println("가장 작은 값은 " + min + "이고, 위치는 " + minPos + "번째입니다.");

}

 

 

 

문제 풀이_랜덤

 

[25, 30, 14, 3, 35, 27, 29, 36, 2, 25]
가장 큰 값은 36이고, 위치는 7번째입니다.
가장 작은 값은 2이고, 위치는 8번째입니다.

public static void main(String[] args) {
		
    int[] numbers = new int[10];

    for(int i=0; i<numbers.length; i++)
    {
        numbers[i] = (int)(Math.random()*50)+1;
    }

    int min = numbers[0]; // 최소값 0번째부터 찾는다
    int max = numbers[0];

    int minPos = 0; // 순서
    int maxPos = 0;

    for(int i=1; i<numbers.length; i++)
    {
        if(min > numbers[i]) 
        {
            min = numbers[i];
            minPos = i; // min도 i로 해야 순서에 맞는 듯
        }

        if(max < numbers[i]) // 모두 적용되므로 else if 쓰지 않는다
        {
            max = numbers[i];
            maxPos = i;
        }

    }

    System.out.println(Arrays.toString(numbers));
    System.out.println("가장 큰 값은 " + max + "이고, 위치는 " + maxPos + "번째입니다.");
    System.out.println("가장 작은 값은 " + min + "이고, 위치는 " + minPos + "번째입니다.");

}

 

 

 

2. 정렬된 수에서 하나의 수 위치 찾기

 

수가 정렬 된 상태이므로 중간 값을 하나 선택한다. 찾으려는 값이 그보다 크면 범위를 오른쪽으로, 작으면 범위를 왼쪽으로 좁힌다.

한번 비교할 때마다 1/2씩 범위가 좁혀진다.

 

 

찾는 수는 10번째 있습니다.

public static void main(String[] args) {

    int[] numbers = {12, 25, 31, 48, 54, 66, 70, 83, 95, 108};

    int target = 108;

    int left = 0; // 맨 왼쪽
    int right = numbers.length-1; // 맨 오른쪽
    int mid = (left+right)/2;

    int tmp = numbers[mid]; // 비교 할 내용
    boolean find = false; // 수 찾았는지 여부

    while(left <= right) // left가 right보다 작거나 같은 동안
    {
        if(target == tmp)
        {
            find = true; // 수를 찾은 경우
            break; // 멈춘다
        }

        else if(target < tmp) // 찾으려는 수가 더 작은 경우
        {
            right = mid-1; // 맨 오른쪽에서 -1
        }

        else // 찾으려는 수가 더 큰 경우
        { 
            left = mid+1; // 맨 왼쪽에서 +1
        }

        mid = (left+right)/2;
        tmp = numbers[mid]; // tmp = numbers의 mid번째
    }

    if(find == true)
    {
        mid++;
        System.out.println("찾는 수는 " + mid + "번째 있습니다.");
    }

    else
        System.out.println("찾는 수가 없습니다.");

}

 

 

옵션 추가 

 

1. 배열 수 랜덤으로 출력 (중복 X)

2. 찾는 수 Scanner 입력

 

 

public static void main(String[] args) {
		
    // 난수 출력
    int[] numbers = new int[10];
    int su=0;
    boolean bCheck=false;

    // 중복 제거
    for(int i=0; i<numbers.length; i++)
    {
        bCheck=true;
        while(bCheck)
        {
            su = (int)(Math.random()*50)+1;
            bCheck = false;

            for(int j=0; j<i; j++)
            {
                if(numbers[j]==su)
                {
                    bCheck=true;
                    break;
                }
            }
        }
        numbers[i]=su;

    }

    Arrays.sort(numbers);
    System.out.println(Arrays.toString(numbers));

    // 찾는 수 입력
    Scanner sc = new Scanner(System.in);

    System.out.println("찾으려는 수: ");
    int target = sc.nextInt();

    // 입력한 수 찾기
    int left = 0; 
    int right = numbers.length-1; 
    int mid = (left + right)/2;

    int temp = numbers[mid]; // 비교할 수
    boolean find = false; // 수 찾았는지 여부

    while(left <= right) // 오름차순 조건(기본 조건??)
    {
        if(target == temp) // 수를 찾은 경우
        {
            find = true;
            break;
        }

        else if(target < temp) // 찾으려는 수가 더 작은 경우
        {
            right = mid-1;
        }

        else
        {
            left = mid+1;
        }

        mid = (left+right)/2;
        temp = numbers[mid]; // mid가 바뀌었으니 재조정`
    }

    if(find == true) // 수를 찾는 경우
    {
        mid++; // 실제 배열 수에 맞추기 +1
        System.out.println("찾는 수는 " + mid + "번째에 있습니다.");
    }

    else
        System.out.println("찾는 수가 없습니다.");

}

 

 

 

3. 특정 범위의 숫자 배열에 있는 각 숫자 개수 세기

 

M 이상 N 이하의 수가 순서 없이 나열 되었을 때 각 수가 몇 개인지 세기.
연령대에 따른 인원을 체크할 수 있다.

 

10명 중 20대는 2명입니다.
.
.
10명 중 80대는 1명입니다.
10명 중 90대는 1명입니다.

public static void main(String[] args) {
		
    int[] people = {55, 40, 27, 99, 76, 81, 29, 31,33, 62}; 
    int[] ages = new int[10]; // 연령대

    for(int i=0; i<people.length; i++)
    {
        int age = people[i]; // 연령

        if(age < 30) 
            ages[0]++;
        else if(age < 40)
            ages[1]++;
        else if(age < 50)
            ages[2]++;
        else if(age < 60)
            ages[3]++;
        else if(age < 70)
            ages[4]++;
        else if(age < 80)
            ages[5]++;
        else if(age < 90)
            ages[6]++;
        else if(age <= 100)
            ages[7]++;
    }

    int number = people.length;

    System.out.println(number + "명 중 20대는 " + ages[0] + "명입니다.");
    System.out.println(number + "명 중 30대는 " + ages[1] + "명입니다.");
    System.out.println(number + "명 중 40대는 " + ages[2] + "명입니다.");
    System.out.println(number + "명 중 50대는 " + ages[3] + "명입니다.");
    System.out.println(number + "명 중 60대는 " + ages[4] + "명입니다.");
    System.out.println(number + "명 중 70대는 " + ages[5] + "명입니다.");
    System.out.println(number + "명 중 80대는 " + ages[6] + "명입니다.");
    System.out.println(number + "명 중 90대는 " + ages[7] + "명입니다.");

}