데브 매칭 지원시 실제론 못풀었던 문제…

앞에 문제나 뒤에 문제에 너무 시간을 소비했었다.

이제 와서 풀어보니, 무난하게 풀릴듯.

먼저 문제 설명을 하자면

예시로 $ 6 X 6 $ 사이즈의 행렬이 있다고 할때

아래와 같은 그림처럼 표기할 수 있다.

grid_example.png

이때 각 행렬 좌표 두개의 쌍으로 이루어진 요구사항 (문제상에서는 query) 에 맞춰

해당 좌표 내에 행렬 값들을 시계 방향으로 회전시킨다.

아래 그림은 (2, 2), (5, 4) 를 기준으로 했을 때 회전 예시이다.

rotation_example.png

이러한 요구사항들로 행렬을 회전시킨뒤 이동한 값중 최소값을 반환하면 되는 문제

  1. 요구사항대로 행렬을 회전
  2. 회전중에 값을 체크하여 가장 작은 값만 도출
  3. 요구 사항별로 반복

으로 완료되는 문제.

풀이⌗

회전이라고 해서 복잡하게 생각할 필요 없이,

  1. 목표 가장 상위 열 을 우측 으로 이동
  2. 목표 가장 우측 행 을 아래 로 이동
  3. 목표 가장 하위 열 을 좌측 으로 이동
  4. 목표 가장 좌측 행 을 상단 으로 이동

으로 나누어서 생각하면 편할 듯 싶다.

그렇다면 예시로 목표 가장 상위 열을 우측으로 이동 같은 경우에

목표 가장 상위 열 과 우측으로 이동 을 구현하여야 하는데

목표 가장 상위 열 의 경우

요구사항인 query를 [(x1, y1), (x2, y2)] 표기할 수 있을때

목표 가장 상위 열 은 (*, y1) 이다

이때 우측으로 이동의 이동 범위 지정을 해줘야 하는데

이동 범위는 x1 ~ x2 까지 이다

이와 같은 방식으로 나머지 부분도 구현을 진행하면 해결되는 문제

나머지는 사소한 것들이 남아 있는데,

내가 푼 방식의 경우 이차원 배열을 통한 행렬을 표현하였는데, 인덱스가 0부터 시작이기에

요구사항 query의 행렬과 값을 일치시키기 위해 0번 행과 0열을 넣은 이차원 배열을 생성하였다.

마지막으로 회전 기능 구현 코드이다.

사용할 행렬 이차원 배열 과, 요구사항을 구현한 클래스인 Query를 사용하여 구현하였다.

private int rotate(int[][] map, Query query) {
		int startPoint = map[query.a.x][query.a.y];
		int min = startPoint;
		//상단 우측으로 | a.x -> b.x , a.y 그대로
		for (int x = query.a.x; x < query.b.x; x++) {
			map[x][query.a.y] = map[x + 1][query.a.y];
			min = Math.min(min, map[x][query.a.y]);
		}
		//우변 하단으로 | b.x 그대로, a.y -> b.y
		for (int y = query.a.y; y < query.b.y; y++) {
			map[query.b.x][y] = map[query.b.x][y + 1];
			min = Math.min(min, map[query.b.x][y]);
		}

		// 하단 좌측으로 | b.x -> a.x | b.y 그대로
		for (int x = query.b.x; x > query.a.x; x--) {
			map[x][query.b.y] = map[x - 1][query.b.y];
			min = Math.min(min, map[x][query.b.y]);
		}

		// 자변 위쪽으로 | a.x 그대로 | b.y -> a.y
		for (int y = query.b.y; y > query.a.y; y--) {
			map[query.a.x][y] = map[query.a.x][y - 1];
			min = Math.min(min, map[query.a.x][y]);
		}
		map[query.a.x][query.a.y + 1] = startPoint;
		return min;
	}

참고⌗