[Lv.0] 최댓값 구하기 (1)

https://school.programmers.co.kr/learn/courses/30/lessons/120847

프로그래머스

 

문제 설명

정수 배열 numbers가 매개변수로 주어집니다.

 numbers의 원소 중 두 개를 곱해 만들 수 있는 최댓값을 return하도록 solution 함수를 완성해주세요.

 

제한 사항

 

입출력 예

 

입출력 예 설명

아이디어 (큰 틀)

• 배열 전체를 돌면서 가장 최대인 값과, 그 다음 큰 값을 찾는다.
• 최댓값, 최댓값보다 하나 작은 값 => 이게 최댓값이 되도록.
• 또 다른 방법은 완전탐색, 일일이 다 돌기
• 아니면 최댓값 일일이 찾기 어려우니 정렬 먼저 시켜놓고 해도 됨.   

방법 2가지가 있는데,

<첫 번째>

최댓값과 그 다음 최댓값을 찾는다.

최댓값보다 하나 작은 값이 최댓값이 되도록!

 

1등을 제거하는 방법

- 배열의 원소를 삭제하지 않고 1등이 1등이 아니게.

- 임의의 값으로 조작한다.

--------------------------------------------------------------------------------------------------

최댓값을 찾고 나서 max를 다시 0으로 바꿔준다.

 

초기 코드

class Solution {
  public int Solution(int[] numbers) {
    int answer = 0;
    int max = 0;

    for (int i = 0; i < numbers.length; i++) {
      if (max<numbers[i]) {
        max = numbers[i];
      }
    }
    numbers[i] =0; // 다시 초기화
    return answer;
  }
}

 

numbers[i]에 0을 집어넣었지만, 값이 복사가 되었기 때문에

max를 아무리 조작을 해도 numbers[i]는 전혀 영향을 받지 않는다.

그래서 최댓값을 조작하고 싶으면 numbers를 조작해야 하는데, 

근데 여기서는 numbers[i] =0;에서 i를 읽어오지 못한다.

 

class Solution {
  public int Solution(int[] numbers) {
    int answer = 0;
    int max = 0;
    int i = 0;
    for (i = 0; i < numbers.length; i++) {
      if (max<numbers[i]) {
        max = numbers[i];
      }
    }
    numbers[i] =0; // 다시 초기화
    return answer;
  }
}

여기서 또 문제는 for문이 끝나고 나면 i는 마지막 값인 상태일 것이다 항상. (ㅑ++)이 계속 되고 있으니까.

- 중요한 것은 최댓값의 위치를 정확하게 아는 것.

 

수정하면

class Solution {
  public int Solution(int[] numbers) {
    int answer = 0;
    int max = 0;
    int i = 0;
    int index = 0; // 최댓값의 인덱스를 저장하기 위한 변수
    for (i = 0; i < numbers.length; i++) {
      if (max<numbers[i]) {
        max = numbers[i];
        index = i; // 최댓값의 인덱스 저장
      }
    }
    numbers[index] =0; // 다시 꼴등으로 내림.
    return answer;
  }
}

 

이제 두 번째 최댓값 찾으러 가야.

그리고 변수에 결과값을 저장하는 걸 빼먹으면 안 된다.

class Solution {
  public int Solution(int[] numbers) {
    int answer = 0;
    int max = 0;
    int i = 0;
    int index = 0; // 최댓값의 인덱스를 저장하기 위한 변수
    
    for (i = 0; i < numbers.length; i++) {
      if (max<numbers[i]) {
        max = numbers[i];
        index = i; // 최댓값의 인덱스 저장
      }
    }
    int result1 = numbers[index];
    numbers[index] =0; // 다시 꼴등으로 내림.
    for (i = 0; i < numbers.length; i++) {
      if (max<numbers[i]) {
        max = numbers[i];
        index = i; // 최댓값의 인덱스 저장
      }
    }
    int result2 = numbers[index];
    answer = result1 * result2;
    return answer;
  }
}

여기서 약간의 수정이 필요한데,

첫 번째 반복문에서는 max가 이미 최대가 되어서 나왔는데,

두 번째 반복문 탈 때도 역시 최댓값인 상태로 타게 되어서 문제가 발생할 것이다.

그래서 max도 두 번째 타기 전에 초기화가 필요하다.

 

class Solution {
  public int Solution(int[] numbers) {
    int answer = 0;
    int max = 0;
    int i = 0;
    int index = 0; // 최댓값의 인덱스를 저장하기 위한 변수

    for (i = 0; i < numbers.length; i++) {
      if (max<numbers[i]) {
        max = numbers[i];
        index = i; // 최댓값의 인덱스 저장
      }
    }
    
    int result1 = numbers[index];
    numbers[index] =0; // 다시 꼴등으로 내림.
    max = 0;

    for (i = 0; i < numbers.length; i++) {
      if (max<numbers[i]) {
        max = numbers[i];
        index = i; // 최댓값의 인덱스 저장
      }
    }
    int result2 = numbers[index];
    answer = result1 * result2;
    return answer;
  }
}

---

 

<두 번째>

완전탐색

• 더 무식한 방법이지만 범용성을 지니고 있다.
• 모든 경우의 수를 다 해보고, 그 중에 최대를 고른다.
• 가장 안전한 방법이지만, 시간이 오래걸릴 수 있다.
• for문으로 구현이 가능하다.
• 두 개의 for문을 끝까지 돌면서 찾기.

초기 코드

class Solution {
  public int solution(int[] numbers) {
    int answer = 0;
    int max = 0;
    for (int i = 0; i < numbers.length; i++) {
      for (int j = 0; j < numbers.length - 1; j++) {
        answer = numbers[i] * numbers[j];
      }
    }
    if (max < answer) {
      max = answer;
    } 
    return max;
  }
}

이렇게 하면 그런데 비교가 딱 한번만 되어 나온다.(마지막에 나온 것만)

최댓값을 구할 때도 완전탐색의 개념이 된다.

그러니까, 매번 비교해야 한다.

즉, 반복문 속에 비교 로직이 들어가야 한다는 뜻.

곱하고 나서 비교하는 순서가 맞다.

 

수정하면

class Solution {
  public int solution(int[] numbers) {
    int answer = 0;
    int max = 0;
    for (int i = 0; i < numbers.length; i++) {
      for (int j = 0; j < numbers.length - 1; j++) {
        answer = numbers[i] * numbers[j];

        if (max < answer) {
          max = answer;
        }
      }
    }
    return max;
  }
}

그런데 여기서는 i와 j가 같을 때도 수행이 된다는 맹점이 있다.

이걸 체크하는 부분을 따로 집어넣어줘야 한다.

그리고

for (int j = 0; j < numbers.length - 1; j++) 이 부분은 j를 마지막 칸은 비교를 안 한다는 소리이므로 주의.

지금은 i가 마지막 칸까지 커버를 해주기 때문에 문제가 없었는데, 항상 주의해야 함.

 

 

class Solution {
    public int solution(int[] numbers) {
        int answer = 0;
        int max =0;
        for(int i=0; i<numbers.length; i++) {
            for(int j=0; j<numbers.length; j++) {
                if(i!=j) {
                    answer  = numbers[i] * numbers[j];
                }
                if(max < answer) {
                    max = answer;
                }
            }
        }
        
        return max;
    }
}

완전히 똑같은 거니라고 물어보는 것.

 

 

나의 코드

버전 1

class Solution {
  public int Solution(int[] numbers) {
    int answer = 0;
    int max = 0;
    int i = 0;
    int index = 0; // 최댓값의 인덱스를 저장하기 위한 변수

    for (i = 0; i < numbers.length; i++) {
      if (max<numbers[i]) {
        max = numbers[i];
        index = i; // 최댓값의 인덱스 저장
      }
    }
    
    int result1 = numbers[index];
    numbers[index] =0; // 다시 꼴등으로 내림.
    max = 0;

    for (i = 0; i < numbers.length; i++) {
      if (max<numbers[i]) {
        max = numbers[i];
        index = i; // 최댓값의 인덱스 저장
      }
    }
    int result2 = numbers[index];
    answer = result1 * result2;
    return answer;
  }
}

 

 

버전 2

class Solution {
    public int solution(int[] numbers) {
        int answer = 0;
        int max =0;
        for(int i=0; i<numbers.length; i++) {
            for(int j=0; j<numbers.length; j++) {
                if(i!=j) {
                    answer  = numbers[i] * numbers[j];
                }
                if(max < answer) {
                    max = answer;
                }
            }
        }
        
        return max;
    }
}