패턴매칭

문제 제시

인자로 문자열 2개가 전달된다.

하나는 패턴을 나타내는 문자열이고 하나는 데이터를 담은 문자열이다.

데이터를 담은 문자열이 패턴과 일치하는지를 판별하는 메서드를 만드시오.

 

예시

func solution(_ pattern: String, _ data: String) -> Bool {
    ...
}

solution("abbaa", "dog cat cat dog dog") // true
solution("xyxy", "one two two one") // false
solution("cbac", "dog cat bird dog") // true

문제 해결

func solution(_ pattern:String, _ target: String) -> Bool {
    // 패턴과 데이터를 문자열로 변환
    let patternChar = pattern.map{$0}
    let input = data.split(separator: " ")

    // 패턴과 데이터 딕셔너리 생성
    var patternDic: [Int: String] = [:]
    var dataDic: [Int: String] = [:]


    var patternResult: [String] = []
    var dataResult: [String] = []

    var patternCount: Int = 1
    var dataCount: Int = 1

    // 패턴 배열 비교하여 딕셔너리 생성
    for i in patternChar {
        if patternDic.isEmpty {
            patternDic.updateValue(String(i), forKey: patternCount)
            patternCount += 1
        } else {
            if !(patternDic.values.contains(String(i))) {
                patternDic.updateValue(String(i), forKey: patternCount)
            }
        }
    }

    // 데이타 배열 비교하여 딕셔너리 생성
    for i in input {
        if dataDic.isEmpty {
            dataDic.updateValue(String(i), forKey: dataCount)
            dataCount += 1
        } else {
            if !(dataDic.values.contains(String(i))) {
                dataDic.updateValue(String(i), forKey: dataCount)
            }
        }
    }

    // 패턴 딕셔너리 치환
    for i in patternChar {
        for j in patternDic {
            if String(i) == j.value {
                patternResult.append(String(j.key))
            }
        }
    }

    // 데이터 딕셔너리 치환
    for i in input {
        for j in dataDic {
            if String(i) == j.value {
                dataResult.append(String(j.key))
            }
        }
    }

    return patternResult == dataResult
}

처음에는 이렇게 복잡하게 for문을 돌면서 어떻게 어찌저찌 구현을 하였다.

그러나 이렇게 한다면 분명 효율성과 시간초과가 나올것이라고 생각하여 리팩토링 해보았다.

func solution(_ pattern: String, _ target: String) -> Bool {
    // 패턴 파라미터의 값 중복 제거 (패턴 종류 파악)
    let uniquePattern: String = Array(pattern).reduce("", { (result, next) -> String in
        if result.contains(next) {
            return result
        }
        return result + String(next)
    })
    
    // 타겟 파라미터 공백 문자열 기준 분리
    let targets = target.components(separatedBy: " ")
    
    // 패턴과 값을 담을 딕셔너리 생성
    var targetDic: [String: String] = [:]
    
    // 패턴의 초기 위치 값
    var patternIndex = 0
    
    // 최종 치환된 문자열 변수
    var finalTarget: String = ""
    
    // 타겟 돌면서 치환
    for i in targets {
        // 딕셔너리에 해당 키 값이 있는지 판별
        if let value = targetDic[i] {
            finalTarget.append(value)
            continue
        }
        
        guard patternIndex < uniquePattern.count else {
            return false
        }
        
        // 치환
        let patternValue = uniquePattern[uniquePattern.index(uniquePattern.startIndex, offsetBy: patternIndex)]
        targetDic[i] = String(patternValue)
        finalTarget.append(patternValue)
        
        patternIndex += 1
    }
    
    // 최종 패턴과 치환된 타겟 비교
    return pattern == finalTarget
}

고차함수를 적절히 사용하여 조금 더 효율성 있게 구조화해보았다.

딕셔너리를 돌며 해당 키에 대한 벨류 값을 비교해주고 있다면 넘어가며 해당 키 값을 추가하고 없다면 새로운 키값과 벨류를 만들어준다.

이런식으로 조금 더 반복문을 줄이고 효율성을 높여보았다.

 

사용된 개념

 - 문자열 다루기

 - 조건 / 반복문

 - 딕셔너리

 - 문자 치환

문제 뒷담화

해당 문제는 간단하게 생각이 들었는데 막상 구현을 하려니 생각보다 빠르고 쉽게 풀리지 않았다.

강제로 처음 문제 해결 방식처럼 구현은 할 수 있었지만 효율적으로 고차함수를 사용하여 푸는것이 머리가 안돌았다.

딕셔너리는 키 값이 중복될 수 없는 점을 활용하여 타겟을 돌며 딕셔너리에 해당 키에 대한 벨류값이 있는지 파악하고 치환해줌으로 해결하였다.