백준) 1141번: 접두사 (Swift)

목차

머리말

문제 링크

1141번: 접두사

이 문제를 선택한 이유

• 구현 문제 연습
• Swift 문자열 인덱스 접근 연습

풀이

n과 단어를 배열에 할당

1. 첫 줄의 숫자를 정수로 변환하여 n으로 할당한다.
2. 다음 줄부터는 n에 대한 반복문을 돌며 빈 배열에 하나하나씩 문자열을 추가한다.

isPrefix 함수

1. 우선 맨 아래 두 단어를 비교하여 한 단어가 다른 단어의 접두사인지를 판별하는 함수(isPrefix)를 만들었다.
2. 두 단어 중 작은 값을 범위로 하여 문자열 인덱스를 접근하는데, 같은 값이면 카운트를 한다
3. 카운트가 범위와 값이 같으면 접두사가 충족하기에 true를, 그렇지 않으면 기본값인 false를 리턴한다.

이중 반복문을 통한 인덱스 접근

1. 두 단어를 조합하기 위해 이중 반복문으로 인덱스를 접근한다.
2. isPrefix 함수로 두 단어가 접두사인지를 판별하여 참일 경우 조건문을 들어간다.
3. 두 단어 중 작은 단어를 "X"로 재할당한다.
4. 만약 두 단어가 같은 단어이면 하나만 "X"로 재할당한다.

반복문을 거친 배열 중에 "X"가 아닌 배열의 개수를 카운트

1. 위의 이중 반복문을 거쳤으면 접두사에 해당하는 단어가 모두 "X"가 되었을 것이다.
2. 배열의 요소를 돌면서 "X"가 아니면 카운트를 하여 최대의 부분집합의 수를 구한다.
3. 해당 수를 출력한다.

// 1141번: 접두사
// 실버 1
// https://www.acmicpc.net/problem/1141

import Foundation

var n: Int = Int(readLine()!)!
var words: [String] = []

for _ in 1...n {
    words.append(readLine()!)
}

for i in 0..<words.count {
    for j in i+1..<words.count {
        if isPrefix(words[i], words[j]) {
            if words[i].count > words[j].count {
                words[j] = "X"
            } else if words[i].count < words[j].count {
                words[i] = "X"
            } else {
                words[i] = "X"
            }
        }
    }
}

var count = 0

for word in words {
    if word != "X" { count += 1 }
}

print(count)

func isPrefix(_ wordOne: String, _ wordTwo: String) -> Bool {
    var result = false

    let range = min(wordOne.count, wordTwo.count)
    var count = 0

    for i in 0..<range {
        if wordOne[wordOne.index(wordOne.startIndex, offsetBy: i)] == wordTwo[wordTwo.index(wordTwo.startIndex, offsetBy: i)] {
            count += 1
        }
    }

    if count == range { result = true }

    return result
}

꼬리말

알고리즘 분류가 정렬? 트리?

• 문제를 풀고 분류를 보니 정렬과 트리가 들어가 있었다. 난 단순히 반복문, 조건문만 해서 풀었는데…
• 정렬을 할지 생각하다가 시간복잡도가 $n\log{n}$에 의해 시간 초과가 날까봐 사용하지 않았다

Swift의 문자열 접근은 정말…😭

• 오랜만에 인덱스 접근을 하니 문법이 익숙하지 않아 애를 먹었다.
• 이중삼중으로 접근하는데 결국 공식 문서를 참고했다… 하하
• index(_:offsetBy:) | Apple Developer Documentation