천천히 빛나는
백준 : DAY 1 (Java) 본문
본 포스팅에서는 [이차원 배열과 연산, 요세푸스 문제, 안전영역, 배열돌리기3, 신기한 소수]을 다룹니다.
17140. (골드4) 이차원 배열과 연산
import java.io.*;
import java.util.*;
public class Main {
static int r, c, k;
static int map[][];
static int time;
static int freq[];
static ArrayList<Pair> list = new ArrayList<>();
static int maxRow, maxCol;
static int tempMaxRow, tempmaxCol;
static class Pair {
int freq;
int val;
Pair(int freq, int val) {
this.freq = freq;
this.val = val;
}
}
static void makingFreq(int rOrC) {
if (rOrC == 1) {
for (int i = 0; i < maxRow; i++) {
freq = new int[101];
for (int j = 0; j < maxCol; j++) {
if(map[i][j] == 0)
continue;
freq[map[i][j]]++;
}
sortingR(i);
}
} else {
for (int j = 0; j < maxCol; j++) {
freq = new int[101];
for (int i = 0; i < maxRow; i++) {
freq[map[i][j]]++;
}
sortingC(j);
}
}
maxRow = tempMaxRow;
maxCol = tempmaxCol;
}
static void sortingR(int r) {
for (int i = 1; i <= 100; i++) {
if (freq[i] == 0)
continue;
list.add(new Pair(freq[i], i));
}
Collections.sort(list, (o1, o2) -> {
if (o1.freq == o2.freq) {
return Integer.compare(o1.val, o2.val);
} else {
return Integer.compare(o1.freq, o2.freq);
}
});
int sz = list.size() * 2;
if(sz > 100) {
sz = 100;
}else if (maxCol > sz) {
sz= maxCol;
}
int len = 0;
for (int j = 0; j < sz; j += 2) {
if (list.size() > j / 2) {
map[r][j] = list.get(len).val;
map[r][j + 1] = list.get(len++).freq;
} else {
map[r][j] = 0;
map[r][j + 1] = 0;
}
}
if (r == 0)
tempmaxCol = len * 2;
else
tempmaxCol = Math.max(len * 2, tempmaxCol);
list.clear();
}
static void sortingC(int c) {
for (int i = 1; i <= 100; i++) {
if (freq[i] == 0)
continue;
list.add(new Pair(freq[i], i));
}
Collections.sort(list, (o1, o2) -> {
if (o1.freq == o2.freq) {
return Integer.compare(o1.val, o2.val);
} else {
return Integer.compare(o1.freq, o2.freq);
}
});
int sz = list.size() * 2;
if(sz > 100) {
sz = 100;
}else if (maxCol > sz) {
sz= maxCol;
}
int len = 0;
for (int i = 0; i < sz; i += 2) {
if (list.size() > i / 2) {
map[i][c] = list.get(len).val;
map[i + 1][c] = list.get(len++).freq;
} else {
map[i][c] = 0;
map[i + 1][c] = 0;
}
}
if (c == 0) {
tempMaxRow = len * 2;
}
else {
tempMaxRow = Math.max(len * 2, tempMaxRow);
}
list.clear();
}
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
r = Integer.parseInt(st.nextToken());
c = Integer.parseInt(st.nextToken());
k = Integer.parseInt(st.nextToken());
map = new int[101][101];
maxRow = 3;
maxCol = 3;
tempMaxRow = 3;
tempmaxCol = 3;
for (int i = 0; i < 3; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < 3; j++) {
map[i][j] = Integer.parseInt(st.nextToken());
}
}
while (time < 101) {
if (map[r - 1][c - 1] == k)
break;
time++;
if (maxRow >= maxCol)
makingFreq(1);
else
makingFreq(2);
}
time = time > 100 ? -1 : time;
System.out.println(time);
br.close();
}
}행이 열보다 크거나 같을 경우에는 1번을 호출하고 그게 아니라면 2번을 호출하게 된다.
1번 호출의 경우 0일 경우를 제외하고 행에 있는 모든 값의 빈도수를 계산하고 freq 배열을 하나 만들게 된다. 그 후 sorting을 통해서 빈도수가 적은 순서대로 정렬을 하게 된다. 정렬을 한 후에는 map에 덮어쓰기를 한다. 여기서 최대 열 길이를 저장하는 tempmaxCol을 만들어 놓게 된다. 2번의 호출의 경우는 이게 열로 바뀌는 것 말고는 달라지는 게 없다.
hashMap을 이용해서 구현한 경우가 많았다. 숫자를 카운팅해서 HashMap에 담았다가 우선순위 큐에 옮겨담아서 정렬을 하게 된다.
Map<Integer, Integer> map = new HashMap<>(); // <number, count>
for (int i = 1; i <= yLength; i++) {
if (A[key][i] == 0) continue;
map.compute(A[key][i], (num, count) -> count == null ? 1 : count + 1);
}
map.forEach((k, v) -> pq.add(new Pair(k, v))); // 우선순위 큐에 삽입각 숫자들의 개수를 세주거나 추가해주는 방법인데 map 자료구조에 익숙하지 않아서 compute를 처음 접하게 되었다. compute()메서드는 key의 여부와 상관없이 전달받은 인자를 통하여 람다함수를 적용하고, 결과에 따라 key를 제거하거나 새로운 value를 저장한다.
A[key][i]가 key가 되고 그 뒤에 적은 람다함수를 통해 추가 또는 새로운값 저장을 한다. 모든 값을 우선순위 큐에 넣어주고 (자동 정렬) 앞에서부터 배열을 다시 만들어준다.
https://bcp0109.tistory.com/216
백준 17140번. 이차원 배열과 연산 (Java)
Problem문제 링크 문제에서 설명해주는 R 연산과 C 연산을 반복한 뒤 특정 좌표의 숫자가 k 와 일치하는 시간은 몇 초 뒤인지 구하는 문제입니다. Solution단순하게 구현하면 됩니다.R 연산과 C 연산의
bcp0109.tistory.com
HashMap<Integer, Integer> hash = new HashMap<>();
for(int j=0;j<col_len;j++) {
if(map[i][j] == 0) continue;
if(hash.containsKey(map[i][j])) {
hash.put(map[i][j], hash.get(map[i][j])+1);
} else {
hash.put(map[i][j], 1);
}
}compute 함수 없이 containsKey 함수를 사용해서 직접 구현해주신 분도 계신다. put으로 넣을 수 있는데, key 값이 중복되면 나중에 선언된 key의 value가 출력된다.
https://developer-ellen.tistory.com/130
BOJ - 이차원 배열과 연산 17140번 (JAVA)
❓ 문제 - 백준 이차원 배열과 연산 17140번 - JAVA 풀이법 출처 (https://www.acmicpc.net/problem/17140) 17140번: 이차원 배열과 연산 첫째 줄에 r, c, k가 주어진다. (1 ≤ r, c, k ≤ 100) 둘째 줄부터 3개의 줄에 배
developer-ellen.tistory.com
<HashMap>
- put(key, value);
- get(key);
- containsKey(key);
- putAll(map); // map에 다른 map을 전부 포함
https://reakwon.tistory.com/151
[Collection] 이것만 알면 해시맵(HashMap) 정복 가능 - HashMap의 특징, 사용법 예제
해시맵(HashMap) 해시맵은 이름 그대로 해싱(Hashing)된 맵(Map)입니다. 여기서 맵(Map)부터 짚고 넘어가야겠죠? 맵이라는 것은 키(Key)와 값(Value) 두 쌍으로 데이터를 보관하는 자료구조입니다. 여기서
reakwon.tistory.com
1158. (실버4) 요세푸스 문제
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int k = Integer.parseInt(st.nextToken());
ArrayDeque<Integer> dq = new ArrayDeque<>();
for(int i = 0; i < n; i++) {
dq.offer(i+1);
}
sb.append("<");
while(!dq.isEmpty()) {
if(dq.size() == 1) {
sb.append(dq.poll()).append(">");
break;
}
for(int i = 0; i < k - 1; i++) {
int temp = dq.poll();
dq.offer(temp);
}
sb.append(dq.poll()).append(", ");
}
System.out.println(sb);
}
}
계속 돌면서 제거하기 위해서 자료구조 Deque을 사용하였다. 나는 492ms가 나왔는데 200ms쯤인 자바 코드들이 많았다. 나는 ArrayList의 remove 부분이 굉장히 시간을 많이 잡아먹는다고 생각해서 다른 자료구조를 쓴건데 ArrayList에서 remove한 코드들이 더 시간은 짧았다!
K번째 사람들을 계속 제거하게 되는데 제거할 때마다 index 값이 당겨지게 때문에 K-1을 더하는 형식으로 진행하면 된다.
https://tussle.tistory.com/903
[백준] 알고리즘 분류(자료구조,JAVA)1158번, 요세푸스 문제
문제 링크 1158번: 요세푸스 문제 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000) www.acmicpc.net 주의사항 JAVA를 사용하여 프로그램을 사용하였습니다. 백준에서 코드
tussle.tistory.com
2468. (실버1) 안전 영역
import java.io.*;
import java.util.*;
public class Main {
static int N;
static int map[][];
static boolean visited[][];
static final int dx[] = { 1, 0, -1, 0 };
static final int dy[] = { 0, -1, 0, 1 };
static void noFlood(int r, int c, int limit) {
ArrayDeque<int[]> q = new ArrayDeque<>();
q.offer(new int[] { r, c });
visited[r][c] = true;
while (!q.isEmpty()) {
int[] top = q.poll();
int x = top[0];
int y = top[1];
for (int d = 0; d < 4; d++) {
int nx = x + dx[d];
int ny = y + dy[d];
if(nx < 0 || nx >= N || ny < 0 || ny >= N) continue;
if(visited[nx][ny] || map[nx][ny] < limit + 1) continue;
q.offer(new int[] {nx, ny});
visited[nx][ny] = true;
}
}
}
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
StringTokenizer st;
N = Integer.parseInt(br.readLine());
map = new int[N][N];
int maxVal = 0;
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < N; j++) {
map[i][j] = Integer.parseInt(st.nextToken());
maxVal = Math.max(maxVal, map[i][j]);
}
}
int ans = 0;
for(int l = 0; l < maxVal; l++) {
visited = new boolean[N][N];
int cnt = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if(!visited[i][j] && map[i][j] > l) {
noFlood(i, j, l);
cnt++;
}
}
}
ans = Math.max(ans, cnt);
}
System.out.println(ans);
}
}영역들을 잠기게 해서 가장 많은 개수의 connected componet를 찾는 문제였다. 나는 매번 높이를 다르게 해서 안전영역을 count 하는 bfs 코드를 작성하였지만 다른 분들 코드보다 훨씬 느리다는 것을 알게 되었다.그 이유는 dfs를 사용한 경우가 더 빨랐기 때문이다. 나는 bfs가 dfs보다 항상 빠를 것이라고 생각했는데 그게 아니었다. 그래서 검색을 해봤는데 이정도면 거의 똑같다고 보는게 맞다고 하긴한다.
16935. (골드5) 배열 돌리기 3
import java.io.*;
import java.util.*;
public class Main {
// 1. 상하 반전
// 2. 좌우 반전
// 3. 오른쪽 90도 회전
// 4. 왼쪽 90도 회전
// 5. 그룹 시계
// 6. 그룹 반시계
static StringBuilder sb;
static int N, M, R;
static int map[][];
static final int[] dx = { 0, 1, 0, -1 };
static final int[] dy = { 1, 0, -1, 0 };
static void updown() {
int temp;
for (int i = 0; i < N / 2; i++) {
for (int j = 0; j < M; j++) {
temp = map[i][j];
map[i][j] = map[N - i - 1][j];
map[N - i - 1][j] = temp;
}
}
}
static void leftright() {
int temp;
for (int j = 0; j < M / 2; j++) {
for (int i = 0; i < N; i++) {
temp = map[i][j];
map[i][j] = map[i][M - j - 1];
map[i][M - j - 1] = temp;
}
}
}
static void rRotation() {
int copy[][] = new int[N][M];
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
copy[i][j] = map[i][j];
}
}
map = new int[M][N];
for (int i = 0; i < M; i++) {
for (int j = 0; j < N; j++) {
map[i][j] = copy[N - 1 - j][i];
}
}
int temp = N;
N = M;
M = temp;
}
static void lRotation() {
int copy[][] = new int[N][M];
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
copy[i][j] = map[i][j];
}
}
map = new int[M][N];
for (int i = 0; i < M; i++) {
for (int j = 0; j < N; j++) {
map[i][j] = copy[j][M - 1 - i];
}
}
int temp = N;
N = M;
M = temp;
}
static void clockRotation() {
int copy[][] = new int[N][M];
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
copy[i][j] = map[i][j];
}
}
int d = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (i < N / 2 && j < M / 2)
d = 0;
else if (i < N / 2 && j >= M / 2)
d = 1;
else if (i >= N / 2 && j >= M / 2)
d = 2;
else
d = 3;
int nx = i + dx[d] * (N / 2);
int ny = j + dy[d] * (M / 2);
map[nx][ny] = copy[i][j];
}
}
}
static void counterclockRotation() {
int copy[][] = new int[N][M];
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
copy[i][j] = map[i][j];
}
}
int d = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (i < N / 2 && j < M / 2)
d = 1;
else if (i < N / 2 && j >= M / 2)
d = 2;
else if (i >= N / 2 && j >= M / 2)
d = 3;
else
d = 0;
int nx = i + dx[d] * (N / 2);
int ny = j + dy[d] * (M / 2);
map[nx][ny] = copy[i][j];
}
}
}
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = null;
sb = new StringBuilder();
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
R = Integer.parseInt(st.nextToken());
map = new int[N][M];
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < M; j++) {
map[i][j] = Integer.parseInt(st.nextToken());
}
}
st = new StringTokenizer(br.readLine());
for (int i = 0; i < R; i++) {
int cmd = Integer.parseInt(st.nextToken());
switch (cmd) {
case 1:
updown();
break;
case 2:
leftright();
break;
case 3:
rRotation();
break;
case 4:
lRotation();
break;
case 5:
clockRotation();
break;
case 6:
counterclockRotation();
break;
}
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
System.out.print(map[i][j] + " ");
}
System.out.println();
}
}
}5번부턴 시계 방향과 반시계 방향이 들어가는 부분이다. 4개의 구역으로 나누고 시계방향으로 돌려야 한다. 좌표값을 확인해서 어디로 가야하는지 작성해주는 코드로 작성해주었다.
2023. (골드5) 신기한 소수
import java.io.*;
import java.util.*;
public class Main {
static int prime[] = { 2, 3, 5, 7 };
static int num[];
static int N;
static StringBuilder sb = new StringBuilder();
static boolean isPrime(int num) {
for (int i = 2; i * i <= num; i++) {
if (num % i == 0)
return false;
}
return true;
}
static void surprise(int cnt, int num) {
if (cnt == N) {
sb.append(num).append("\n");
return;
}
num *= 10;
for (int i = 1; i < 10; i += 2) {
if (isPrime(num + i)) {
surprise(cnt + 1, num + i);
}
}
}
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
for (int i = 0; i < 4; i++) {
surprise(1, prime[i]);
}
System.out.println(sb);
}
}첫째자리는 항상 소수여야하며, 그 뒤에 붙는 숫자들은 2의 배수가 아니어야 한다. (%2로 나누어지기 때문에 무조건 홀수를 붙여서 검사해야 한다) 이와 같은 성질을 이용하면 시간을 72ms로 줄일 수 있다.
에라토스테네스라는 방식으로 소수를 판단할 수도 있긴한데 메모리 제한이 4MB이기 때문에 이와 같은 방식을 사용해야 한다.
'JAVA > BAEKJOON (JAVA)' 카테고리의 다른 글
| 백준 : DAY 2 (Java) (0) | 2024.04.02 |
|---|
