[Swift 알고리즘] 프로그래머스(Lv.3) - 불량 사용자 / 2019 카카오 인턴십

안녕하세요. 개발 중인 정주입니다.

 

오늘은 "프로그래머스(Lv.3) - 불량 사용자" 문제를 풀었습니다.

 

---

 

Github

GitHub - jeongju9216/SwiftAlgorithm: 스위프트 알고리즘

 

문제 링크

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

 

---

풀이

이번 문제는 문자열 처리, 조합 문제입니다.

 

1. 제재 아이디를 구합니다.

제가 제재 아이디를 구한 방법은 이렇습니다.

1. 불량 사용자 리스트에서 아이템을 하나씩 체크합니다. (banned)
2. banned에서 *의 위치를 구합니다.
3. user_id의 user id들 중 banned와 문자열 길이가 같은 id를 구합니다.
4. 이 id들을 banned의 * 위치와 동일한 위치에 *로 값을 업데이트 합니다.
5. 변환한 user id가 banned와 동일한지 확인하고 동일하다면 banned의 매칭 리스트에 append합니다.

말로는 복잡하지만 코드를 보시면 오히려 이해가 편하실 겁니다.

여기서 구한 제재 아이디로 구성할 수 있는 경우의 수를 구해야 합니다.

 

2. 제재 아이디의 경우의 수를 구합니다.

제가 이 경우의 수를 못 구해서 끝내 풀이를 보았습니다.

너무나도 아쉽더라고요. dfs를 이용하는건가? 아니면 배열? 어떻게 응용해야 하지? 계속 고민해봐도 마땅히 모르겠더라고요.

 

재귀와 Set을 이용하여 중복을 지우면서 조합을 결과 Set에 insert 하였습니다.

1. 먼저 빈 Set을 인자와 count로 사용하는 index 인자를 전달, 호출합니다.
2. Set에 제재 아이디를 하나씩 추가합니다.
3. Set의 원소 개수와 제재 아이디의 개수가 동일하면 결과에 추가합니다.
4. 길이가 다르다면 index를 1 증가 시키고 제재 아이디를 추가한 Set을 전달하여 재귀 호출합니다.

3번에서 개수로 처리가 가능한 이유는 Set이기 때문입니다.

[A, B]라는 원소가 들어가더라도 Set에 insert를 할 때 sort를 하여 넣기 때문에 중복 처리가 됩니다.

Set은 중복되는 원소가 없기 때문에 이 문제에서는 개수가 같으면 같다고 볼 수 있습니다.

 

result도 Set으로 정의하여 중복되는 조합을 걸렀습니다.

이렇게 제재 아이디의 경우의 수를 구할 수 있었습니다.

 

제가 글을 잘 못 쓰는 편이라 코드가 더 이해가 쉬울 수도 있습니다 ㅠㅠ

감사합니다!

 

---

전체 코드

import Foundation

func solution(_ user_id:[String], _ banned_id:[String]) -> Int {

    var ids: [[String]] = Array(repeating: [], count: banned_id.count)
    
    for (bIndex, banned) in banned_id.enumerated() {
        //dot 위치 구하기
        var dotIndex: [Bool] = Array(repeating: false, count: banned.count)
        for (i, ch) in banned.enumerated() {
            dotIndex[i] = (ch == "*")
        }
        
        //제재 아이디 구하기
        for user in user_id {
            if banned.count != user.count {
                continue
            }
            
            let userString = user.enumerated().map { (index, ch)->String in
                return dotIndex[index] ? "*" : String(ch)
            }.joined()
            
            if userString == banned {
                ids[bIndex].append(user)
            }
        }
    }
    
    var results: Set<[String]> = []
    
    //조합 구하기
    func banResult(banIds: Set<String>, index: Int) {
        for bannedId in ids[index] {
            var newBanIds = banIds
            newBanIds.insert(bannedId)
            
            if newBanIds.count == ids.count {
                results.insert(newBanIds.sorted())
            } else if index+1 < ids.count {
                banResult(banIds: newBanIds, index: index+1)
            }
        }
    }
    
    banResult(banIds: [], index: 0)
    
    return results.count
}

---

아직은 초보 개발자입니다.

더 효율적인 코드 훈수 환영합니다!

공감과 댓글 부탁드립니다.