[백준 17822번] 원판 돌리기 (java)

17822번: 원판 돌리기

몇번째 원판인지, 해당 원판에 어떤 숫자가 있는지를 2차원 배열을 만들어서 저장한다.

int[][] circle = new int[N+1][M+1];

 

x, d, k를 저장하는 Command 클래스를 만들고, T번마다 x, d, k 값이 다르므로 크기가 T인 배열을 생성한다.

Command[] cmd = new Command[T];

 

먼저, T번 반복하기 위한 반복문이 필요하다.

매번 cmd 배열에서 변수 x, d, k를 꺼내고, d가 0일 때(시계방향)와 d가 1일 때(반시계방향)의 케이스를 조건문으로 나누었다.

 

M+1 크기의 임시 배열 tmp를 만들고, 원판을 회전하고 난 후의 숫자들의 위치를 임시 배열에 담는다.

 

예를 들어, circle[1][1] = 1, circle[1][2] = 2, circle[1][3] = 3, circle[1][4] = 4 이고,

d= 0, k = 1 이어서 시계방향으로 한칸 움직어야 한다면, tmp 배열에 들어가는 값들은 다음과 같다.

tmp[1] = 4, tmp[2] = 1, tmp[3] = 2, tmp[4] = 3 

 

원판 회전이 모두 끝나고 나면 tmp에 저장된 숫자들을 다시 circle배열에 반영한다.

circle[1][1] = tmp[1] = 4

circle[1][2] = tmp[2] = 1

circle[1][3] = tmp[3] = 2

circle[1][4] = tmp[4] = 3

	for (int m = x; m <= N; m += x) {

		int[] tmp = new int[M + 1]; // 원판 회전 후 결과를 담을 임시배열

		if (d == 0) {     // 시계 방향
			for (int j = 1; j <= M; j++) {
				tmp[(j - 1 + k) % M + 1] = circle[m][j];
			}
		}

		else if (d == 1) { // 반시계 방향
			for (int j = 1; j <= M; j++) {
				tmp[(j - 1 - (k % M) + M) % M + 1] = circle[m][j];
			}
		}

		for (int j = 1; j <= M; j++) {
			circle[m][j] = tmp[j];
		}
	}

 

원판을 회전시키고 나면, 인접한 수를 모두 찾아서 HashSet에 저장한다. 

이중 for문을 돌면서 (i, j)를 기준으로 (i, j-1), (i, j+1), (i-1, j), (i+1, j) 중에 같은 수가 있는지 확인하고,

같은 수가 있으면 그 좌표를 HashSet에 넣는다.

 

Pos 클래스를 정의하여, i와 j 정보를 담도록 했다.

HashMap에 들어가는 객체는 이 Pos 객체가 된다.

static class Pos {

	int i, j;

	Pos(int i, int j) {
		this.i = i;
		this.j = j;
	}
}

 

HashSet을 사용하는 이유는 가장 안쪽 원판부터 가장 바깥쪽 원판까지 차례대로 인접한 수가 있는지 검사하는 과정에서 중복된 값을 넣을 수 있기 때문이다.

 

예를 들어, (1, 1)과 (2, 1)의 수가 같다고 할 때,

1번째 원판을 돌면서 (1, 1)과 (2, 1)의 수가 같은 것을 확인하고 HashSet에 (1, 1)과 (2, 1)을 넣는다.

그리고 2번째 원판 차례에서도 (2, 1)과 (1, 1)의 수가 같은 것을 확인하고 HashSet에 (1, 1)과 (2, 1)을 넣게 된다.

 

HashSet은 집합이므로 중복된 값을 넣어도 하나만 들어가므로 중복을 피할 수 있다.

	Set<Pos> set = new HashSet<>();

	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			if (circle[i][j] > 0) {
            
				int nj = (j + 1) <= M ? j + 1 : 1;  // 같은 원판 내에서 왼쪽 검사
				if (circle[i][nj] == circle[i][j]) { 
					set.add(new Pos(i, nj));
				}

				nj = (j - 1) >= 1 ? j - 1 : M;       // 같은 원판 내에서 오른쪽 검사
				if (circle[i][nj] == circle[i][j]) {
					set.add(new Pos(i, nj));
				}

                // 바깥쪽 원판에서 인접한지 검사
				if (i + 1 <= N && circle[i + 1][j] == circle[i][j]) {
					set.add(new Pos(i + 1, j));
				}

                // 안쪽 원판에서 인접한지 검사
				if (i - 1 >= 1 && circle[i - 1][j] == circle[i][j]) {
					set.add(new Pos(i - 1, j));
				}
			}

		}
	}

 

이렇게 지울 대상이 되는 위치를 HashSet에 넣고 나면, 

이 집합의 크기가 0일 때와 그렇지 않을 때로 나뉜다.

 

집합의 크기가 0 이라면, 지울만한 수가 없다는 뜻이므로 전체 원판 내의 수들의 평균을 구한 후,

평균보다 작으면 +1, 평균보다 크면 -1 해주는 작업을 한다.

 

집합의 크기가 0보다 크면, 지울만한 수가 있다는 뜻이므로 인접한 수들을 모두 지운다.

나는 지운다는 것을 해당 수가 0이 되는 경우라고 정하고, circle[i][j]를 0으로 바꾸는 작업을 했다. 

	if (set.size() == 0) { // 집합의 크기가 0인 경우
		int sum = 0;
		int cnt = 0;

		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= M; j++) {
				if (circle[i][j] > 0) {
					sum += circle[i][j];
					cnt++;
				}
			}
		}

		double avg = (double) sum / (double) cnt; // 평균

		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= M; j++) {
				if (circle[i][j] > 0) {

					if (circle[i][j] < avg) // 평균보다 작으면
						circle[i][j]++;

					else if (circle[i][j] > avg) // 평균보다 크면
						circle[i][j]--;
				}
			}
		}
	}

	else {  // 집합의 크기가 0이 아닌경우

		Iterator<Pos> it = set.iterator();
		while (it.hasNext()) {
			Pos pos = it.next();
			circle[pos.i][pos.j] = 0; // 집합에서 위치정보 하나씩 꺼내서 0으로 바꿔줌
		}
	}

 

T번의 횟수가 모두 끝나고 나면, 원판의 수들 중 0이 아닌 것들을 모두 더하고, 그 결과를 반환한다.

	int sum = 0;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			sum += circle[i][j];
		}
	}

	return sum;

 

 

전체 코드 :