🔧

알고리즘/다형성

서정희_1012

최대값 구하기 알고리즘

문제1) https://codeup.kr/problem.php?id=2081&rid=0

주어진 배열을 한번 순회하며 탐색하면 해결할 수 있다.

→ 시간복잡도는 빅오 표기법으로 표기했을시에 O(N)에 해당한다.

(이때 위의 문제에서의 N=9)

O(N)의 의미

전체 코드

import java.util.Scanner;

public class CodeUp2081 {
    public static void main(String[] args) {
        int max = 0,index = 0;
        Scanner sc = new Scanner(System.in);
        for(int i=1;i<10;i++){
            int now= sc.nextInt(); 
            if(max<now||(i==1)){
                max= now;
                index=i;
            }
        }
        System.out.println(max);
        System.out.println(index);
    }
}
Java
복사

만약 주어진 배열이 다음과 같다고 하자.

0	1	2	3	4	5	6	7	8
3	29	38	12	57	74	40	85	61

for(int i=1;i<10;i++){
            int now= sc.nextInt(); 
            if(max<now||(i==1)){
                max= now;
                index=i;
            }
        }
Java
복사

위와 같이 반복문이 진행됨에 따라 각각의 변수의 값은 다음과 같이 변하게 된다.

i	1	2	3	4	5	6	7	8	9
now	3	29	38	12	57	74	40	85	61
max	3	29	38	38	57	74	74	85	85
index	1	2	3	3	5	6	6	8	8

따라서 max는 85, index는 8이 출력된다.

•

최대값 구하기 알고리즘 구현 시 주의사항

만약 max에 다음과 같이 배열의 첫번째 값을 대입하지 않았다면 무슨 문제가 발생할까?

int max = 0;
if(max<now||(i==1)){
      max= now;
      index=i;
}
Java
복사

해당 문제는 배열의 값이 자연수로 제한되어있다. 따라서 max를 0으로 초기화해도 문제가 없다.
하지만 만약 배열의 값이 음수가 나올 수 있는 환경에서의 최대값을 구하는 문제라면?
→최대값이 0이 되는 오류 발생 가능

문제2) 최대값 2 (codeup.kr)

주어진 이차원 배열을 한번 순회하며 탐색하면 해결할 수 있다.

→ 시간복잡도는 빅오 표기법으로 표기했을시에 O(N^2)에 해당한다.

(이때 위의 문제에서의 N=9)

전체 코드

import java.util.Scanner;

public class CodeUp4596 {
    public static void main(String[] args) {
        int max=-1;
        int indexX=-1;
        int indexY=-1;
        Scanner sc = new Scanner(System.in);
        for(int i=1;i<10;i++){
            for(int j=1;j<10;j++){
                int now= sc.nextInt();
                if(max<now||(i==1&&j==1)){
                    max= now;
                    indexX=i;
                    indexY=j;
                }
            }

        }
        System.out.println(max);
        System.out.println(indexX+" "+indexY);
    }
}
Java
복사

문제 1과 같은 방법으로 작성하였다.

마찬가지로 max의 값을 이차원 배열에서의 제일 처음 값으로 초기화해주어야 한다.

if(max<now||(i==1&&j==1)){
    max= now;
    indexX=i;
    indexY=j;
}
Java
복사

박수진_1012

다형성 적용

•

코드의 중복 없이 min,max를 모두 이용할 수 있도록 callback메서드를 사용하여 구성

코드:

getMaxOrMin

•

파라미터값 : int[] arr 배열/ Compare 인터페이스

•

출력값: Compare 에 따른 Max이거나 Min값

•

설명: 배열의 첫번째 값을 기준으로 Compare에서 비교식을 받아와 for문을 돌린다.

•

max인 경우 arr[i] > targetValue

•

min인 경우 arr[i] < targetValue

max

•

Comare 인터페이스를 오버라이딩하여 valueA와 valueB를 max값을 구할 수 있도록 return해줌

min

•

Comare 인터페이스를 오버라이딩하여 valueA와 valueB를 min값을 구할 수 있도록 return해줌

전체 로직

•

CallBack 작동 방식을 사용하여 main에서 max함수를 호출하고, getMaxOrMin함수를 호출하게된다. 하지만 호출할 때에는 Compare 인터페이스를 구현해주는 구현체를 함께 넘겨서 getMaxOrMin함수에서 compare메서드를 호출하게 될 때 해당 넘어온 호출함수로 다시 돌아가서 해당 메서드를 실행하게 된다.

전체코드