[ 2021.06.21 ] 하루 세 문제(3일차)
매일 3개의 주제를 골라 문제를 풀어봅시다.
- 문자열
- 정규표현식
- 자료구조
문자열
- 문제 : 문자열 폭발
- 난이도 : Gold 4
- 해설
- KMP 알고리즘으로 해결하려고 했으나 메모리초과(128MB)
- String class의
subString
함수와+
연산자의 남용으로 메모리초과가 발생한 것 같습니다. - 풀이 검색 결과
Stack
으로 풀이한 내용이 많았습니다. - 찾아낸 최적의 풀이 방법(스택 사용 X) : [백준] 9935번 문자열 폭발 (Java)
- 소스코드 : https://www.acmicpc.net/source/30207971
정규표현식
- 문제 : Contact
- 난이도 : Gold 5
- 해설
- 기본적인 정규표현식 문제입니다.
- Java에서 제공하는
Pattern
class와Matcher
class를 사용하면 됩니다. - 소스코드 : https://www.acmicpc.net/source/30210533
자료구조
- 문제 : 문제집
- 난이도 : Gold 2
- 해설
- 위상 정렬 문제입니다. 단, 스페셜 저지가 없는 위상 정렬 문제입니다.
- 여기서 스페셜 저지가 없다는 것은 정해진 단 하나의 답만 있다는 것입니다.
- 위상 정렬을 조금 수정하여 풀면 됩니다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class BAEKJOON_Gold_2_문제집 {
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 m = Integer.parseInt(st.nextToken());
List<List<Integer>> map = new ArrayList<>();
for (int i = 0; i <= n; i++) {
map.add(new ArrayList<>());
}
int[] inDegree = new int[n + 1];
int a, b;
for (int i = 0; i < m; i++) {
st = new StringTokenizer(br.readLine());
a = Integer.parseInt(st.nextToken());
b = Integer.parseInt(st.nextToken());
map.get(a).add(b);
inDegree[b] += 1;
}
int[] result = new int[n + 1];
List<Integer> order = new ArrayList<>();
for (int i = 1; i <= n; i++) {
if (inDegree[i] == 0) {
order.add(i);
}
}
for (int i = 1; i <= n; i++) {
if (order.isEmpty()) {
break;
}
int p = order.remove(0);
result[i] = p;
for (int j = 0; j < map.get(p).size(); j++) {
int l = map.get(p).get(j);
if (inDegree[l] != 0) {
inDegree[l] -= 1;
if (inDegree[l] == 0) {
boolean inserted = false;
for (int k = 0; k < order.size(); k++) {
if (order.get(k) > l) {
order.add(k, l);
inserted = true;
break;
}
}
if (!inserted) {
order.add(l);
}
}
}
}
}
StringBuilder sb = new StringBuilder();
for (int i = 1; i <= n; i++) {
sb.append(result[i]).append(" ");
}
System.out.println(sb.toString().trim());
br.close();
}
}
Author And Source
이 문제에 관하여([ 2021.06.21 ] 하루 세 문제(3일차)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@taek/2021.06.21-하루-세-문제3일차저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)