공부 기록

뭔가 문제가 삼성느낌이 난다...

문제 풀이 코드는 아래와 같다. 코드가 넘 긴 느낌이 있긴 하지만... 시키는 대로만 하면 풀 수 있다

import java.util.*;

public class Main {
	private static int STAND = 0;
	private static int FALL = 1;

	private static int[][] before;

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);

		int R = in.nextInt();
		int C = in.nextInt();
		int round = in.nextInt();

		int mat[][] = new int[R][C];
		for (int i = 0; i < R; i++) {
			for (int j = 0; j < C; j++) {
				mat[i][j] = in.nextInt();
			}
		}

		before = new int[R][C]; // 0: 서 있음, 1: 넘어짐
		int score = 0;
		for (int r = 0; r < round; r++) {
			int attackR = in.nextInt() - 1;
			int attackC = in.nextInt() - 1;
			Direction direction = Direction.valueOf(in.next());

			int defendR = in.nextInt() - 1;
			int defendC = in.nextInt() - 1;
			score += turn(mat, attackR, attackC, direction, defendR, defendC, R, C);
		}

		System.out.println(score);
		print(before);
	}

	private static int turn(int mat[][], int attackR, int attackC, Direction direction, int defendR, int defendC,
			int maxRow, int maxCol) {
		int[][] after = clone(before, maxRow, maxCol);
		attack(mat, after, attackR, attackC, direction, maxRow, maxCol);
		int score = calculateScore(after, maxRow, maxCol);
		defend(after, defendR, defendC);

		before = after;
		return score;
	}

	private static void attack(int mat[][], int[][] after, int attackR, int attackC, Direction direction, int maxRow,
			int maxCol) {
		if (after[attackR][attackC] == FALL) {
			return;
		}

		after[attackR][attackC] = FALL;
		for (int i = 1; i < mat[attackR][attackC]; i++) {
			int newRow = attackR + direction.row * i;
			int newCol = attackC + direction.col * i;
			// System.out.println(newRow + " " + newCol + " " + direction.toString());
			if (isBoundary(newRow, newCol, maxRow, maxCol) && after[newRow][newCol] == STAND) {
				attack(mat, after, newRow, newCol, direction, maxRow, maxCol);
			}
		}
	}

	private static boolean isBoundary(int row, int col, int maxRow, int maxCol) {
		if (row < 0) {
			return false;
		}
		if (col < 0) {
			return false;
		}
		if (row >= maxRow) {
			return false;
		}
		if (col >= maxCol) {
			return false;
		}
		return true;
	}

	private static void defend(int[][] after, int defendR, int defendC) {
		after[defendR][defendC] = STAND;
	}

	private static int calculateScore(int after[][], int row, int col) {
		int sum = 0;

		for (int i = 0; i < row; i++) {
			for (int j = 0; j < col; j++) {
				if (before[i][j] == STAND && after[i][j] == FALL) {
					sum++;
				}
			}
		}
		return sum;
	}

	private static int[][] clone(int mat[][], int row, int col) {
		int newMat[][] = new int[row][col];

		for (int i = 0; i < row; i++) {
			for (int j = 0; j < col; j++) {
				newMat[i][j] = mat[i][j];
			}
		}

		return newMat;
	}

	private static void print(int mat[][]) {
		int row = mat.length;
		int col = mat[0].length;

		for (int i = 0; i < row; i++) {
			for (int j = 0; j < col; j++) {
				if (mat[i][j] == STAND) {
					System.out.print("S ");
				} else {
					System.out.print("F ");
				}
			}
			System.out.println();
		}
	}
}

enum Direction {
	N(-1, 0), W(0, -1), E(0, 1), S(1, 0);

	int row;
	int col;

	Direction(int row, int col) {
		this.row = row;
		this.col = col;
	}

	public String toString() {
		return this.name() + "(" + this.row + ", " + this.col + ")";
	}
}

설치 조건

• 기둥
  • 바닥 위에 있거나 (y=0)
  • 보의 한쪽 끝 부분 위에 있거나 다른 기둥 위에 있어야 한다 (아래와 이어져있다)
• 보
  • 한쪽 끝 부분이 기둥 위에 있거나 또는 양쪽 끝 부분이 다른 보와 동시에 연결되어 있어야 한다. (왼쪽이나 오른쪽과 이어져있다)
• 기둥과 보는 길이가 1인 선분으로 표현된다.

예시

1. (1, 0)에서 위쪽으로 기둥을 하나 설치 후, (1, 1)에서 오른쪽으로 보를 하나 만듭니다.
2. (2, 1)에서 위쪽으로 기둥을 하나 설치 후, (2, 2)에서 오른쪽으로 보를 하나 만듭니다.
3. (5, 0)에서 위쪽으로 기둥을 하나 설치 후, (5, 1)에서 위쪽으로 기둥을 하나 더 설치합니다.
4. (4, 2)에서 오른쪽으로 보를 설치 후, (3, 2)에서 오른쪽으로 보를 설치합니다.

만약 (4, 2)에서 오른쪽으로 보를 먼저 설치하지 않고, (3, 2)에서 오른쪽으로 보를 설치하려 한다면 2번 규칙에 맞지 않으므로 설치가 되지 않습니다.

기둥과 보를 삭제하는 기능도 있는데 기둥과 보를 삭제한 후에 남은 기둥과 보들 또한 위 규칙을 만족해야 한다.

만약, 작업을 수행한 결과가 조건을 만족하지 않는다면 해당 작업은 무시된다.

어떻게 풀지 생각해 보다가 구조물을 추가할 수 있는지 여부를 보는 함수 addValid을 만들어 두고,

구조물을 제거할 때에는 구조물을 일단 제거한 뒤, 주위에 있는 기둥과 보를 다시 추가할 때 조건에 맞는지 여부를 addValid를 이용해서 보도록 했다.

이렇게 풀면 조건에 대해 세세하게 생각할 필요 없이 addValid 함수만 호출하면 되어서 쉽게 문제를 풀 수 있다.

import java.util.*;
class Solution {
	public static int HORIZONTAL = 1;
	public static int VERTICAL = 0;

	public static int ADD = 1;
	public static int DELETE = 0;

	public int[][] solution(int n, int[][] build_frame) {
		TreeSet<Structure> set = new TreeSet<Structure>();

		for (int i = 0; i < build_frame.length; i++) {
			int x = build_frame[i][0];
			int y = build_frame[i][1];
			boolean isVertical = build_frame[i][2] == VERTICAL ? true : false;
			boolean isAdd = build_frame[i][3] == ADD ? true : false;

			if (!isAdd) {
				removeValid(x, y, isVertical, set);
			} else {
				addValid(x, y, isVertical, set);
			}
		}

		int[][] answer = new int[set.size()][3];
		int index = 0;
		for (Structure s : set) {
			answer[index][0] = s.x;
			answer[index][1] = s.y;
			answer[index][2] = s.structure;
			index++;
		}
		return answer;
	}

	public void removeValid(int x, int y, boolean isVertical, TreeSet<Structure> set) {
		if (isVertical) { // 기둥
			if (set.contains(new Structure(x, y + 1, VERTICAL))) {
				// 제거할 기둥 위에 기둥이 있는 경우
				set.remove(new Structure(x, y, VERTICAL));
				if (!addValid(x, y + 1, true, set)) {
					set.add(new Structure(x, y, VERTICAL));
					return;
				}
			}

			if (set.contains(new Structure(x, y + 1, HORIZONTAL))) {
				// 기둥 위에 오른쪽 보가 지탱이 안되는 경우
				set.remove(new Structure(x, y, VERTICAL));
				if (!addValid(x, y + 1, false, set)) {
					set.add(new Structure(x, y, VERTICAL));
					return;
				}
			}

			if (set.contains(new Structure(x - 1, y + 1, HORIZONTAL))) {
				// 기둥 위에 왼쪽 보가 지탱이 안되는 경우
				set.remove(new Structure(x, y, VERTICAL));
				if (!addValid(x - 1, y + 1, false, set)) {
					set.add(new Structure(x, y, VERTICAL));
					return;
				}
			}

			set.remove(new Structure(x, y, VERTICAL));
			return;
		}

		// 보
		if (set.contains(new Structure(x, y, VERTICAL))) {
			// 보 위에 기둥이 있는 경우
			set.remove(new Structure(x, y, HORIZONTAL));
			if (!addValid(x, y, true, set)) {
				set.add(new Structure(x, y, HORIZONTAL));
				return;
			}
		}
		if (set.contains(new Structure(x + 1, y, VERTICAL))) {
			// 보 오른쪽 위에 기둥이 있는 경우
			set.remove(new Structure(x, y, HORIZONTAL));
			if (!addValid(x + 1, y, true, set)) {
				set.add(new Structure(x, y, HORIZONTAL));
				return;
			}
		}

		if (set.contains(new Structure(x + 1, y, HORIZONTAL))) {
			// 오른쪽 보와 연결되어있는 보에 기둥이 없는 경우
			set.remove(new Structure(x, y, HORIZONTAL));
			if (!addValid(x + 1, y, false, set)) {
				set.add(new Structure(x, y, HORIZONTAL));
				return;
			}
		}

		if (set.contains(new Structure(x - 1, y, HORIZONTAL))) {
			// 왼쪽 보와 연결되어있는 보에 기둥이 없는 경우
			set.remove(new Structure(x, y, HORIZONTAL));
			if (!addValid(x - 1, y, false, set)) {
				set.add(new Structure(x, y, HORIZONTAL));
				return;
			}
		}

		set.remove(new Structure(x, y, HORIZONTAL));
		return;
	}

	public boolean addValid(int x, int y, boolean isVertical, TreeSet<Structure> set) {
		if (isVertical) { // 기둥
			if (y == 0) {
				// 바닥 위에 있는 경우
				set.add(new Structure(x, y, VERTICAL));
				return true;
			}

			if (set.contains(new Structure(x - 1, y, HORIZONTAL)) || set.contains(new Structure(x, y, HORIZONTAL))) {
				// 보의 한쪽 끝 부분 위에 있는 경우
				set.add(new Structure(x, y, VERTICAL));
				return true;
			}

			if (set.contains(new Structure(x, y - 1, VERTICAL))) {
				// 다른 기둥 위에 있는 경우
				set.add(new Structure(x, y, VERTICAL));
				return true;
			}

			return false;
		}

		// 보
		if (set.contains(new Structure(x + 1, y, HORIZONTAL)) && set.contains(new Structure(x - 1, y, HORIZONTAL))) {
			// 양쪽 끝 부분이 다른 보와 동시에 연결
			set.add(new Structure(x, y, HORIZONTAL));
			return true;
		}
		if (set.contains(new Structure(x, y - 1, VERTICAL)) || set.contains(new Structure(x + 1, y - 1, VERTICAL))) {
			// 한쪽 끝 부분이 기둥 위에 있는 경우
			set.add(new Structure(x, y, HORIZONTAL));
			return true;
		}

		return false;
	}
}

class Structure implements Comparable<Structure> {
	int x, y;
	int structure;

	public Structure(int x, int y, int structure) {
		this.x = x;
		this.y = y;
		this.structure = structure;
	}

	@Override
	public int compareTo(Structure o) {
		if (x == o.x) {
			if (y == o.y) {
				return Integer.compare(structure, o.structure);
			}
			return Integer.compare(y, o.y);
		}
		return Integer.compare(x, o.x);
	}

	@Override
	public boolean equals(Object o) {
		if (this == o) {
			return true;
		}
		if (!(o instanceof Structure)) {
			return false;
		}
		Structure s = (Structure) o;
		return x == s.x && y == s.y && structure == s.structure;
	}

	@Override
	public int hashCode() {
		return Objects.hash(x, y, structure);
	}

	@Override
	public String toString() {
		if (structure == 1) {
			return "(" + x + ", " + y + ") 보";
		}
		return "(" + x + ", " + y + ") 기둥";
	}
}

문제 조건

회전판에 먹어야 할 1~N의 음식이 있다. 각 음식을 섭취하는데 일정 시간이 소요된다.

• 무지는 1번 음식부터 먹기 시작하며, 회전판은 번호가 증가하는 순서대로 음식을 무지 앞으로 가져다 놓는다.
• 마지막 번호의 음식을 섭취한 후에는 회전판에 의해 다시 1번 음식이 무지 앞으로 온다. => 원형 큐
• 무지는 음식 하나를 1초 동안 섭취한 후 남은 음식은 그대로 두고, 다음 음식을 섭취한다.

무지가 먹방을 시작한 지 K 초 후에 방송이 잠시 중단되었는데, 다시 방송을 이어갈 때 섭취할 음식의 번호를 구하는 문제이다.

먼저 k가 음식의 갯수보다 큰지 작은지 생각해 보아야 한다.

• k < food_times.length: (k+1) 번째 음식을 무조건 리턴
• k > food_times.length: 맨 처음 들어있는 음식의 시간만큼 사이클을 돌 수 있는 경우
  • 한 cycle을 돌 수 있는 경우: k 시간에서 사이클을 도는 시간만큼 바로 빼준다
  • 한 cycle 전에 끝나는 경우: 큐에 있는 index를 크기순으로 정렬했을 때 몇번째 위치를 리턴해야 하는지 생각해본다

음.. 글로 설명하니까 좀 어려워 보이는데,,,,

프로그래머스 질문하기에 나와있는 예시를 한 번 시뮬레이션 해 보면

food_times=[4,2,3,6,7,1,5,8] k=27 => answer = 5

food = [(0, 4), (1, 2), (2, 3), (3, 6), (4, 7), (5, 1), (6, 5), (7, 8)] 이고 가장 작은 값을 가진 1만큼의 사이클을 돈다고 하면 1*8=8 => k-8=19

food = [(0, 4), (1, 2), (2, 3), (3, 6), (4, 7), (6, 5), (7, 8)] 그 다음 가장 작은 2-1 = 1만큼의 사이클을 돌면 1*7=7 => 19-7=12

food = [(0, 4), (2, 3), (3, 6), (4, 7), (6, 5), (7, 8)] 그 다음 가장 작은 3-2 = 1만큼의 사이클을 돌면 1*6=6 => 12-6=6

food = [(0, 4), (3, 6), (4, 7), (6, 5), (7, 8)] 그 다음 가장 작은 4-3 = 1만큼의 사이클을 돌면 1*5=5 => 6-5=1

food = [(3, 6), (4, 7), (6, 5), (7, 8)] 마지막으로 사이클을 온전히 다 돌지 못하기 때문에 1+1번째 요소를 찾으면 (4,7)이고 해당 answer=5이다.

즉, 한 개의 사이클을 온전히 돌 수 있다면 그 요소는 결국 리스트에서 사라지기 때문에 위치가 영향을 주지 않고,

food_times가 가장 작은 순으로 사이클을 돌아야 하기 때문에 자료구조는 priority queue가 적합하다.

한 개의 사이클을 온전히 돌 수 없다면 맨 처음 들어왔던 food_times의 인덱스 순으로 순회한다.

아래는 그 풀이이다.

import java.util.*;
import java.util.stream.Collectors;
class Solution {
	public int solution(int[] food_times, long k) {
		int length = food_times.length;

		if (k < length) {
			return (int) (k % length) + 1;
		}

		PriorityQueue<Food> queue = new PriorityQueue<Food>();
		for (int i = 0; i < food_times.length; i++) {
			queue.add(new Food(i, food_times[i]));
		}

		long minus = 0;
		while (!queue.isEmpty()) {
			Food now = queue.peek();
			long cycle = (long) (now.left - minus) * queue.size();
			if (k - cycle >= 0) { // 한바퀴
				k -= cycle;
				minus = now.left;
				queue.poll();

			} else { // 중간에 멈춤
				k %= queue.size();
				return queue.stream().mapToInt(food -> food.index).sorted().skip(k).findFirst().getAsInt() + 1;
			}
		}

		return -1;
	}
}

class Food implements Comparable<Food> {
	int index;
	int left;

	public Food(int index, int left) {
		this.index = index;
		this.left = left;
	}

	@Override
	public int compareTo(Food o) {
		return Integer.compare(left, o.left);
	}

	@Override
	public String toString() {
		return "(" + index + ", " + left + ")";
	}
}

시뮬레이션 문제이다. 시키는대로만 구현하면 된다.

행렬이 범위만 주의하도록 하자 1 ≤ r ≤ R, 1 ≤ c ≤ C

import java.util.*;

public class Main {
	public static int dr[] = { -1, 1, 0, 0 };
	public static int dc[] = { 0, 0, 1, -1 };

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int row = in.nextInt();
		int col = in.nextInt();
		int n = in.nextInt();
		int mat[][] = new int[row + 1][col + 1];

		Shark sharks[] = new Shark[n + 1];
		for (int i = 1; i <= n; i++) {
			int r = in.nextInt();
			int c = in.nextInt();
			int s = in.nextInt();
			int d = in.nextInt();
			int z = in.nextInt();

			sharks[i] = new Shark(i, r, c, s, dr[d - 1], dc[d - 1], z);
			mat[r][c] = i;
		}

		int sum = 0;

		for (int i = 1; i <= col; i++) {
			sum += getShark(i, mat, sharks);
			moveShark(mat, sharks, row, col);
		}
		System.out.println(sum);
	}

	public static int getShark(int col, int[][] mat, Shark[] sharks) {
		for (int i = 0; i < mat.length; i++) {
			if (mat[i][col] != 0) {

				int size = sharks[mat[i][col]].size;
				sharks[mat[i][col]] = null;
				mat[i][col] = 0;

				return size;
			}
		}
		return 0;
	}

	public static void moveShark(int[][] mat, Shark[] sharks, int maxRow, int maxCol) {
		for (int i = 1; i < sharks.length; i++) {
			Shark shark = sharks[i];

			if (shark != null) {
				mat[shark.row][shark.col] = 0;
				shark.move(maxRow, maxCol, shark.speed);
			}
		}

		for (int i = 1; i < sharks.length; i++) {
			Shark shark = sharks[i];

			if (shark != null) {
				if (mat[shark.row][shark.col] == 0) {
					mat[shark.row][shark.col] = i;
				} else {
					Shark beforeShark = sharks[mat[shark.row][shark.col]];
					if (beforeShark.size > shark.size) {
						sharks[i] = null;
					} else {
						sharks[mat[shark.row][shark.col]] = null;
						mat[shark.row][shark.col] = i;
					}
				}
			}
		}
	}
}

class Shark {
	int name;
	int row;
	int col;
	int speed;
	int dr;
	int dc;
	int size;

	public Shark(int name, int row, int col, int speed, int dr, int dc, int size) {
		this.name = name;
		this.row = row;
		this.col = col;
		this.speed = speed;
		this.dr = dr;
		this.dc = dc;
		this.size = size;
	}

	public void changeDirection() {
		this.dr = -dr;
		this.dc = -dc;
	}

	public void move(int maxRow, int maxCol, int move) {
		// 상어가 이동하려고 하는 칸이 격자판의 경계를 넘는 경우에는 방향을 반대로 바꿔서 속력을 유지한채로 이동한다.
		if (move == 0) {
			return;
		}

		int newRow = row + dr * move;
		int newCol = col + dc * move;
		if (newRow > 0 && newCol > 0 && newRow <= maxRow && newCol <= maxCol) {
			row = newRow;
			col = newCol;
			return;
		}

		if (newRow <= 0) {
			row = 1;
			changeDirection();
			move(maxRow, maxCol, 1 - newRow);
			return;
		}
		if (newCol <= 0) {
			col = 1;
			changeDirection();
			move(maxRow, maxCol, 1 - newCol);
			return;
		}
		if (newRow > maxRow) {
			row = maxRow;
			changeDirection();
			move(maxRow, maxCol, newRow - maxRow);
			return;
		}
		if (newCol > maxCol) {
			col = maxCol;
			changeDirection();
			move(maxRow, maxCol, newCol - maxCol);
			return;
		}

	}
}