[Lv.0] 수열과 구간 쿼리

 

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

프로그래머스

극강의 난이도 문제!!!

 

문제 설명

정수 배열 arr와 2차원 정수 배열 queries이 주어집니다. queries의 원소는 각각 하나의 query를 나타내며, [i, j] 꼴입니다.

각 query마다 순서대로 arr[i]의 값과 arr[j]의 값을 서로 바꿉니다.

위 규칙에 따라 queries를 처리한 이후의 arr를 return 하는 solution 함수를 완성해 주세요.

 

제한 사항

 

입출력 예

 

입출력 예 설명

 

 

아이디어

1)

지금 queries의 [0,.3], [1,2], [1,4] 가 하나의 쿼리의 쌍이라는 이야기

즉 queries는 행 하나하나가 하나의 쿼리다.

쌍끼리 자리를 바꿔서 내보내는 것을 쿼리마다 순서대로 하면 되는 것.

 

짝의 연관성 헷갈렸는데, 아마 입력으로 완전 랜덤.

 

2)

나는 queries를 알고 있기 때문에 queries의 1행1열이 0이고, 1행2열이 3인 건 모르더라도,

1행1열과 1행2열을 단순히 가져오는 것은 가능.

이걸 a와 b에 담았다고 하면, a와 b의 숫자가 무엇인지는 관심 없이, 위치를 바꿔주기만 하면 되는 것.

• queries[i][j] => a, b라고 하면 b, a번째 순서를 바꾸면 되고, a와 b가 어떤 수인지는 관심 없다.

 

3) 입출력 예에 있는 숫자를 다 하나씩 사례로 써보기

3-1)

arr[0] -> arr[3], arr[3] -> arr[j] ==> result[0] -> arr[j], result[3] -> arr[i]

 

3-2) i, j도 0, 3을 이용해서 충분히 표현 가능 불필요한 건 지우기

arr[0], arr[3] ==> result[0] -> arr[3], result[3] -> arr[0]

 

3-3) 사례 3개 다 써보기

arr[0], arr[3] ==> result[0] -> arr[3], result[3] -> arr[0]

arr[1], arr[2] ==> result[1] -> arr[2], result[2] -> arr[1]

arr[1], arr[4] ==> result[1] -> arr[4], result[4] -> arr[1]

 

이 세개를 다 써보니

왜 3번을 썼을까? queries의 짝이 3개였으니까. 

queries가 결정, 반복횟수는 queries의 길이가 결정.

 

4)

이제 이 세 문장을 반복문으로 바꾸기

• 요령: 바뀌는 것과 바뀌지 않는 것을 구분.
• 인덱스만 찾으면 일단 된다.
• 0, 3을 queries에 대한 식으로 표현

4-1) arr[0], arr[3] // arr[1], arr[2] // arr[1], arr[4] 를 queries에 대한 식으로 표현

(1) arr[0] -> arr[queries[0][0]]

     arr[3] -> arr[queries[0][1]]

 

(2) arr[1] -> arr[queries[1][0]]

     arr[2] -> arr[queries[1][1]]

 

(3) arr[1] -> arr[queries[2][0]]

     arr[4] -> arr[queries[2][1]]  

 

4-2) 위에서 -> 의 의미는 이것이 대입된다는 소리이므로 대입 연산자로 변경

result[0] = arr[3],  result[3] = arr[0]

result[1] = arr[2], result[2] = arr[1]

result[1] = arr[4], result[4] = arr[1]

 

4-3) arr[queries[ ][ ]] 형식으로 마저 바꾸기

result[0] = arr[queries[0][1]],  result[3] = arr[queries[0][0]]]

result[1] = arr[querise[1][0]], result[2] = arr[queries[1][1]]

result[1] = arr[queries[2][1]], result[4] = arr[querise[2][0]]

 

result[queries[0][0]] = arr[queries[0][1]], result[queries[0][1]] = arr[queries[0][0]]]

result[queries[1][0]] = arr[queries[1][1]], result[queries[1][1]] = arr[queries[2][0]]

result[queries[2][0]] = arr[queries[2][1]], result[queries[2][1]] = arr[queries[1][0]]

 

4-4)

queries가 0, 1, 2 이렇게 변하니까,  행도 결국엔 queries의 현재 값과 똑같다.

 
이제 반복문 만들어서 넣어보기

Class Solution {
	public int[] solution(int[] arr, int[][] queries) {
    	int[] answer = {};
        
        for(int i=0; i<queries.length; i++) {
        	// result[queries[0][0]] = arr[queries[0][1]];
            // result[queries[0][1]] = arr[queries[0][0]]];
        }    
    }

}

일단 이 모양인데, 세 사례를 전부 보면, 열은 안 바뀌고 있다. 행만 바뀌고 있음.

queries의 행은 0부터 2까지 변하고 있음.

지금 queries의 길이도 0부터 2까지 변하고 있으니 반복문에서

저 행을 i로 대체할 수 있다는 것이다.

 

Class Solution {
	public int[] solution(int[] arr, int[][] queries) {
    	int[] answer = {};
        
        for(int i=0; i<queries.length; i++) {
        	result[queries[i][0]] = arr[queries[i][1]];
            result[queries[i][1]] = arr[queries[i][0]]];
        }    
    }

}

 

이제 결과인 result 배열을 만들어서 작업 계속 하기

result의 길이는 arr 길이와 같음.

Class Solution {
	public int[] solution(int[] arr, int[][] queries) {
    	int[] result = new int[arr.length];
        
        for(int i=0; i<queries.length; i++) {
        	result[queries[i][0]] = arr[queries[i][1]];
            result[queries[i][1]] = arr[queries[i][0]]];
        }    
        return result;
    }
}

이렇게 하면 마지막 원소 업데이트가 안 되었다고 결과 출력

문제가 뭐였냐, 나는 지금 결과를 바로바로 result에 담고 있었다.

이렇게 되면...

앞 실행이 뒷 실행에 영향을 주는 상태가 되어버려서, 문제에서 원하는 결과가 나오지 않게 됨.

 

아이디어가 swap!

arr[queries[i][1]]; 와 arr[queries[i][0]]]을 바꾸고 싶어요!

 

최

나의 코드

class Solution {
    public int[] solution(int[] arr, int[][] queries) {
        int[] result = new int[arr.length];

        int temp = 0;
        int x = 0;
        int y = 0;
        for(int i=0; i<queries.length;i++) {
            x = arr[queries[i][1]];
            y = arr[queries[i][0]];
            temp = x;
            x = y;
            y = temp;
            arr[queries[i][1]] = x; // 배열에 바로 집어넣기
            arr[queries[i][0]] = y;
        }
        
        return arr;
    }
}