Skip to content

Commit c476f85

Browse files
skydreamer21skydreamer21
committed
[Week27] 4Q Solve
1517, 1941, 11559, 18808
1 parent 49aab4e commit c476f85

File tree

6 files changed

+581
-0
lines changed

6 files changed

+581
-0
lines changed

‎2022/[Week27 - Mix]/make_dir.sh.save‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1 @@
1+
mkdir df

‎2022/[Week27 - Mix]/김주현/Q11559.java‎

Lines changed: 160 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,160 @@
1+
// 11559번 Puyo Puyo (G4) [구현]
2+
/*
3+
<문제 정보>
4+
1.
5+
6+
<변수 범위>
7+
1.
8+
9+
<프로그램 진행>
10+
1.
11+
12+
<필요 함수>
13+
1.
14+
15+
*/
16+
17+
import Necessary_Class.Pos;
18+
19+
import java.io.*;
20+
import java.util.StringTokenizer;
21+
import java.util.ArrayList;
22+
import java.util.Deque;
23+
import java.util.ArrayDeque;
24+
import java.util.Arrays;
25+
26+
public class Q11559 {
27+
static int[][] map = new int[12][6];
28+
static boolean[][] visited = new boolean[12][6];
29+
30+
static final int N = 12;
31+
static final int M = 6;
32+
static final int EMPTY = '.';
33+
static final int POPPED = '*';
34+
static final int RED = 'R';
35+
static final int YELLOW = 'Y';
36+
static final int GREEN = 'G';
37+
static final int BLUE = 'B';
38+
static final int PURPLE = 'P';
39+
40+
static final int[][] DIR = {{1,0}, {0,1}, {-1,0}, {0,-1}};
41+
42+
public static void main(String args[]) throws IOException {
43+
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
44+
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
45+
StringBuilder sb = new StringBuilder();
46+
StringTokenizer st;
47+
48+
// ******************** 입력 & 초기화 ********************
49+
for (int i=0; i<N; i++) {
50+
char[] input = br.readLine().toCharArray();
51+
for (int j=0; j<M; j++) {
52+
map[i][j] = input[j];
53+
}
54+
}
55+
56+
// ******************** 메인 로직 ********************
57+
58+
int chainCount = -1;
59+
boolean popped = true;
60+
61+
// 연쇄가 일어나는 동안 반복
62+
while (popped) {
63+
chainCount++;
64+
popped = false;
65+
initVisited();
66+
67+
for (int i=0; i<N; i++) {
68+
for (int j=0; j<M; j++) {
69+
if (visited[i][j] || map[i][j] == EMPTY) continue;
70+
if (popPuyo(i, j)) {
71+
popped = true;
72+
}
73+
}
74+
}
75+
pushDown();
76+
}
77+
78+
// ******************** 정답 출력 ********************
79+
80+
sb.append(chainCount);
81+
bw.write(sb.toString());
82+
bw.flush();
83+
bw.close();
84+
br.close();
85+
}
86+
87+
/**
88+
* (x,y)에 연결되어 있는 뿌요를 터뜨리고 true 반환 만약 터뜨릴 수 없다면 false 반환
89+
* @param x
90+
* @param y
91+
* @return isPopped
92+
*/
93+
public static boolean popPuyo(int x, int y) {
94+
ArrayList<Pos> popList = search(x, y);
95+
if (popList.size() < 4) return false;
96+
97+
for (Pos pop : popList) {
98+
map[pop.x][pop.y] = POPPED;
99+
}
100+
return true;
101+
}
102+
103+
public static void pushDown() {
104+
for (int col=0; col < M; col++) {
105+
pushColumnDown(col);
106+
}
107+
}
108+
109+
public static void pushColumnDown(int col) {
110+
int idx = N-1;
111+
for (int i = N-1; i >= 0; i--) {
112+
if (map[i][col] == POPPED || map[i][col] == EMPTY) {
113+
continue;
114+
}
115+
map[idx][col] = map[i][col];
116+
idx--;
117+
}
118+
119+
while (idx >= 0) {
120+
map[idx][col] = EMPTY;
121+
idx--;
122+
}
123+
}
124+
125+
public static ArrayList<Pos> search (int x, int y) {
126+
final int COLOR = map[x][y];
127+
128+
Deque<Pos> q = new ArrayDeque<>();
129+
q.add(new Pos(x, y));
130+
visited[x][y] = true;
131+
132+
Pos now;
133+
int nextX, nextY;
134+
boolean inRange;
135+
ArrayList<Pos> popList = new ArrayList<>();
136+
popList.add(new Pos(x, y));
137+
138+
while (!q.isEmpty()) {
139+
now = q.poll();
140+
141+
for (int[] d: DIR) {
142+
nextX = now.x + d[0];
143+
nextY = now.y + d[1];
144+
inRange = nextX >= 0 && nextY >=0 && nextX < N && nextY < M;
145+
if (inRange && !visited[nextX][nextY] && map[nextX][nextY] == COLOR) {
146+
popList.add(new Pos(nextX, nextY));
147+
visited[nextX][nextY] = true;
148+
q.add(new Pos(nextX, nextY));
149+
}
150+
}
151+
}
152+
return popList;
153+
}
154+
155+
public static void initVisited () {
156+
for (int i=0; i < N; i++) {
157+
Arrays.fill(visited[i], false);
158+
}
159+
}
160+
}

‎2022/[Week27 - Mix]/김주현/Q1517.java‎

Lines changed: 94 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,94 @@
1+
// 1517번 버블 소트 (P5) [정렬]
2+
/*
3+
<문제 정보>
4+
1. N개의 수로 이루어진 수열에 대해 버블 소트를 수행할 때 swap 이 몇번 발생하는지 출력
5+
6+
<변수 범위>
7+
1. 1초 / 512MB
8+
2. 1 <= N <= 500,000
9+
3. 수열 안의 각 수의 절댓값 1,000,000,000 이하의 정수
10+
11+
<프로그램 진행>
12+
1.
13+
14+
<필요 함수>
15+
1.
16+
17+
*/
18+
19+
20+
import java.io.*;
21+
import java.util.StringTokenizer;
22+
23+
public class Q1517 {
24+
static int N;
25+
static int[] arr;
26+
static long answer = 0;
27+
28+
public static void main(String args[]) throws IOException {
29+
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
30+
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
31+
StringBuilder sb = new StringBuilder();
32+
StringTokenizer st;
33+
34+
// ******************** 입력 & 초기화 ********************
35+
N = Integer.parseInt(br.readLine());
36+
arr = new int[N];
37+
st = new StringTokenizer(br.readLine());
38+
for (int i=0; i<N; i++) {
39+
arr[i] = Integer.parseInt(st.nextToken());
40+
}
41+
42+
// ******************** 메인 로직 ********************
43+
44+
mergeSort(0, N-1);
45+
46+
// ******************** 정답 출력 ********************
47+
sb.append(answer);
48+
bw.write(sb.toString());
49+
bw.flush();
50+
bw.close();
51+
br.close();
52+
}
53+
54+
public static void mergeSort (int start, int end) {
55+
if (start == end) return;
56+
57+
int mid = (start + end) / 2;
58+
mergeSort(start, mid);
59+
mergeSort(mid+1, end);
60+
merge(start, mid, end);
61+
}
62+
63+
public static void merge(int start, int mid, int end) {
64+
int left = start;
65+
int right = mid+1;
66+
int[] temp = new int[end - start + 1];
67+
int idx = 0;
68+
69+
while (left <= mid && right <= end) {
70+
if (arr[left] <= arr[right]) {
71+
temp[idx] = arr[left];
72+
left++;
73+
}
74+
else { // arr[left] > arr[right]
75+
temp[idx] = arr[right];
76+
right++;
77+
answer += (mid - left + 1);
78+
}
79+
idx++;
80+
}
81+
82+
while (left <= mid) {
83+
temp[idx++] = arr[left];
84+
left++;
85+
}
86+
87+
while (right <= end) {
88+
temp[idx++] = arr[right];
89+
right++;
90+
}
91+
92+
System.arraycopy(temp, 0, arr, start, end - start + 1);
93+
}
94+
}

0 commit comments

Comments
 (0)