Super Reduced String

Recommanded Free YOUTUBE Lecture: <% selectedImage[1] %>

yundream
2017-12-12
2017-11-30
112650

Super Reduced String

소문자 영어 알파벳으로 구성된 문자열을 가지고 있다. 한번의 연산에서 동일한 값을 가지고 있는 인접한 문자를 삭제 할 수 있다. 예를 들어 문자열 "aabcc"의 경우 연산이 작동하면 "aab" 혹은 "bcc"가 된다.

이러한 연산을 반복해서 가능한 문자열을 줄이기를 원한다. 더 이상 인접한 문자열이 없을 때까지 이 연산을 반복해서 남는 문자열을 출력하라.

만약 남는 문자열이 없을 경우 "Empty String"를 출력한다.

입력 형식

단일 문자열 s

제약 조건

문자열의 길이는 1에서 100 사이다.

출력 형식

마지막 남은 문자열을 출력한다. 문자열이 없다면 Empty String를 출력한다.

예제

입력

aaabccddd

출력

abd

aaabccddd -> abccddd
abccddd -> abddd
abddd -> abd

그러므로 abd를 출력한다.

풀이

Stack을 이용해서 풀기로 했다.

a를 입력한다.
b를 입력한다. 스택의 가장 위에 같은 단어가 없으면 스택에 PushBack 한다.
b를 입력한다. 스택의 가장 위에 같은 "b"가 있으므로 Pop을 해버린다.
a를 입력한다. 스택의 가장위에 "a"가 있으므로 Pop을 한다.
남은 단어가 없으므로 "Empty String"를 출력한다.

위의 과정을 예쁘게 코드로 정리하면된다. 스택을 구현해야 겠으나, 귀찮아서 golang의 list 컨테이너로 대충 스택을 구현해서 풀었다.

package main

import (
    "bufio"
    "container/list"
    "fmt"
    "os"
)

func Reduce(a string) {
    List := list.New()
    strLen := len(a)
    for i := 0; i < strLen; i++ {
        if List.Len() == 0 {
            List.PushBack(a[i])
            continue
        }
        e := List.Back()
        if e.Value == a[i] {
            List.Remove(e)
        } else {
            List.PushBack(a[i])
        }
    }
    if List.Len() == 0 {
        fmt.Println("Empty String")
        return
    }
    for e := List.Front(); e != nil; e = e.Next() {
        fmt.Printf("%c", e.Value)
    }
    fmt.Println()
}

func main() {
    scanner := bufio.NewScanner(os.Stdin)
    buf := make([]byte, 0, 64*1024)
    scanner.Buffer(buf, 1024*1024)
    scanner.Split(bufio.ScanLines)
    scanner.Scan()
    Reduce(scanner.Text())
}

재귀호출 버전

스택이면 재귀호출로도 풀 수 있을 거다. 귀찮아서 패스

Search For:

BY TAGS

Contents