[코드트리 - L12] 25년 하반기 오전 1번 문제 - 택배 하차

코딩테스트 기출 문제 설명: 택배 하차 | 코드트리

코딩테스트 기출 문제 택배 하차의 상세 설명입니다. 문제 요구사항을 정확히 파악하고 효율적인 알고리즘을 설계해보세요.

www.codetree.ai

테스트케이스 #3

입력

30 20
98 2 10 12
15 6 1 1
45 9 5 2
49 3 8 8
34 8 2 21
40 7 7 23
79 8 5 16
5 7 7 7
6 4 6 25
94 4 6 19
26 5 3 2
35 5 2 29
8 14 10 5
86 11 13 16
60 4 1 1
88 7 3 2
38 1 1 1
32 1 9 16
30 2 8 18
7 1 5 10

출력

7
6
15
30
26
32
38
35
60
40
45
34
8
79
88
86
5
94
49
98

문제 풀이

c열 위치의 w x h 크기 k번 택배를 밑으로 이동할 수 있으면 이동하고, 아래에 다른 택배가 있다면 이동을 멈춘다.

택배 하차를 시키는데, 왼쪽 한번 오른쪽 한번 택배를 빼낸다.

1) 왼쪽 택배 하차

택배의 왼쪽이 모두 비어있다면, 왼쪽으로 하차시킬 수 있다.

2) 오른쪽 택배 하차

택배의 오른쪽이 모두 비었다면, 오른쪽으로 하차시킬 수 있다.

각 택배를 하차시킨 후 출력하고, 다시 아래로 내려갈 수 있는 택배는 아래로 내린다. 더이상 하차시킬 수 없다면 멈춘다.

코드 풀이

1. 입력 및 M 개의 택배 위치 2차원 배열 map에 표시

0부터 내려갈 수 있는 최대 길이인 N - h 까지 범위에서, 시작 위치 (0, c)에서 내려갈 수 있는 만큼의 dropRow를 구한다.
dropRow에서 h만큼과 c에서 c + w 까지 택배 번호 k를 표시한다.

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] input;

input = br.readLine().split(" ");
N = Integer.parseInt(input[0]);
M = Integer.parseInt(input[1]);

map = new int[N][N];

// 택배 정보(위치)
for (int i = 0; i < M; i++) {
	input = br.readLine().split(" ");
	int k = Integer.parseInt(input[0]); // 택배 번호 1 6
	int h = Integer.parseInt(input[1]); // 세로 크기 2 2
	int w = Integer.parseInt(input[2]); // 가로 크기 1 2
	int c = Integer.parseInt(input[3]) - 1; // 좌측 좌표(열) 2 0

	int dropRow = 0;
	// 떨어질 위치 찾기
	for (int x = 0; x <= N - h; x++) {
		boolean canPlace = true;
		for (int t = 0; t < h; t++) {
			for (int j = 0; j < w; j++) {
				if (map[x + t][c + j] != 0) {
					canPlace = false;
					break;
				}
			}

			if (!canPlace)
				break;
		}
		if (canPlace) {
			dropRow = x;
		} else {
			break;
		}
	}

	for (int x = dropRow; x < dropRow + h; x++) {
		for (int y = c; y < c + w; y++) {
			map[x][y] = k;
		}
	}
}

택배 중 가장 작은 k를 빼내기 위해 오름차순으로 정렬

static class Package implements Comparable<Package> {
	
    int k;

	Package(int k) {
		this.k = k;
	}

	@Override
	public int compareTo(Package o) {
		return this.k - o.k; // k가 작은 순으로
	}
}

outer 썼으면 좀더 코드를 줄일 수 있을 지도

outer: 
for (int x = 0; x <= N - h; x++) {
	for (int t = 0; t < h; t++) {
		for (int j = 0; j < w; j++) {
			if (map[x + t][c + j] != 0) {
				break outer;
			}
		}
	}
	dropRow = x;
}

2. 좌측으로 택배를 제거

좌측으로 제거 가능한 k를 pq에 넣고, k가 제일 작은 순으로 정렬한다.
중복인 k를 넣지 않기 위해 Set을 활용해 방문 처리
pq가 비어있지 않다면, 가장 작은 k를 제거한다.

// 좌측으로 택배 제거
static boolean removeLeft() {

	PriorityQueue<Package> pq = new PriorityQueue<>();
	Set<Integer> visited = new HashSet<>();
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			int k = map[i][j];

			if (k != 0 && !visited.contains(k)) {
				visited.add(k);

				if (checkLeft(k)) {
					pq.offer(new Package(k));
				}
			}
		}
	}

	// 제거할 k 선택
	if (!pq.isEmpty()) {
		Package p = pq.poll();
		remove(p.k);
		System.out.println(p.k);
		return true;
	}

	return false;
}

왼쪽이 모두 0이어서 제거할 수 있는 지 체크하는 함수
- map[i][j]가 k인 (i, j) 에서 왼쪽인 (0 ~ j - 1) 까지 모두 0인지 확인

// 왼쪽이 모두 0인지
static boolean checkLeft(int k) {

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (map[i][j] == k) {
				for (int t = j - 1; t >= 0; t--) {
					if (map[i][t] != 0 && map[i][t] != k) {
						return false;
					}
				}
			}
		}
	}

	return true;
}

택배 제거 함수
- k 를 모두 0으로 변경하면 제거 완료

static void remove(int k) {

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (map[i][j] == k) {
				map[i][j] = 0;
			}
		}
	}
}

3. 택배를 아래로 내리기

이동 가능한 k들을 모아서 한번에 동시에 1칸 이동시킨다. 한칸씩 이동시키다가 더이상 이동시킬 k가 없으면 멈춘다.

groups에 k별로 좌표를 추가한다.
이동 가능한 k들을 canMoveList에 넣는다.

static void down() {

		while (true) {

			// k별 좌표 수집
			Map<Integer, List<int[]>> groups = new HashMap<>();

			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					if (map[i][j] != 0) {
						int k = map[i][j];

						if (!groups.containsKey(k)) {
							groups.put(k, new ArrayList<int[]>());
						}

						groups.get(k).add(new int[] { i, j });
					}
				}
			}

			boolean moved = false;

			// 이번 턴에 이동 가능한 k들
			List<Integer> canMoveList = new ArrayList<>();

			for (int k : groups.keySet()) {
				List<int[]> cells = groups.get(k);

				boolean canMove = true;

				for (int[] c : cells) {
					int x = c[0];
					int y = c[1];

					if (x + 1 >= N) {
						canMove = false;
						break;
					}

					if (map[x + 1][y] != 0 && map[x + 1][y] != k) {
						canMove = false;
						break;
					}
				}

				if (canMove) {
					canMoveList.add(k);
				}
			}

			if (canMoveList.isEmpty())
				break;

			// 실제 이동
			for (int k : canMoveList) {
				for (int[] c : groups.get(k)) {
					map[c[0]][c[1]] = 0;
				}
			}

			for (int k : canMoveList) {
				for (int[] c : groups.get(k)) {
					map[c[0] + 1][c[1]] = k;
				}
			}

			moved = true;

			if (!moved)
				break;
		}
	}

틀렸던 코드

한칸씩 이동 안하고 k별로 한번에 내려갈 수 있는 만큼 확인하고 내렸더니 둘다 이동해야하는 상황에서 이동이 불가능했다.

static void down(){
		
		Map<Integer, List<int[]>> groups = new HashMap<>();
		// k별로 좌표를 map에 추가
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (map[i][j] != 0) {
					// 어떤 k를 만남
					int k = map[i][j];
					if (!groups.containsKey(k)) {
						groups.put(k, new ArrayList<int[]>());
					}
					groups.get(k).add(new int[] { i, j });
				}
			}
		}
		// k별로 처리
		Map<Integer, Integer> hash = new HashMap<Integer, Integer>();
		for (int k : groups.keySet()) {
			List<int[]> cells = groups.get(k);
			int drop = 0; // 한칸 씩 검사
			while (true) {
				boolean canMove = true;
				for (int i = 0; i < cells.size(); i++) {
					int x = cells.get(i)[0];
					int y = cells.get(i)[1];
					int nx = x + drop + 1;
					if (nx >= N) {
						canMove = false;
						break;
					}
					// 자기 자신은 제외
					if (map[nx][y] != 0 && map[nx][y] != k) {
						canMove = false;
						break;
					}
				}
				if (canMove) {
					drop++;
				} else {
					break;
				}
			}
			if (drop == 0)
				continue;
			// 기존 위치 제거및 아래로 이동
			for (int i = 0; i < cells.size(); i++) {
				int x = cells.get(i)[0];
				int y = cells.get(i)[1];
				map[x][y] = 0;
			}
			for (int i = 0; i < cells.size(); i++) {
				int x = cells.get(i)[0];
				int y = cells.get(i)[1];
				map[x + drop][y] = k;
			}
		}
	}

4. 실행

위 함수 모두 실행하고 더이상 제거할 택배가 없으면 멈춤

while (true) {

	// 2. 좌측으로 택배 제거
	boolean left = removeLeft();
	down();

	// 4. 우측으로 택배 제거
	boolean right = removeRight();
	down();

	if (!left && !right)
		break;
}

전체 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

	static class Package implements Comparable<Package> {
		int k;

		Package(int k) {

			this.k = k;
		}

		@Override
		public int compareTo(Package o) {
			return this.k - o.k; // k가 작은 순으로
		}

	}

	static int N, M;
	static int[][] map;
	static int[] dx = { -1, 0, 1, 0 };
	static int[] dy = { 0, 1, 0, -1 };

	public static void main(String[] args) throws Exception {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] input;

		// N, M
		input = br.readLine().split(" ");
		N = Integer.parseInt(input[0]);
		M = Integer.parseInt(input[1]);

		map = new int[N][N];

		// 택배 정보(위치)
		for (int i = 0; i < M; i++) {
			input = br.readLine().split(" ");
			int k = Integer.parseInt(input[0]); // 택배 번호 1 6
			int h = Integer.parseInt(input[1]); // 세로 크기 2 2
			int w = Integer.parseInt(input[2]); // 가로 크기 1 2
			int c = Integer.parseInt(input[3]) - 1; // 좌측 좌표(열) 2 0

			int dropRow = 0;
			// 떨어질 위치 찾기
			for (int x = 0; x <= N - h; x++) {
				boolean canPlace = true;
				for (int t = 0; t < h; t++) {
					for (int j = 0; j < w; j++) {
						if (map[x + t][c + j] != 0) {
							canPlace = false;
							break;
						}
					}

					if (!canPlace)
						break;
				}
				if (canPlace) {
					dropRow = x;
				} else {
					break;
				}
			}

			for (int x = dropRow; x < dropRow + h; x++) {
				for (int y = c; y < c + w; y++) {
					map[x][y] = k;
				}
			}

		}

		while (true) {

			// 2. 좌측으로 택배 제거
			boolean left = removeLeft();
			down();

			// 4. 우측으로 택배 제거
			boolean right = removeRight();
			down();

			if (!left && !right)
				break;
		}

	}

	static boolean check() {

		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (map[i][j] != 0) {
					return false;
				}
			}
		}

		return true;
	}

	static void down() {

		while (true) {

			// k별 좌표 수집
			Map<Integer, List<int[]>> groups = new HashMap<>();

			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					if (map[i][j] != 0) {
						int k = map[i][j];

						if (!groups.containsKey(k)) {
							groups.put(k, new ArrayList<int[]>());
						}

						groups.get(k).add(new int[] { i, j });
					}
				}
			}

			boolean moved = false;

			// 이번 턴에 이동 가능한 k들
			List<Integer> canMoveList = new ArrayList<>();

			for (int k : groups.keySet()) {
				List<int[]> cells = groups.get(k);

				boolean canMove = true;

				for (int[] c : cells) {
					int x = c[0];
					int y = c[1];

					if (x + 1 >= N) {
						canMove = false;
						break;
					}

					if (map[x + 1][y] != 0 && map[x + 1][y] != k) {
						canMove = false;
						break;
					}
				}

				if (canMove) {
					canMoveList.add(k);
				}
			}

			if (canMoveList.isEmpty())
				break;

			// 실제 이동
			for (int k : canMoveList) {
				for (int[] c : groups.get(k)) {
					map[c[0]][c[1]] = 0;
				}
			}

			for (int k : canMoveList) {
				for (int[] c : groups.get(k)) {
					map[c[0] + 1][c[1]] = k;
				}
			}

			moved = true;

			if (!moved)
				break;
		}
	}

	static boolean removeLeft() {

		PriorityQueue<Package> pq = new PriorityQueue<>();
		Set<Integer> visited = new HashSet<>();
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				int k = map[i][j];

				if (k != 0 && !visited.contains(k)) {
					visited.add(k);

					if (checkLeft(k)) {
						pq.offer(new Package(k));
					}
				}
			}
		}

		// 제거할 k 선택
		if (!pq.isEmpty()) {
			Package p = pq.poll();
			remove(p.k);
			System.out.println(p.k);
			return true;
		}

		return false;

	}

	static boolean removeRight() {

		PriorityQueue<Package> pq = new PriorityQueue<>();
		Set<Integer> visited = new HashSet<>();

		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				int k = map[i][j];

				if (k != 0 && !visited.contains(k)) {
					visited.add(k);

					if (checkRight(k)) {
						pq.offer(new Package(k));
					}
				}
			}
		}

		// 제거할 k 선택
		if (!pq.isEmpty()) {
			Package p = pq.poll();
			remove(p.k);
			System.out.println(p.k);
			return true;
		}

		return false;

	}

	static boolean checkRight(int k) {

		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N - 1; j++) {
				if (map[i][j] == k) {
					for (int t = j + 1; t < N; t++) {
						if (map[i][t] != 0 && map[i][t] != k) {
							return false;
						}
					}
				}
			}
		}

		return true;
	}

	static boolean checkLeft(int k) {

		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (map[i][j] == k) {
					for (int t = j - 1; t >= 0; t--) {
						if (map[i][t] != 0 && map[i][t] != k) {
							return false;
						}
					}
				}
			}
		}

		return true;
	}

	static void remove(int k) {

		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (map[i][j] == k) {
					map[i][j] = 0;
				}
			}
		}

	}

}

저작자표시 비영리 변경금지 (새창열림)

'알고리즘' 카테고리의 다른 글

[코드트리 - L12] 25년 상반기 오전 1번 민트초코우유 (1)	2026.04.08
[코드트리 - L13] 25년 하반기 오후 1번 AI 로봇청소기 (0)	2026.04.07
[알고리즘] 시간 복잡도 & 공간 복잡도 (0)	2026.04.05
[백준 - G3] 20058. 마법사 상어와 파이어스톰 (5)	2026.03.28
[MySQL] 자주 쓰이는 함수 정리 (0)	2026.03.27

문제 풀이

코드 풀이

1. 입력 및 M 개의 택배 위치 2차원 배열 map에 표시

2. 좌측으로 택배를 제거

3. 택배를 아래로 내리기

4. 실행

전체 코드

'알고리즘' 카테고리의 다른 글

티스토리툴바