[ 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();
    }
}

• 소스코드 : https://www.acmicpc.net/source/30212402