[자바] 백준 23746 - 문자열 압축 해제 (java)

 문제 : boj23746

---

 

필요 알고리즘 개념

• 문자열, 구현
  
  • 문자열을 다루는 방법을 알아야한다. 로직 자체는 문제에 제시된 그대로 구현만 할 수 있으면 풀 수 있다.

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

---

 

풀이

 

1. N개의 문자열을 입력받아 저장해둔다.

2. 압축된 문자열을 입력받는다.

3. '1'에서 입력받아둔 문자열을 순회하면서 ('1'에서 입력받을 때 미리 해둬도 된다)

___3.1 'to from' 으로 나눈다. 예를들어 "aa A"라면 from=A, to=aa 이다.

___3.2 '2'의 문자열에서 from을 전부 to로 변경해준다.

4. 새로 생성된 압축이 풀린 문자열에서 S부터 E번째까지의 문자열을 출력해준다.

 

  예를들어 예제 입력 1의 경우를 보자.

압축된 문자열은 ABAC이고, N개의 패턴을 보면 다음과 같다.

- from=A, to=aa 이므로 변환하면 ABAC -> aaBaaC

- from=B, to=bba 이므로 변환하면 aaBaaC -> aabbaaaC

- from=C, to=c 이므로 변환하면 aabbaaC -> aabbaac

 

따라서 최종적으로 s=4, e=6 이므로 aabbaac -> baa가 된다.

 

---

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    private static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }

    public void solution() throws Exception {
        int n = Integer.parseInt(br.readLine());
        String[] tmp = new String[n];
        for (int i = 0; i < n; i++) {
            tmp[i] = br.readLine();
        }

        String str = br.readLine();
        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(tmp[i]);
            String to = st.nextToken();
            String from = st.nextToken();
            str = str.replaceAll(from, to);
        }

        StringTokenizer st = new StringTokenizer(br.readLine());
        int s = Integer.parseInt(st.nextToken());
        int e = Integer.parseInt(st.nextToken());
        System.out.println(str.substring(s-1, e));
    }
}