[Swift Algorithm] 64064 불량 사용자 (2019 카카오 인턴십)

programmers.co.kr/learn/courses/30/lessons/64064

코딩테스트 연습 - 불량 사용자

 

 

풀이방법

먼저 불량사용자에 해당하는 유저아이디를 이차원배열의 형태로 모두 저장했어요

["frodo", "fradi", "crodo", "abc123", "frodoc"], ["fr*d*", "abc1**"]

주어진 예시가 위의 형태라면

[[frodo, fradi], [abc123]]

이렇게 저장되어있겟죠

여기서 저는 문자열로 저장하지않고 간단하게 비교하기위해 인덱스를 사용했어요

result = [[0,1], [3]]

형태의 데이터가 생겨요

 

이데이터를 가지고 이제 

조합을 찾아야해요

 

0,3 인경우와 1,3인 경우가 있겟죠

위의 경우는 쉽지만

 

다른 예시로

result = [[0, 2], [0, 2], [3, 4]]

이런 결과를 가지고있다면

0, 0, 3 이런 조합은 할 수 없으므로

잘생각해줘야겟죠

 

그래서 저는

이차원배열을 순회하면서 하나씩 데이터를 꺼내서 저장하도록 구현했어요

처음 [0,2]중 0을 배열에 저장하고

현재 선택된 배열상태: [0]

 

두번째 [0,2]중 0을 선택하고 선택된 배열중 0이있다면 다음 요소를 선택해가는 과정을 거쳐요

그러면 0은이미있으니까 2가선택되겟죠?

현재 선택된 배열상태: [0, 2]

 

세번째 [3,4]중 3을 선택하면

[0,2,3]이라는 배열을 가지고있겟네요

3개의 선택된 요소가있다면 불량아이디 사용자의 숫자와 같기때문에 1가지의 경우가 끝났고

이배열을 Set에 저장시켜요

현재 선택된 배열상태: [0,2,3]

 

이제 재귀함수를 빠져나오고 다음 반복문을 실행하게될거에요

현재 선택된 배열상태: [0,2]

에서 [3,4]중 3은했으니 4차례죠

현재 선택된 배열상태: [0,2,4]

Set에 저장!

 

다돌았으니 재귀를 다시 빠져나오면

현재 선택된 배열상태: [0]

두번째 [0,2]중 2를 선택했는데 이제 요소가없네요 끝이네요!

 

따라서 Set에는

[[0, 2, 3], [0, 2, 4]]

이 배열이 들어가있고

0,2,3조합과 0,2,4조합이 된다는소리니까 2가지의 경우가 있네요

 

func solutionP64064(_ user_id:[String], _ banned_id:[String]) -> Int {
    
    var result: [[Int]] = Array(repeating: [], count: banned_id.count)
    
    for (index, banID) in banned_id.enumerated() {
        for (i, userID) in user_id.enumerated() {
            // 유저아이디와 불량사용자 길이가 다르면 해당하지않는 아이디임
            if userID.count != banID.count {
                continue
            }
            // *의 위치 저장
            let starIndex = banID.enumerated().filter { $1 == "*" }.map { $0.offset }
            var tempBanID = banID.map { String($0) }
            let tempUserID = userID.map { String($0) }
            
            // *문자를 유저아이디에 대입
            starIndex.forEach {
                tempBanID[$0] = tempUserID[$0]
            }
            // 유저아이디와 불량아이디포맷과 같다면
            // result배열에 벤아이디에 해당하는 인덱스의 위치에 저장
            if tempUserID.joined() == tempBanID.joined() {
                result[index].append(i)
            }
        }
    }
    
    var set = Set<[Int]>()
    
    func combinate(i: Int, select: [Int]) {
        if select.count == banned_id.count {
            set.update(with: select.sorted())
            return
        }
        var select = select
        // 2차원배열을 순서대로 접근
        let arr = result[i]
        // 배열의 첫번째 요소부터 조합을 선택
        for n in arr {
            if select.contains(n) {
                continue
            }
            select.append(n)
            combinate(i: i+1, select: select)
            select.removeLast()
        }
    }
    
    combinate(i: 0, select: [])
    
    print(set.count)
    
    return set.count
}