[코드트리] 구슬의 이동 (Java)

[코드트리] 구슬의 이동 (Java)

문제

https://www.codetree.ai/cote/13/problems/marble-movement?utm_source=clipboard&utm_medium=text

풀이/후기

스터디 시간에 풀게된 문제이다.

처음엔 쉽다고 생각했는데, 한 칸에 여러개의 구슬이 존재할 때 우선순위에 따라 제거하는 작업이 까다로웠다.

그리고 이 문제를 통해 가장 먼저 느낀 것은 '자바의 한계' 였다.

평소에도 코테 준비하면서 파이썬이 훨씬 간단하다는 것은 알고 있었지만, 이번에 특히나 더 그렇게 생각이 된 것 같다.

(아마도 스터디원이 파이썬을 통해 객체 정렬을 구현한 것이 간단해 보여서 그랬을까..?)

 

아무튼 우선순위에 따라 가장 큰 항목을 남기기는 구현을 할 수 있겠는데,

우선순위에 따른 k개를 유지해야 한다는 것이 좀 어려웠던 것 같다.

이 부분은 정렬을 통해 해결할 수 있는데,

클래스이기 때문에 객체 비교를 이용해 정렬을 해야 한다.

생성한 클래스에서 comparable을 implements 이용해야 한다.

그래서 이 부분도 공부가 필요했다.

 

이 문제는 코드트리 문제 중에서도 제출한 사람이 적은 문제인 것 같다.

자바 검색을 해도 안나오는 것을 보니 이상하다고 생각했는데,,,

자바로 제출한 사람이 나밖에 없음ㅋㅋ

신기한 경험이었다.

그래도 코드트리에서 해설 코드를 제공해주어서 다행이지

혼자 고민하다가 삽질을 하루종일 할 뻔했다...

그래도 계속 보다보니 익숙해지고

계속 지웠다 썼다 하니 소스코드도 거의 외운 기분이다.

 

부디 나중에는 바로 생각나길...

코드

package CodeTree.Samsung.Simulation;
//코드트리
//구슬의 이동
//https://www.codetree.ai/cote/13/problems/marble-movement/description

import java.io.*;
import java.util.*;

public class marbleMovement {

	static class Circle implements Comparable<Circle> {
		//Collections.sort 사용을 위해 implements Comparable<Circle> 추가
		int v, num, d;

		Circle(int v, int num, int d) {
			this.v = v;
			this.num = num;
			this.d = d;
		}

		@Override
		public int compareTo(Circle other) {
			if(v != other.v) {
				return v - other.v;
			}
	        if(num != other.num) {
	        	return num - other.num;
	        }
	        return d - other.d;
		}
	}

	static int n, m, t, k;
	static int[][] dir = { { -1, 0 }, { 1, 0 }, { 0, 1 }, { 0, -1 } };
	static ArrayList<Circle>[][] grid = new ArrayList[50][50];
	static ArrayList<Circle>[][] nextGrid = new ArrayList[50][50];

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer str = new StringTokenizer(br.readLine(), " ");

		n = Integer.parseInt(str.nextToken());
		m = Integer.parseInt(str.nextToken());
		t = Integer.parseInt(str.nextToken());
		k = Integer.parseInt(str.nextToken());

		for (int i = 1; i < n + 1; i++) {
			for (int j = 1; j < n + 1; j++) {
				grid[i][j] = new ArrayList<>();
			}
		}

		for (int i = 1; i < m + 1; i++) {
			str = new StringTokenizer(br.readLine(), " ");
			int r = Integer.parseInt(str.nextToken());
			int c = Integer.parseInt(str.nextToken());
			String inp = str.nextToken();
			int v = Integer.parseInt(str.nextToken());

			int d = 0;
			if (inp.equals("U")) {
				d = 0;
			}
			if (inp.equals("D")) {
				d = 1;
			}
			if (inp.equals("R")) {
				d = 2;
			}
			if (inp.equals("L")) {
				d = 3;
			}

			// 정렬 시 속도 내림차순, 번호 내림차순이 되도록
			// (-속도, -번호, 방향) 순으로 대입
			grid[r][c].add(new Circle(-v, -i, d));

		}

		while (t-- > 0) {
			// nextGrid 초기화
			for (int i = 1; i < n + 1; i++) {
				for (int j = 1; j < n + 1; j++) {
					nextGrid[i][j] = new ArrayList<>();
				}
			}

			// 구슬의 이동
			movingFunc();

			// 구슬의 개수 조정
			selectCircle();

			for (int i = 1; i < n + 1; i++) {
				for (int j = 1; j < n + 1; j++) {
					grid[i][j] = (ArrayList<Circle>) nextGrid[i][j].clone();
				}
			}
		}

		int cnt = 0;
		for (int i = 1; i < n + 1; i++) {
			for (int j = 1; j < n + 1; j++) {
				cnt += grid[i][j].size();
			}
		}

		System.out.println(cnt);

	}

	static boolean inRange(int x, int y) {
		return 1 <= x && x <= n && 1 <= y && y <= n;
	}

	static void movingFunc() {
		for (int i = 1; i < n + 1; i++) {
			for (int j = 1; j < n + 1; j++) {
				for (int tm = 0; tm < grid[i][j].size(); tm++) {
					int v = grid[i][j].get(tm).v;
					int num = grid[i][j].get(tm).num;
					int d = grid[i][j].get(tm).d;

					int tv = -v;
					int cx = i;
					int cy = j;
					int nx = 1;
					int ny = 1;
					while (tv-- > 0) {
						nx = cx + dir[d][0];
						ny = cy + dir[d][1];
						if (!inRange(nx, ny)) {
							if (d == 0)
								d = 1;
							else if (d == 1)
								d = 0;
							else if (d == 2)
								d = 3;
							else if (d == 3)
								d = 2;
							nx = cx + dir[d][0];
							ny = cy + dir[d][1];
						}
						cx = nx;
						cy = ny;
					}

					nextGrid[nx][ny].add(new Circle(v, num, d));

				}
			}
		}
	}

	static void selectCircle() {
		for (int i = 1; i < n + 1; i++) {
			for (int j = 1; j < n + 1; j++) {
				int size = (int) nextGrid[i][j].size();

				if (size >= k) {
					// 우선순위를 위한 정렬
					Collections.sort(nextGrid[i][j]);
					// k개만 남도록 반복
					while ((int) nextGrid[i][j].size() > k) {
						// 가장 마지막에 있는 항목을 제거
						int t = nextGrid[i][j].size() - 1;
						nextGrid[i][j].remove(nextGrid[i][j].size() - 1);
					}
				}
			}
		}
	}
}

TestCase

#3 입력

4 4 4 1
1 1 L 1
1 3 R 2
2 2 U 1
3 2 D 3

 

#3 출력

3

 

Commit

https://github.com/allrightDJ0108/CodingTestStudy/commit/8acd47de157fdfbff2dfc2112258d965138cb85b

참고