[2607/Swift] 비슷한 단어

*** 언어는 Swift! ***

이번에는 비슷한 단어라는 이름을 가지고 있는 2607번 문제이다.

이 문제를 풀 때 진짜 생각해야할 것도 많았고, 문제도 이해하는데 시간이 조금 걸렸고 해서 푸는데만 4시간 이상이 걸렸던 문제였다.

처음에 스터디 하기 전에 풀어간 코드가 중간에 마음에 안드는 부분이 있어서 블로그 포스팅 하기 전에 다시 수정했지만 이 코드도 딱히 마음에 드는 편은 아니었다. ⸜( ⌓̈ )⸝

 

어쨌든 거두절미하고 자세한 문제 내용은 아래와 같다.

자 오늘도 어김없이 문제를 쪼개보기로 하자

 

1. 첫째 줄에는 단어의 갯수가 주어지며, 둘째 줄 부터는 한 줄에 하나씩 단어가 주어진다.

2. 두개의 배열 갯수가 같지만 하나씩 다른 문자가 있으면 바꿔준다.

3. 비교하는 단어가 더 길다면 첫번째 단어에서 다른 문자를 제거한다.

4. 비교하는 단어가 더 짧다면 첫번째 단어에서 다른 문자를 추가한다.

5. 두 문자가 같은지 비교한다.

 

2, 3, 4번에 대한 문제가 조금 어려웠다. 이 문제는 하나의 단어에서 어떤 한 문자를 더하거나, 한 문자를 빼거나, 한 문자를 바꿨을 때 첫 번째 단어와 같은 지를 비교해야 했기 때문에 3개의 조건이 필요했다.

 

1. 첫째 줄에는 단어의 갯수가 주어지며, 둘째 줄 부터는 한 줄에 하나씩 단어가 주어진다.

이제는 익숙해져버린 입력을 받아보자

let count = Int(readLine()!)!
    
var words: [String] = []
var firstWord: [String] = []
var compareWords: [String] = []
var wordsIndex = 1
var matchCount = 0

/// 둘째 줄 부터는 한 줄에 하나씩 단어가 주어진다.
for _ in 0..<count {
    let word = readLine()!

    /// 단어를 오름차순으로 정렬한다.
    words.append(String(word.sorted(by: <)))
}

/// 첫  번째 단어를 배열에 저장한다.
firstWord = words[0].map { String($0) }

count로 단어의 갯수를 입력받고 둘째 줄 부터 입력받은 단어를 words 배열에 저장한다.

우리는 첫 번째 단어와 비교할거니까 배열의 첫 번째 값을 firstWord에 저장한다.

matchCount에는 비슷한 단어의 갯수를 저장할 것이고

wordsIndex는 비교할 단어 배열의 index 위치를 저장해 줄 것이다.

 

단어를 오름차순으로 정렬한 이유는 그렇게 했을 때 같은 문자를 버리고 다른 문자를 찾을 때 용이할 것 같아서 오름차순으로 정렬했다.

 

자 먼저 이 행동이 비교할 단어의 갯수를 모두 돌아야하기 때문에 while문을 이용해 반복해준다.

while wordsIndex < words.count {

그 다음에 비교할 단어를 compareWords 배열에 저장한다. 이 때 index 값은 위에서 선언해둔 wordsIndex로 대신한다.

 compareWords = words[wordsIndex].map { String($0) }

위에서 오름차순으로 정렬했기 때문에 문자의 위치는 다르지만 정렬하면 똑같은 단어들이 있을 것이다.

예를 들면 문제에 나온 DOG와 GOD 이다.

두 단어를 오름차순으로 정렬하면

["D", "G", "O"]

["D", "G", "O"]

와 같이 똑같아지기 때문에 더 이상의 비교는 필요가 없다. 그렇기 때문에 초반에 두 개의 단어가 같다면 matchCount와 wordsIndex를 올려주고 continue 한다.

if firstWord.joined() == compareWords.joined() {
    wordsIndex += 1
    matchCount += 1
    continue
}

자 그럼 이제는 다음 비교를 위한 준비가 필요하다.

 

1-1. 두 배열에 같은 값이 있는지 확인하고 남겨진 문자에 대한 인덱스를 가져온다.

이제 위에서 완벽히 똑같을 때에 대한 처리는 했으니 이젠 다를 경우에 대한 처리를 해보자

먼저 두 배열에 같은 값이 있는지 확인하고 있으면 그 자리를 빈 값으로 바꿔준다.

나중에 비교를 위해 temp 변수를 새로 만들어서 같은 문자를 제거한 배열을 저장해주었다.

/// 비교를 위해 temp 변수를 만든다.
var firstTempWords: [String] = firstWord
var compareTempWords: [String] = compareWords

 for i in 0..<firstWord.count {
    for j in 0..<compareWords.count {
        if firstTempWords[i] == compareTempWords[j] {
            compareTempWords[j] = ""
            firstTempWords[i] = ""
            break
        }
    }
}

그럼 만약 DOG 와 GOOD 을 비교하면

firstWord 에는 모든 게 같기 때문에 -> ["", "", ""]

compareWords 에는 O가 하나 남기 때문에 -> ["", "", "", "O"]

이런 식으로 저장되게 될 것이다.

 

자 그럼 이제 남은 문자에 대한 인덱스를 가져오자

여기가 가장 마음에 들지 않은 코드인데 for문을 돌려서 비어있는 값이 아닌 경우 해당 인덱스 값을 변수에 저장해준다.

var extraCompareIndex: Int = 0
var extraFirstIndex: Int = 0

for i in 0..<compareTempWords.count {
    if !compareTempWords[i].isEmpty {
        extraCompareIndex = i
        break
    }
}

for i in 0..<firstTempWords.count {
    if !firstTempWords[i].isEmpty {
        extraFirstIndex = i
        break
    }
}

 

compareWords, firstWord 둘 다 인덱스를 가져온 이유는 치환할 때 firstWord 배열 안의 값을 이용해야하는 경우도 있고, compareWords 의 단어가 더 긴 경우도 있을 것이고 firstWord 의 단어가 더 긴 경우도 있기 때문이다.

자 이제 본격적으로 비교를 해보자

 

2. 두개의 배열 갯수가 같지만 하나씩 다른 문자가 있으면 바꿔준다.

먼저 두개의 배열 갯수가 같지만 하나씩 다른 문자가 있는 경우이다.

예로는 AAAB 와 ABBA 이다

위 경우는 정렬되면 ["A", "A", "A", "B"], ["A", "A", "B", "B"]

그리고 중복되는 단어를 제거하면 ["", "", "A", ""], ["", "", "", "B"]

위 처럼 남게 될 것이다. 그럼 여기서 우리는 A와 B를 바꿔준다.

firstWord와 똑같아져야하기 때문에 compareWords를 map을 이용해 index가 같은 곳을 찾아준다.

 if firstWord.count == compareWords.count {
    compareWords = compareWords.enumerated().map { index, value in
        ///  인덱스가 같으면
        if index == extraCompareIndex {
            /// 해당 인덱스를 firstWord의 index로 바꿔주기
            return firstWord[extraFirstIndex]
        }
        return String(value)
    }.sorted(by: <)
}

여기서 enumerated().map 을 사용했는데 기존 map은 그냥 value, 배열 값만 받아올 수 있었다. 하지만 지금 내가 필요한 건 배열의 index이기 때문에 enumerated()를 사용했다. enumerated()는 sequence를 리턴하는데 이 친구를 이용해 index 값을 얻을 수 있다.

 

여기서 index와 아까 구했던 extraCompareIndex를 이용해 같은지 비교한 후 해당 위치의 값을 firstWord 배열의 extraFirstIndex 값을 return 해준다. 나머지는 그대로 compareWords의 값을 리턴해준다.

그리고 배열이 똑같은지 비교를 위해 sorted로 오름차순으로 정렬한다.

 

그렇게 되면 ["A", "A", "A", "B"], ["A", "A", "B", "B"] 는 최종적으로 compareWords의 3번째 자리를 firstWords의 2번째 자리의 값으로 바꿔주고, 정렬했기 때문에 ["A", "A", "A", "B"], ["A", "A", "A", "B"] 가 되어 똑같아지게 된다.

 

3. 비교하는 단어가 더 길다면 첫번째 단어에서 다른 문자를 제거한다.

이번에는 비교하는 단어가 즉 compareWords가 더 긴 경우이다.

예를 들면 AAAB 와 AAABC

위 경우는 마찬가지로 정렬되면 ["A", "A", "A", "B"], ["A", "A", "A", "B", "C"]

그리고 중복되는 단어를 제거하면 ["", "", "", ""], ["", "", "", "", "C"]

위 처럼 CompareWords의 값만이 남게된다. 그럼 여기서 우리는 단순하게 CompareWords의 저 마지막 C만 제거해주면 된다.

else if firstWord.count <= compareWords.count {
    /// 비교하는 문자가 첫번째 문자보다 더 길 때, 비교하는 문자에서 남는 문자를 제거해준다.
    compareWords.remove(at: extraCompareIndex)
    compareWords = compareWords.sorted(by: <)
}

위에서 구했던 extraCompareIndex가 4가 될 테니 compareWords에서 4번째 값을 제거하면

["A", "A", "A", "B"], ["A", "A", "A", "B"] 로 똑같아지게 된다.

 

4. 비교하는 단어가 더 짧다면 첫번째 단어에서 다른 문자를 추가한다.

이번에는 비교하는 단어가 즉 compareWords가 더 짧은 경우이다.

예를 들면 AAAB 와 ABA

위 경우는 마찬가지로 정렬되면 ["A", "A", "A", "B"], ["A", "A", "B"]

중복되는 단어를 제거하면 ["", "", "A", ""], ["", "", ""]

위 처럼 이번에는 firstWords의 값이 남게 된다. 우리의 중점은 firstWord 이기 때문에 compareWords의 해당 값을 추가해주면 된다.

else if firstWord.count >= compareWords.count {
    ///첫 문자가 더 길 때 비교하는 문자에 추가해준다.
    compareWords.append(firstWord[extraFirstIndex])
    compareWords = compareWords.sorted(by: <)
}

위에서 구했던 extraFirstIndex가 2가 될 테니 compareWords에 firstWords의 extraFirstIndex의 값 즉 A를 append 해준 뒤 정렬한다. 그렇게 하면

["A", "A", "A", "B"], ["A", "A", "A", "B"] 로 똑같아지게 된다.

 

5. 두 문자가 같은지 비교한다.

마지막으로 위에 조건문을 하나씩 통과한 후 같은지 확인한 후 matchCount와 index를 변경하기 위해 같은 지 비교한다.

if firstWord.joined() == compareWords.joined() {
    matchCount += 1
}

wordsIndex += 1

 

이렇게 하면 정답을 얻을 수 있다! while 문 안의 전체 코드는 아래와 같다.

while wordsIndex < words.count {

    /// 비교할 단어를 배열에 저장한다.
    compareWords = words[wordsIndex].map { String($0) }

    /// sorting 한 두 단어가 똑같으면 바로 넘긴다.
    if firstWord.joined() == compareWords.joined() {
        wordsIndex += 1
        matchCount += 1
        continue
    }

    /// 비교를 위해 temp 변수를 만든다.
    var firstTempWords: [String] = firstWord
    var compareTempWords: [String] = compareWords

    /// 두 배열에 같은 값이 있는지 확인한다.
    for i in 0..<firstWord.count {
        for j in 0..<compareWords.count {
            if firstTempWords[i] == compareTempWords[j] {
                compareTempWords[j] = ""
                firstTempWords[i] = ""
                break
            }
        }
    }

    /// 배열에 남겨진 문자 가져오기
    /// 배열에 남겨진 문자 인덱스 가져오기
    var extraCompareIndex: Int = 0
    var extraFirstIndex: Int = 0

    for i in 0..<compareTempWords.count {
        if !compareTempWords[i].isEmpty {
            extraCompareIndex = i
            break
        }
    }

    for i in 0..<firstTempWords.count {
        if !firstTempWords[i].isEmpty {
            extraFirstIndex = i
            break
        }
    }

    /// 두개의 배열 갯수가 같고, 하나씩 다른 문자가 있다면 치환해준다.
    if firstWord.count == compareWords.count {
        compareWords = compareWords.enumerated().map { index, value in
            ///  인덱스가 같으면
            if index == extraCompareIndex {
                /// 해당 인덱스를 firstWord의 index로 바꿔주기
                return firstWord[extraFirstIndex]
            }
            return String(value)
        }.sorted(by: <)
    } else if firstWord.count <= compareWords.count {
        /// 비교하는 문자가 첫번째 문자보다 더 길 때, 비교하는 문자에서 남는 문자를 제거해준다.
        compareWords.remove(at: extraCompareIndex)
        compareWords = compareWords.sorted(by: <)
    } else if firstWord.count >= compareWords.count {
        ///첫 문자가 더 길 때 비교하는 문자에 추가해준다.
        compareWords.append(firstWord[extraFirstIndex])
        compareWords = compareWords.sorted(by: <)
    }
    
    if firstWord.joined() == compareWords.joined() {
        matchCount += 1
    }
    
    wordsIndex += 1
}

 

이번에는 코드가 되게 얼레벌레하고 길고 복잡했지만 그래도 풀었다는 것에 조금 뿌듯했다!

오늘도 한 건 해결 ⸜(*ˊᗜˋ*)⸝