Skip to content

Commit 41f9cee

Browse files
GoogleokGoogleok
committed
28주차 알고리즘 완료
1 parent 1844e3b commit 41f9cee

3 files changed

Lines changed: 275 additions & 0 deletions

File tree

‎src/programmers/level2/week_28/Solution001.java‎

Lines changed: 100 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,100 @@
1+
package programmers.level2.week_28;
2+
3+
import java.util.Arrays;
4+
5+
/**
6+
* 거리두기 확인하기
7+
* https://programmers.co.kr/learn/courses/30/lessons/81302?language=java
8+
*/
9+
public class Solution001 {
10+
public static void main(String[] args) {
11+
String[][] places = {{"POOOP", "OXXOX", "OPXPX", "OOXOX", "POXXP"}, {"POOPX", "OXPXP", "PXXXO", "OXXXO", "OOOPP"}, {"PXOPX", "OXOXP", "OXPOX", "OXXOP", "PXPOX"}, {"OOOXX", "XOOOX", "OOOXX", "OXOOX", "OOOOO"}, {"PXPXP", "XPXPX", "PXPXP", "XPXPX", "PXPXP"}, {"OOPOO", "OPOOO", "OOOOO", "OOOOO", "OOOOO"}};
12+
Solution001 sol = new Solution001();
13+
System.out.println(Arrays.toString(sol.solution(places)));
14+
}
15+
16+
public int[] solution(String[][] places) {
17+
int[] answer = new int[places.length];
18+
int cnt = 0;
19+
boolean isPass;
20+
for (int i = 0; i < places.length; i++) {
21+
isPass = true;
22+
for (int j = 0; j < places[i].length; j++) {
23+
for (int k = 0; k < places[i][j].length(); k++) {
24+
if (places[i][j].charAt(k) == 'P') {
25+
// 상
26+
if (j > 0 && places[i][j - 1].charAt(k) == 'P') {
27+
isPass = false;
28+
break;
29+
}
30+
// 하
31+
if (j < 4 && places[i][j + 1].charAt(k) == 'P') {
32+
isPass = false;
33+
break;
34+
}
35+
// 좌
36+
if (k > 0 && places[i][j].charAt(k - 1) == 'P') {
37+
isPass = false;
38+
break;
39+
}
40+
// 우
41+
if (k < 4 && places[i][j].charAt(k + 1) == 'P') {
42+
isPass = false;
43+
break;
44+
}
45+
// 상 두칸
46+
if (j > 1 && places[i][j - 2].charAt(k) == 'P' && places[i][j - 1].charAt(k) != 'X') {
47+
isPass = false;
48+
break;
49+
}
50+
// 하 두칸
51+
if (j < 3 && places[i][j + 2].charAt(k) == 'P' && places[i][j + 1].charAt(k) != 'X') {
52+
isPass = false;
53+
break;
54+
}
55+
// 좌 두칸
56+
if (k > 1 && places[i][j].charAt(k - 2) == 'P' && places[i][j].charAt(k - 1) != 'X') {
57+
isPass = false;
58+
break;
59+
}
60+
// 우 두칸
61+
if (k < 3 && places[i][j].charAt(k + 2) == 'P' && places[i][j].charAt(k + 1) != 'X') {
62+
isPass = false;
63+
break;
64+
}
65+
// 왼쪽 위
66+
if (j > 0 && k > 0 && places[i][j - 1].charAt(k - 1) == 'P' && (places[i][j].charAt(k - 1) != 'X' || places[i][j - 1].charAt(k) != 'X')) {
67+
isPass = false;
68+
break;
69+
}
70+
// 오른쪽 위
71+
if (j > 0 && k < 4 && places[i][j - 1].charAt(k + 1) == 'P' && (places[i][j].charAt(k + 1) != 'X' || places[i][j - 1].charAt(k) != 'X')) {
72+
isPass = false;
73+
break;
74+
}
75+
// 왼쪽 아래
76+
if (j < 4 && k > 0 && places[i][j + 1].charAt(k - 1) == 'P' && (places[i][j].charAt(k - 1) != 'X' || places[i][j + 1].charAt(k) != 'X')) {
77+
isPass = false;
78+
break;
79+
}
80+
// 오른쪽 아래
81+
if (j < 4 && k < 4 && places[i][j + 1].charAt(k + 1) == 'P' && (places[i][j].charAt(k + 1) != 'X' || places[i][j + 1].charAt(k) != 'X')) {
82+
isPass = false;
83+
break;
84+
}
85+
}
86+
}
87+
88+
if (!isPass) {
89+
break;
90+
}
91+
}
92+
93+
answer[i] = isPass ? 1 : 0;
94+
}
95+
96+
return answer;
97+
}
98+
99+
100+
}

‎src/programmers/level2/week_28/Solution002.java‎

Lines changed: 77 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,77 @@
1+
package programmers.level2.week_28;
2+
3+
4+
import java.util.*;
5+
6+
/**
7+
* 순위검색
8+
* https://programmers.co.kr/learn/courses/30/lessons/72412?language=java
9+
*/
10+
public class Solution002 {
11+
static Map<String, ArrayList<Integer>> map;
12+
13+
public static void main(String[] args) {
14+
String[] info = {"java backend junior pizza 150", "python frontend senior chicken 210", "python frontend senior chicken 150", "cpp backend senior pizza 260", "java backend junior chicken 80", "python backend senior chicken 50"};
15+
String[] query = {"java and backend and junior and pizza 100", "python and frontend and senior and chicken 200", "cpp and - and senior and pizza 250", "- and backend and senior and - 150", "- and - and - and chicken 100", "- and - and - and - 150"};
16+
17+
Solution002 sol = new Solution002();
18+
System.out.println(Arrays.toString(sol.solution(info, query)));
19+
}
20+
21+
// 조합
22+
static void comb(String str, int depth, String[] info) {
23+
if (depth == 4) {
24+
int score = Integer.parseInt(info[4]);
25+
if (map.containsKey(str)) {
26+
map.get(str).add(score);
27+
} else {
28+
ArrayList<Integer> tmp = new ArrayList<>();
29+
tmp.add(score);
30+
map.put(str, tmp);
31+
}
32+
return;
33+
}
34+
comb(str + "-", depth + 1, info);
35+
comb(str + info[depth], depth + 1, info);
36+
}
37+
38+
static int binarySearch(String query, int score) {
39+
if (!map.containsKey(query)) return 0;
40+
List<Integer> scoreList = map.get(query);
41+
int start = 0, end = scoreList.size() - 1;
42+
43+
while (start <= end) {
44+
int mid = (start + end) / 2;
45+
if (score > scoreList.get(mid)) start = mid + 1;
46+
else end = mid - 1;
47+
}
48+
return scoreList.size() - start;
49+
}
50+
51+
public int[] solution(String[] info, String[] query) {
52+
int[] answer = new int[query.length];
53+
map = new HashMap<>();
54+
55+
for (String in : info) {
56+
comb("", 0, in.split(" "));
57+
}
58+
59+
// 2. map에 저장된 점수 list 오름차순으로 정렬
60+
List<String> keys = new ArrayList<>(map.keySet());
61+
for (String key : keys) {
62+
List<Integer> scoreList = map.get(key);
63+
Collections.sort(scoreList);
64+
}
65+
66+
int queryIdx = 0;
67+
for (String q : query) {
68+
query[queryIdx] = q.replaceAll(" and ", "");
69+
String[] tmp = query[queryIdx].split(" ");
70+
answer[queryIdx++] = binarySearch(tmp[0], Integer.parseInt(tmp[1]));
71+
}
72+
73+
return answer;
74+
}
75+
76+
77+
}

‎src/programmers/level2/week_28/Solution003.java‎

Lines changed: 98 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,98 @@
1+
package programmers.level2.week_28;
2+
3+
import java.util.ArrayList;
4+
import java.util.List;
5+
6+
/**
7+
* 수식 최대화
8+
* https://programmers.co.kr/learn/courses/30/lessons/67257#qna
9+
*/
10+
public class Solution003 {
11+
public static void main(String[] args) {
12+
String expression = "100-200*300-500+20";
13+
Solution003 sol = new Solution003();
14+
System.out.println(sol.solution(expression));
15+
}
16+
17+
public long solution(String expression) {
18+
String[] longArr = expression.split("[^0-9]");
19+
List<Long> longList = new ArrayList<>();
20+
for (String l : longArr)
21+
longList.add(Long.parseLong(l));
22+
23+
String[] opsArr = expression.split("[0-9]+");
24+
List<String> opsList = new ArrayList<>();
25+
for (int i = 1; i < opsArr.length; i++) {
26+
opsList.add(opsArr[i]);
27+
}
28+
List<Long> longTemp;
29+
List<String> opsTemp;
30+
31+
long max = 0;
32+
33+
longTemp = new ArrayList<>(longList);
34+
opsTemp = new ArrayList<>(opsList);
35+
calcProc(longTemp, opsTemp, new String[]{"+", "-", "*"});
36+
max = Math.max(max, Math.abs(longTemp.get(0)));
37+
38+
longTemp = new ArrayList<>(longList);
39+
opsTemp = new ArrayList<>(opsList);
40+
calcProc(longTemp, opsTemp, new String[]{"+", "*", "-"});
41+
max = Math.max(max, Math.abs(longTemp.get(0)));
42+
43+
longTemp = new ArrayList<>(longList);
44+
opsTemp = new ArrayList<>(opsList);
45+
calcProc(longTemp, opsTemp, new String[]{"-", "+", "*"});
46+
max = Math.max(max, Math.abs(longTemp.get(0)));
47+
48+
longTemp = new ArrayList<>(longList);
49+
opsTemp = new ArrayList<>(opsList);
50+
calcProc(longTemp, opsTemp, new String[]{"-", "*", "+"});
51+
max = Math.max(max, Math.abs(longTemp.get(0)));
52+
53+
longTemp = new ArrayList<>(longList);
54+
opsTemp = new ArrayList<>(opsList);
55+
calcProc(longTemp, opsTemp, new String[]{"*", "-", "+"});
56+
max = Math.max(max, Math.abs(longTemp.get(0)));
57+
58+
longTemp = new ArrayList<>(longList);
59+
opsTemp = new ArrayList<>(opsList);
60+
calcProc(longTemp, opsTemp, new String[]{"*", "+", "-"});
61+
max = Math.max(max, Math.abs(longTemp.get(0)));
62+
63+
return max;
64+
}
65+
66+
public void calcProc(List<Long> longLi, List<String> opsLi, String[] ops) {
67+
calc(longLi, opsLi, ops[0]);
68+
calc(longLi, opsLi, ops[1]);
69+
calc(longLi, opsLi, ops[2]);
70+
}
71+
72+
public void calc(List<Long> longLi, List<String> opsLi, String ops) {
73+
int i = 0;
74+
int length = opsLi.size();
75+
76+
while (i < length) {
77+
if (ops.equals(opsLi.get(i))) {
78+
switch (ops) {
79+
case "+":
80+
longLi.set(i, longLi.get(i) + longLi.get(i + 1));
81+
break;
82+
case "-":
83+
longLi.set(i, longLi.get(i) - longLi.get(i + 1));
84+
break;
85+
case "*":
86+
longLi.set(i, longLi.get(i) * longLi.get(i + 1));
87+
break;
88+
}
89+
longLi.remove(i + 1);
90+
opsLi.remove(i);
91+
i--;
92+
length--;
93+
}
94+
i++;
95+
}
96+
}
97+
98+
}

0 commit comments

Comments
 (0)