코딩 테스트_3. 해당 단어를 원하는 단어로 변환

( 문제 )

입력 1.

"this is {template} {template} is {state}"

입력 2.

[["template", "string"], ["state", "changed"]]

입력 2에 따라 입력 1의 문자열을 template -> string, state -> changed로 바꿔서 리턴해주면 됩니다.

결과

"this is string string is changed"

여기서 해당 배열 찾아서 바꿔주면 되겠네 할 수 있습니다.

문제는..!

[["template", "string"], ["state", "changed"], ["changed", "template"]]

입력 2로 이와 같은 상황이 주어질 때입니다.

유니온-파인드 알고리즘을 이용하면 비교적 쉽게 해결할 수 있습니다.

 

유니온-파인드 설명 관련 영상

(54) Union Find in 5 minutes — Data Structures & Algorithms - YouTube

 

---

( 문제 해설 )

1. 유니온-파인드의 숫자를 문자열로 치환하고

2. 간선을 입력 2의 오른쪽 왼쪽의 입력이라고 생각하고 코드를 짜면 문제를 비교적 쉽게 풀 수 있습니다

0 - 3의 간선을

template - string이라고 생각하고 코드를 짜는 거죠.

이런 생각으로  union연산을 ( 입력 2 ) 길이만 큼의 이중 for문을 돌려주면 변환 과정이 무한루프가 돼도 알아서 빠져나오게끔 코드를 짤 수 있습니다.

[["template", "string"], ["state", "changed"], ["changed", "template"], ["string", "state"]]

무한루프? 무슨 소리지 하실 수 있는데 위와 같은 입력 2의 형태를 보시면 무한루프가 되겠구나 할 겁니다. 유니온 연산은 입력2의 길이의 제곱만큼만 하면 되기 때문에 설령 무한루프가 되는 입력이라도 되지 않는다는 뜻입니다.

설명이 다소 난잡하지만...

이번 문제는 유니온-파인드를 이해하셨다면 제 코드를 보시면 어떻게 짰겠구나 하고 바로 감을 잡을실겁니다.

 

---

[ 코드 ]

 

#3번 문제 - 문자열 변환
def union(a, b, parents):
    a = find(a, parents)
    b = find(b, parents)
    if a != b:
        parents[a] = b


def find(x, parents):
    if parents[x] != x:
        parents[x] = find(parents[x], parents)
        return parents[x]
    return x


def solution(strs, change):
    answer = ""

    parents = {}
    for index in range(len(change)):
        for j in range(2):
            parents[change[index][j]] = change[index][j]

    # 유니온-파인트 이용
    for _ in range(len(change)):
        for idx in range(len(change)):
            a, b = change[idx][0], change[idx][1]
            union(a, b, parents)

    # 변환
    list_strs = strs.split(" ")
    for i in range(len(list_strs)):
        if list_strs[i][0] == "{":
            # 바꾸기 넣어야됨
            # parents[list_strs[i][1:-1]]
            list_strs[i] = parents[list_strs[i][1:-1]]

    for strs in list_strs:
        answer += strs + " "
    return answer


print(solution("this is {template} {template} is {state}", [["template", "string"], ["state", "changed"], ["changed", "template"], ["string", "state"]]))
# 입력
# "this is {template} {template} is {state}"
# [["template", "string"], ["state", "changed"]]
# 내가 추가: [["template", "string"], ["state", "changed"], ["changed", "template"]]
# 결과
# "this is string string is changed"

---

후기

 

코 테일 때 이렇게 문제를 멋들어지게 풀고 싶다..

될 수 있겠지?

문제 2, 3은 시험이 얼마 남지 않은 상황에서 문제를 슥보고 푼 거라

실제 문제와 다를 수 있습니다. 애초에 실제 문제는 공개하지 않기 때문에 알 수 없지만

다만 저처럼 코테를 보신 분이 있을 수 있을 수도 있고 못 푼 게 억울하기도 하고

푸는 게 재밌기도 하니까 공부 삼아 배포합니다.

이상 코테 풀이였습니다.