메멩
123
2021-09-12 17:56:41
7
217

백준 2562번 최댓값구하기 문제. 왜 틀렸을까요..?


코테 이제 시작한 완전 초보입니다. 이해해주세요ㅎㅎ


9개의 서로 다른 자연수가 주어질 때, 이들 중 최댓값을 찾고 그 최댓값이 몇 번째 수인지를 구하는 프로그램을 작성하시오.

예를 들어, 서로 다른 9개의 자연수

3, 29, 38, 12, 57, 74, 40, 85, 61

이 주어지면, 이들 중 최댓값은 85이고, 이 값은 8번째 수이다.

입력
첫째 줄부터 아홉 번째 줄까지 한 줄에 하나의 자연수가 주어진다. 주어지는 자연수는 100 보다 작다.

출력
첫째 줄에 최댓값을 출력하고, 둘째 줄에 최댓값이 몇 번째 수인지를 출력한다.


import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

//최댓값
public class Main {

    public static void main(String[] args) throws IOException {


        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int[] arr = new int[9];

        for(int i=0; i<9; i++) {
            String a = br.readLine();
            arr[i] = Integer.parseInt(a);
        }
        int[] arr1 = arr;
        Arrays.sort(arr);
        int[] arr2 = arr;

        System.out.println(arr1[arr1.length-1]);
        for(int i=0; i< arr1.length; i++) {
            if(arr1[i] == arr2[8]) {
                System.out.println(i);
            }
        }

    }

}

실행하면 예제는 잘 출력되는데 틀렸다고 나오네요. 다른 방식으로 정답을 맞추기는 했지만 이게 왜 틀렸는지에 대한 궁금증이 계속 남아서 글 올립니다. 선배님들 가르침 부탁드립니다

0
  • 답변 7

  • yeori
    2k
    2021-09-12 18:33:07

    위코드에서는 최대값이 정렬하기전에 몇번째 값인지 추적할 수가 없겠네요

    오름차순으로 정렬했으니 최대값은 맨 끝에 있겠죠

    근데 정렬전에 3번째였는지 첫번째였는지 알 수가 없습니다.

  • 메멩
    123
    2021-09-12 19:15:52

    yeori
    잘 이해가 가지 않습니다.

    정렬 전 배열 arr1

    정렬 후 배열 arr2

    arr1 = [3, 29, 38, 12, 57, 74, 40, 85, 61]

    arr2 = [3, 12, 29, 38, 40, 57, 61, 74, 85]

    arr1[i] = arr2[8] 일때 i값을 출력했으니 몇번째 값인지 추적

    두번째 for문에서 arr1의 값과 arr2의 마지막값(최대값)과 비교했으니까

    찾은거 아닌가요..??


  • 제타건담
    7k
    2021-09-12 20:16:50 작성 2021-09-12 20:17:32 수정됨

    이 문제는 정렬을 하면 오히려 풀지를 못합니다..

    정렬을 해버리면 항상 최대값은 배열의 맨 마지막 요소가 되어버리기 때문에 입력된 상태의 그 당시의 값을 가져오질 못합니다..

    문제를 보면 입력할 당시의 최대값의 위치는 8번째이지만..

    정렬을 한 뒤의 85의 위치는 배열의 맨 마지막 위치인 9번째가 되기 때문에 틀린겁니다..

    내가 숫자를 입력했을때 3번째에 최대값을 입력했으면 그 위치인 3이 나와야 하는겁니다..

    그러나 정렬을 해버리면 매번 최대값이 마지막에 오기 때문에 원래 입력했을때의 위치를 가져오지 못합니다..

    푸는 방법은 의외로 단순합니다만..이걸 알려드리면 공부의 의미가 없습니다..

    한가지 힌트를 드리면 정렬을 해서 최대값을 찾으려 하지 마시고..직접 최대값을 찾으려고 하세요..


  • yeori
    2k
    2021-09-12 20:33:28 작성 2021-09-12 20:46:15 수정됨

    아하~ 이 지점에서 오해가 있군요.

    이런 코드를 쓰셨는데...

    int[] arr1 = arr;
    Arrays.sort(arr);
    int[] arr2 = arr;

    여기서 arr1 이 arr을 "참조하게" 했습니다. 더 정확하게 말로 풀면 아래와 같습니다.

    arr이 가리키고 있는 대상(배열)을 arr1 도 같이 가리키게 함

     이 지점까지는 아래의 그림이 맞습니다.

    arr1 = [3, 29, 38, 12, 57, 74, 40, 85, 61]

    그런데 정렬을 하고나면 arr과 arr1 변수가 함께 가리키는 배열은 아래와 같이 정렬이 끝난 상태입니다.

    
    arr     arr1
     |       |
     v       v
    [3, 12, 29, 38, 40, 57, 61, 74, 85]

    질문하신 분은 assign을 하면 정렬 직전의 배열의 상태를 그대로 간직할거라고 생각하지만, 배열과 같은 참조 타입 변수는 assign을 하면 배열의 위치만 가리키는 식으로 작동합니다.

    그러니까 하나의 배열을 참조하는 여러개의 변수가 있을때(arr, arr1, arr2) 이중 누구를 사용해서든 배열의 값을 변경하면 그 변경은 모든 변수에게 다 보입니다. 여기서는 Arrays.sort 를 호출해서 배열내의 숫자들을 다 뒤집고, 이 변경은 arr, arr1, arr2 모두에게 동일하게 보입니다.

    원래 의도대로 코드를 수정하면 아래와 같습니다.

    int[] arr1 = Arrays.copyOf(arr, arr.length);
    Arrays.sort(arr);

    Arrays.copyOf 는 주어진 배열의 처음부터 두번째 인자의 갯수만큼만 복사해서 "새로운 배열"을 반환합니다.

    위와같이 수정하면 arr1과 arr2는 서로 다른 배열을 가리키기때문에 의도하신대로 작동은 할겁니다.



    그런데 위 문제는 굳이 별도의 배열을 따로 만들지 않고도 자료구조를 개선해서 더 낫게 구현할 수도 있습니다.

  • 메멩
    123
    2021-09-13 08:33:37

    제타건담

    yeori 

    두분다 답장 주셔서 감사합니다.


    import java.util.Arrays;
    class Main {
      public static void main(String[] args) {
        int[] arr = new int[5];
        arr[0] = 5;
        arr[1] = 3;
        arr[2] = 8;
        arr[3] = 1;
        arr[4] = 4;
    
        int[] arr1 = Arrays.copyOf(arr, arr.length);
        System.out.println("복사값 : " + arr1);
        System.out.println("sort 전 : " + arr);
        for(int i=0; i<5; i++) {
          System.out.println(arr[i]);
        }
        Arrays.sort(arr);
        System.out.println("sort 후 : " + arr);
        for(int i=0; i<5; i++) {
          System.out.println(arr[i]);
        }
        System.out.println(arr);
      }
    }

    이런식으로 해보니 정렬해도 참조값이 같은걸 확인할 수 있었습니다. 덕분에 이해가 잘 됐습니다.

    추가로 copyOf도 알게 되었습니다. 정말 감사합니다!!!!!!!

  • 제타건담
    7k
    2021-09-13 14:17:48 작성 2021-09-13 14:24:37 수정됨


    class Main {
      public static void main(String[] args) {
        int[] arr = new int[5];
        arr[0] = 5;
        arr[1] = 3;
        arr[2] = 8;
        arr[3] = 1;
        arr[4] = 4;
        
        int maxval = -1; // 최대값
        int maxloc = -1; // 최대값 위치
        int arrlength = arr.length; // 배열 길이
    
       for(int i=0; i < arrlength; i++){
         if(maxval < arr[i]) {
           maxval = arr[i];
           maxloc = i + 1;
         }
       }
    
      System.out.println("최대값 : " + maxval);
      System.out.println("위치 : " + maxloc);
    }

    정렬은 제일 작은거부터 제일 큰거까지 또는 제일 큰거부터 제일 작은거까지 순서대로 전부를 알아야 할때는 사용하지만

    단순히 최대값 또는 최소값만 구하는 거라면 정렬을 사용하는건 오히려 낭비입니다..

    정렬에 따른 연산 비용이 크기 때문이죠..

    상황에 따라 정렬을 써야 할지 말아야 할지도 생각하세요..

  • 메멩
    123
    2021-09-13 17:34:57

    제타건담 

    선배님 코드 잘 봤습니다. 연산비용까지 고려할 생각을 하지 못했습니다. 뭔가 문제 풀때마다 급급하게 정답만 맞춰보자 식으로 접근하다보니 그부분까지는 생각을 못했네요ㅎㅎ

    가르침 감사합니다!!!

  • 로그인을 하시면 답변을 등록할 수 있습니다.