Java/코딩테스트
백준 20058, 프로그래머스 - 섬 연결하기, 보석쇼핑
Bubbles
2023. 7. 12. 08:30
https://www.acmicpc.net/problem/20058
20058번: 마법사 상어와 파이어스톰
마법사 상어는 파이어볼과 토네이도를 조합해 파이어스톰을 시전할 수 있다. 오늘은 파이어스톰을 크기가 2N × 2N인 격자로 나누어진 얼음판에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c
www.acmicpc.net
* 삼성 기출문제 (시뮬레이션, 구현, 탐색)
1. 단계를 입력받고 칸을 나눈다. 참고로 이때 바로 원본배열에 적용하면 안된다. (동시에 녹이고 반영해야하므로)
2. 각 격자를 회전시키는 함수 수행
3. 얼음 녹이기 (모든 얼음은 동시에 녹아야 한다!!!! 꼭 기억할 것!)
4. 다 끝나면 덩어리 출력
이런 문제의 경우 미리 각 움직임을 dirX, dirY 배열에 정의해두면 편하다.
! 배열을 회전하는 함수도 종종 문제에서 출제되므로 이번 기회에 외워두기
! 얼음 한번에 녹는다는 것을 꼭 기억. 바로 원본배열 건드리면 안된다. 삼성기출에서 이런 유형이 자주 나온다.
public class p20058 {
public static int[][] graph;
public static int[] step;
public static int[] dirX = { 0, 1, 0, -1 };
public static int[] dirY = { -1, 0, 1, 0 };
public static int size, answerIce, answerSize;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int q = Integer.parseInt(st.nextToken());
size = (int) Math.pow(2, n);
graph = new int[size][size];
for (int i = 0; i < size; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < size; j++) {
graph[i][j] = Integer.parseInt(st.nextToken());
}
}
step = new int[q];
st = new StringTokenizer(br.readLine());
for (int i = 0; i < q; i++) {
step[i] = Integer.parseInt(st.nextToken());
}
for (int i = 0; i < q; i++) {
graph = divide(step[i]); // 단계에 맞게 칸 나누고 회전 시키기
graph = melt(); // 녹인 결과 저장
}
answerIce = answerSize = 0;
find();
System.out.println(answerIce);
System.out.println(answerSize);
}
public static int[][] divide(int steps) {
int[][] temp = new int[size][size];
steps = (int) Math.pow(2, steps);
for (int i = 0; i < size; i += steps) {
for (int j = 0; j < size; j += steps) {
rotateRight(i, j, steps, temp);
}
}
return temp;
}
public static void rotateRight(int x, int y, int size, int[][] temp) {
for (int i = 0; i < size; i++) {
for (int j = 0; j < size; j++) {
temp[x+i][y+j] = graph[x+size-1-j][y+i];
}
}
}
public static int[][] melt() {
int[][] temp = new int[size][size];
for (int i = 0; i < size; i++) {
temp[i] = Arrays.copyOf(graph[i], size);
}
for (int i = 0; i < size; i++) {
for (int j = 0; j < size; j++) {
int count = 0;
if (graph[i][j] == 0) {
continue;
}
for (int k = 0; k < 4; k++) {
int nextX = i + dirX[k];
int nextY = j + dirY[k];
if (nextX >= 0 && nextX < size && nextY >= 0 && nextY < size && graph[nextX][nextY] > 0) {
count++;
} // 현 좌표에서 4방향 탐색. 유효 범위내 좌표이고, 얼음이 있다면 count 증가
}
if (count < 3) {
temp[i][j]--;
}
}
}
return temp;
}
public static void find() {
Queue<Pos> queue = new LinkedList<>();
boolean[][] visited = new boolean[size][size];
for (int i = 0; i < size; i++) {
for (int j = 0; j < size; j++) {
answerIce += graph[i][j]; // 모든 칸의 얼음 다 더한값이 answerIce
if (graph[i][j] > 0 && !visited[i][j]) {
queue.offer(new Pos(i, j));
visited[i][j] = true;
int count = 1;
while (!queue.isEmpty()) {
Pos pos = queue.poll();
for (int k = 0; k < 4; k++) {
int nextX = pos.x + dirX[k];
int nextY = pos.y + dirY[k];
if (nextX >= 0 && nextX < size && nextY >= 0 && nextY < size && graph[nextX][nextY] > 0 && !visited[nextX][nextY]) {
queue.offer(new Pos(nextX, nextY));
visited[nextX][nextY] = true;
count++;
}
}
}
answerSize = Math.max(answerSize, count); // 가장 큰 얼음 칸 개수
}
}
}
}
static class Pos {
int x;
int y;
public Pos(int x, int y) {
this.x = x;
this.y = y;
}
}
}
https://school.programmers.co.kr/learn/courses/30/lessons/42861
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
* Greedy 알고리즘
* 우선순위큐에 넣어서 자동으로 에지 값 순서로 정렬시키고(에지 가중치 작은 순 정렬) 하나씩 꺼내면서 다리를 놓는다. 다리를 놓을 수 있는 최대 개수는 노드-1이므로 edgeCount값을 n-1로 지정해놓은 것. (노드-1인 경우는 일직선으로 쭉 연결된 경우)
import java.util.*;
public class 섬연결하기 {
class Solution {
public int[] union;
public int solution(int n, int[][] costs) {
PriorityQueue<Edge> queue = new PriorityQueue<>();
union = new int[n];
int edgeCount = n-1;
int answer = 0;
for (int i = 0; i < n; i++) {
union[i] = i;
}
for (int i = 0; i < costs.length; i++) {
queue.add(new Edge(costs[i][0], costs[i][1], costs[i][2]));
}
while (edgeCount > 0) {
Edge e = queue.poll();
int a = findNode(e.start);
int b = findNode(e.end);
if (a != b) {
unionNode(a, b);
answer += e.weight;
edgeCount--;
}
}
return answer;
}
public void unionNode(int a, int b) {
int findA = findNode(a);
int findB = findNode(b);
if (findA != findB) {
union[findB] = findA;
}
}
public int findNode (int n) {
if (union[n] == n) {
return n;
} else {
return union[n] = findNode(union[n]);
}
}
public class Edge implements Comparable<Edge> {
int start;
int end;
int weight;
public Edge (int s, int e, int w) {
this.start = s;
this.end = e;
this.weight = w;
}
public int compareTo(Edge e) {
return this.weight < e.weight ? -1 : 1;
}
}
}
}
https://school.programmers.co.kr/learn/courses/30/lessons/67258
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
* two-pointer 알고리즘 문제
* Set, Map 에 대해 알고 있을 것.
중복 없이 각 값만 저장하고, 순서는 중요하지 않으므로 Set 사용.
각 보석별 개수는 Map에 저장. (보석종류, 개수)의 형태로 저장한다.
import java.util.*;
public class 보석쇼핑 {
class Solution {
public int[] solution(String[] gems) {
int start = 0;
int end = 0;
int startAnswer = 0;
int endAnswer = gems.length-1;
// 보석 종류를 먼저 저장해두기, 종류 그 자체를 저장하므로 HashSet
Set<String> gemType = new HashSet<>(Arrays.asList(gems));
Map<String, Integer> tempGem = new HashMap<>();
tempGem.put(gems[start], 1);
while (start < gems.length) {
if (tempGem.keySet().size() == gemType.size()) { // 현재 모든 보석이 다 들어있다면
if (end - start < endAnswer - startAnswer) {
startAnswer = start;
endAnswer = end;
} // 현재 거리가 더 짧다면 startAnswer, endAnswer 갱신
// 시작점 옮겨주고 시작점 보석을 줄임
tempGem.put(gems[start], tempGem.get(gems[start]) - 1);
// 0개라면 해당 보석 종류 제거
if (tempGem.get(gems[start]) == 0) {
tempGem.remove(gems[start]);
}
start++;
}
else if (end < gems.length - 1) { // 그게 아니라면 end를 뒤로 보내서 한 칸씩 늘린다
end++;
if (tempGem.get(gems[end]) == null) {
tempGem.put(gems[end], 1);
}
else {
tempGem.put(gems[end], tempGem.get(gems[end]) + 1);
}
}
else {
break;
}
}
return new int[] { startAnswer + 1, endAnswer+1 };
}
}
}