[백준 9935번] 문자열폭발

2021. 7. 5. 05:02Algorithm/practice

https://www.acmicpc.net/problem/9935

 

9935번: 문자열 폭발

첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다. 두 문자열은 모

www.acmicpc.net


문제 접근 및 해결 방법

처음에 replace와 재귀를 이용해서 Java로 풀었는데 메모리 초과가 났다. 싸피분들과 리뷰를 하며 스택을 이용해야한다는 걸 알게 되었다. 백준 9935번 문자열 폭발과 유사해서 다시 풀어보았다. 마침 Go를 배우고 있어서 Go로 다시 풀어보았다. 풀면서 Go에 stack이 없어서 slice 개념을 이용해서 구현했다. 또한 풀면서 Go가 지원하는 자료형에 char이 없어서 slice한 string이 byte형이 된다는 것을 알게되었다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
package main
 
import (
    "bufio"
    "fmt"
    "os"
)
 
func main() {
    r := bufio.NewReader(os.Stdin)
    w := bufio.NewWriter(os.Stdout)
    defer w.Flush()
 
      var str, target string
      var stack []byte
  
      fmt.Fscan(r, &str, &target)
  
      var lenOfStr int = len(str)
      var lenOfTarget int= len(target)
  
      for i := 0; i < lenOfStr; i++ {
        stack = append(stack, str[i])
 
        var lenOfStack int = len(stack)
        if stack[lenOfStack-1== target[lenOfTarget-1] { // 만약 넣은 문자가 폭발문자열의 끝문자와 같을 경우
            if lenOfStack >= lenOfTarget && string(stack[lenOfStack-lenOfTarget:lenOfStack]) == target {
                stack = stack[:lenOfStack-lenOfTarget] // 폭발문자열이 있으면 폭발문자열 빼주기
            }
        }
    }
  
    if len(stack) == 0{
        fmt.Fprintln(w, "FRULA")
    }else
        fmt.Fprintln(w, string(stack))
    }
}
cs

'Algorithm > practice' 카테고리의 다른 글

[백준 9935번] 문자열폭발  (0) 2021.07.05
[백준 2805번] 나무 자르기  (0) 2020.07.22
[백준 11005번] 진법변환2  (0) 2020.07.10
[백준 1181번] 단어정렬  (0) 2020.07.09
[백준 2446번] 별찍기-2446  (0) 2020.07.08
[백준 2523번] 별찍기-13  (0) 2020.07.08
1 2 3 4 5 6 7 8 ··· 78