벽에그린나의키

2019년 1월 13일 일요일

#5알고리즘 연습- K번째 수/JAVA & Shallow copy

K번째 수

문제 설명

배열 array의 i번째 숫자부터 j번째 숫자까지 자르고 정렬했을 때, k번째에 있는 수를 구하려 합니다.

예를 들어 array가 [1, 5, 2, 6, 3, 7, 4], i = 2, j = 5, k = 3이라면

array의 2번째부터 5번째까지 자르면 [5, 2, 6, 3]입니다.
1에서 나온 배열을 정렬하면 [2, 3, 5, 6]입니다.
2에서 나온 배열의 3번째 숫자는 5입니다.

배열 array, [i, j, k]를 원소로 가진 2차원 배열 commands가 매개변수로 주어질 때, commands의 모든 원소에 대해 앞서 설명한 연산을 적용했을 때 나온 결과를 배열에 담아 return 하도록 solution 함수를 작성해주세요.

제한사항

array의 길이는 1 이상 100 이하입니다.
array의 각 원소는 1 이상 100 이하입니다.
commands의 길이는 1 이상 50 이하입니다.
commands의 각 원소는 길이가 3입니다.

입출력 예

array	commands	return
[1, 5, 2, 6, 3, 7, 4]	[[2, 5, 3], [4, 4, 1], [1, 7, 3]]	[5, 6, 3]

입출력 예 설명

[1, 5, 2, 6, 3, 7, 4]를 2번째부터 5번째까지 자른 후 정렬합니다. [2, 3, 5, 6]의 세 번째 숫자는 5입니다.
[1, 5, 2, 6, 3, 7, 4]를 4번째부터 4번째까지 자른 후 정렬합니다. [6]의 첫 번째 숫자는 6입니다.
[1, 5, 2, 6, 3, 7, 4]를 1번째부터 7번째까지 자릅니다. [1, 2, 3, 4, 5, 6, 7]의 세 번째 숫자는 3입니다.

출처

문제풀이 IDEA

주어진 Array에 대해 command 내부 배열의 원소를 뽑아와 부분배열로 자를수 있었으면 좋겠다. 그럼 그 이후에 부분 배열에서 index를 뽑아오는일은 쉬운 일이지 않을까?

나의 코드⭐

import java.util.*;

class Solution {
    public int[] solution(int[] array, int[][] commands) {
        int answer[];
        answer = new int[commands.length];  // int[] answer = new int[commands.length] 로 간결하게 적어줄 수 있다

                                                JAVA array는 동적으로 크기가 변하지 않으므로 command의 길이로 array크기 설정

                                                왜 command의 크기로 설정하냐면 command = [[1,2],[3,4],[5,6]]일때 길이는 3이되는데

                                                2차배열 내부의 배열은 각각 answer array의 element하나하나를 나타내므로 length로 설정

        for(int i = 0; i <commands.length; i++){   // answer배열의 원소갯수는 command배열의 길이와 같으므로

int[] temp = Arrays.copyOfRange(array, commands[i][0]-1, commands[i][1]);  //copyOfRange 메서드를 이용하여 array배열을 부분배열로 저장
           Arrays.sort(temp);                                                         //저장된 temp를 오름차순으로 정렬해준다
           answer[i] = temp[commands[i][2]-1];                                        //command의 내부배열을 i를 이용해 순서대로 가져오는데 
            }                                                                           그 배열의 2번째 인덱스가 array의 부분배열에서 뽑아올

                                                                                        자리수를 가르키고 index는 그보다 1 작으므로 -1을 해준다

     return answer;
    }
}

눈 여겨볼 개념

Array.copyOfRange(copy할 대상 array, array의 시작 index, 마지막 index(전까지 copy))

Deepcopy와 Shallowcopy

①array ②int[] test1 = Arrays.copyOfRange(array,0,array.length);

③int[] test2 = Arrays.copyOf(array,array.length);

④int[] test3 = array

①[I@706a04ae ②[I@6eceb130
③[I@10a035a0 ④[I@706a04ae

1번과 4번은 같은 주소를 참조하고 있다 --객체복사
(shallow copy의 경우 따로 객체를 생성하고 그 안에 객체를 객체 복사한것)

쌍둥이가 같은 집에 살고 있다 -- 주소도 같고 집안에서 일어나는 일에 대해 영향을 받는다

2번과 3번은 새로운 주소를 할당받아 객체를 만들었다 -- shallow copy

쌍둥이가 다른집에서 살고있다 -- 주소는 다르지만 집안에서 일어나는 일에 대해서는 영향을 받는다(대신 immutable한 = 각자의 집에서의 일들은 서로에 영향을 미치지 않는다)

위의 2번과 3번은 확인해본결과

int[][] test2 = Arrays.copyOf(commands,commands.length);

System.out.println(commands[1][1]);

System.out.println(test2[1][1]);

System.out.println("----------------");

System.out.println(commands);

System.out.println(test2);

System.out.println("----------------");

test2[1][1] = 100;

System.out.println(commands[1][1]);

System.out.println(test2[1][1]);

4
4
----------------
[[I@706a04ae
[[I@6eceb130
----------------
100
100

이렇듯 다른 주솟값을 가지고 있지만 mutable한 값에 대해 변경사항이 서로 영향을
미치므로 shallow copy다(혹시 틀리면 지적 부탁드리겠습니다ㅠㅠ)

shallow copy를 할때에는 객체를 새로 생성하고 객체를 복사한다고 했는데
이때 [1, 2, 3 [4, 5, 6]]이런 경우에 1 2 3 은 현재 int라는 값이 복사된것이고
뒤에 [4, 5, 6] 이부분은 array이므로 주소가 복사되어있는데([1,2,3, ox100(주솟값)]이런느낌
int값의 변경은 독립되어 있어 original이랑 copy된 애랑 서로 영향을 안미치지만
array부분은 같은 주솟값을 참고 하고 있으므로 변경사항이 original이랑 copy값에 둘다 영향을 미친다

shallow copy와 deep copy에 대해

immutable /mutable 객체의 변경에 대해서

2D array change value

출처: 프로그래머스(https://programmers.co.kr)