[프로그래머스] Swift - 매칭 점수

https://school.programmers.co.kr/learn/courses/30/lessons/42893

프로그래머스

 

2023.10.14 기준 Level 3

 

알고리즘 공부를 위해 풀고 기록하는 글입니다!
참고만 해주시고 더 좋은 풀이법이 있다면 알려주세요!

 

아이디어

문제 조건

• HTML 형태의 페이지 정보가 주어진다.
• 각 페이지에 대해 점수들을 계산해서 매칭 점수가 가장 높은 페이지를 찾아야 한다.
• 점수 계산법
  • 기본 점수 = 해당 웹페이지의 텍스트 중, 검색어가 등장하는 횟수 (대소문자 무시)
  • 외부 링크 수 = 해당 웹페이지에서 다른 웹 페이지로 연결된 링크의 개수
  • 링크 점수 = 해당 웹페이지로 링크가 걸린 다른 웹페이지의 기본 점수 ÷ 외부 링크 수의 총합
  • 매칭 점수 = 기본 점수 + 링크 점수

 

문제에서 제공하는 html 형태의 문자열을 잘 파싱해서 주어진 점수들을 전부 계산하면 됩니다.

순차적으로 해결하면 되는 구현 문제입니다.

 

우선 웹페이지를 모델링한 클래스를 생성합니다.

해당 클래스의 생성자는 html 문자열을 받아서 파싱을 수행합니다.

 

Page.init()이 수행하는 작업들

1. 전체 html을 "<" 를 구분으로 split 하여 태그들을 분리하고 대소문자를 무시하라는 문제 조건에 따라 전부 소문자로 바꿉니다.
2. "<mata "로 시작하는 태그에서 해당 웹페이지의 url을 검출합니다.
3. "<a "로 시작하는 태그에서 외부 링크의 url들을 검출합니다.
4. 모든 태그들에서 word를 몇개 포함하는지 체크해서 기본 점수를 갱신합니다.

 

이렇게 기본 점수와 외부 링크를 전부 찾았으면 이제 웹페이지 간의 관계를 연결 할 수 있습니다.

즉, A 페이지가 B 페이지를 외부링크로 표시하고 있다면 B는 A로 부터 참조받고 있는 상황입니다.

Page들을 반복문을 돌며 이러한 참조 관계를 파악하고 B의 referencedLinks 배열에 A를 추가합니다.

즉, B는 A로부터 참조받고 있다는 것을 저장한 것입니다. (여기서 참조 == 링크로 연결)

 

이렇게 링크 연결 관계 또한 전부 저장을 했다면 링크 점수를 구할 수 있습니다.

링크 점수를 구했다면 곧바로 매칭 점수를 구할 수 있습니다. (매칭 점수 = 기본점수 + 링크 점수)

 

매칭 점수를 구해서 제일 큰 매칭 점수를 가진 페이지 번호를 리턴하면 됩니다!

 

풀이

1. Page 클래스 생성

fileprivate class Page {
    var url: String = ""
    var externalLinks = [String]()
    var referencedLinks = [Page]()
    var basicScore: Int = 0
    var externalLinkScore: Int {
        externalLinks.count
    }
    var linkScore: Double {
        referencedLinks.map { Double($0.basicScore) / Double($0.externalLinkScore) }.reduce(0, +)
    }
    var matchingScore: Double {
        Double(basicScore) + linkScore
    }

    init(word: String, html: String) {
        let html = html.split(separator: "<").map { $0.trimmingCharacters(in: .whitespacesAndNewlines) }.map { $0.lowercased() }.map { "<"+$0 }
        let word = word.lowercased()
        var basicSum = 0
        for tag in html {
            // url 찾기
            if tag.starts(with: "<meta ") {
                parseMetaTag(tag)
            }
            
            if tag.starts(with: "<a ") {
                parseATag(tag)
            }
            
            // 기본 점수 구하기
            basicSum += calculateBasicScore(for: tag, in: word)
        }
        
        self.basicScore = basicSum
    }
    
    func parseMetaTag(_ tag: String) {
        let metaTag = tag.split(separator: " ")
        if metaTag[1].contains("og:url") {
            self.url = String(metaTag[2].dropFirst(9).dropLast(3))
        }
    }
    
    func parseATag(_ tag: String) {
        let link = String(tag.split(separator: ">")[0].dropFirst(9).dropLast())
        self.externalLinks.append(link)
    }
    
    func calculateBasicScore(for tag: String, in word: String) -> Int {
        // 검색어를 알파벳을 제외한 문자로 분리
        let searchWords = tag.components(separatedBy: CharacterSet.letters.inverted)
        return searchWords.filter { $0 == word }.count
    }
}

• init에서 html을 split하고 나서 생긴 String들에는 좌우 공백이 생기는 경우가 발생해서 .whitespacesAndNewlines 들을 trimming 했습니다.
• 태그 단위로 분리하기 위해 "<" 를 기준으로 split 했는데 이러면 각 태그에서 "<"이 사라지기 때문에 map을 통해 전부 "<"를 다시 앞에 붙여줬습니다.
• calculateBasicScore 메서드는 해당 태그에서 word가 포함된 횟수를 리턴합니다.
  • CharacterSet.letters.inverted 를 활용하여 알파벳이 아닌 다른 모든 문자로 구분하라는 문제 조건을 충족했습니다.

 

2. solution 함수 구현

fileprivate func solution(_ word:String, _ pages:[String]) -> Int {
    let pages = pages.map { Page.init(word: word, html: $0) }
    
    for page in pages {
        for link in page.externalLinks {
            if let linkedPage = pages.first(where: { $0.url == link }) {
                linkedPage.referencedLinks.append(page)
            }
        }
    }
    
    let matchingScores = pages.map { $0.matchingScore }

    let maxScore = matchingScores.max()!
    
    return matchingScores.firstIndex(of: maxScore)!
}

1. html 형태의 pages를 Page 인스턴스로 매핑합니다.
2. page 객체들 간의 연결 관계를 파악하여 referencedLinks 배열에 넣습니다.
3. matchingScore를 계산하여 배열에 저장합니다.
4. 매칭 점수의 최댓값을 구하고 해당 페이지의 인덱스를 리턴합니다.

 

마무리

문제 자체는 특별한 알고리즘 기법이 필요 없기 때문에 난이도가 매우 높다고 할 수는 없지만 언어의 문법을 잘 알고 있는 것이 중요했습니다.

문자열을 문제 요구대로 잘 파싱하고 순서대로 점수를 차분히 구하는 것이 핵심이었습니다.

trimming, CharacterSet을 통한 분리 등 Swift에서 제공하는 툴들을 잘 활용하면 효율적으로 태그를 다룰 수 있었습니다.

 

정규식을 활용해서 멋지게 풀이한 답안들도 많이 있었는데 실전에서 정규식을 잘 세우고 적용하는 것은 쉽지 않을 것 같습니다. 그래도 정규식을 어떻게 세우고 코드에서 적용하는지에 대해서는 알아두면 좋을 것 같네요!