[Swift] 프로그래머스 LV2. [3차] 파일명 정렬

프로그래머스 LV2. [3차] 파일명 정렬

 

접근 방식

 

파일명을 head, number, tail 세 부분으로 나눠 튜플로 만들고, head는 대소문자 구분 없이, number는 정수 값으로 정렬하는 문제.

 

정규 표현식으로 나눌 수도 있지만, 제대로 공부해 본 적이 없어 검색해서 그대로 쓰는 건 학습에 도움이 안 될 것 같아 직접 문자를 순회하며 처리. 정규 표현식의 시간복잡도를 가늠하기 어려운 점도 있었음.

 

문자를 앞에서부터 보며 숫자가 처음 나오는 위치를 head의 끝으로, 숫자가 끊기거나 5자리를 넘기는 지점을 number의 끝으로 잡음. 파일명 끝까지 숫자면 tail은 빈 문자열.

 

시행착오

 

반례에 대한 질문

 

https://programmers.co.kr/questions/30185

 

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

 

테스트 케이스 3, 4, 5, 6, 7, 19, 20번이 틀림.

 

질문 게시판을 보면 보통 3번은 맞는 경우가 많던데 여기서부터 틀려서 더 헤맴.

 

import Foundation
func solution(_ files:[String]) -> [String] {

        // head, number는 무조건 1글자 이상이나 tail은 없을 수도 있다.
        var fileList = [(String, String, String)]()

        // 데이터 정제
        files.forEach { file in

            var numberFlag = false
            var numberRangeStart = -1

            var numberCount = 0 // 숫자는 최대 5개이므로
            for i in 0..<file.count {
                let idx = file.index(file.startIndex, offsetBy: i)

                if file[idx].isNumber && numberCount != 0 && file[idx] == "0" {
                    print(numberCount)
                    numberCount += 1
                }

                if file[idx].isNumber && numberFlag == false {
                    numberFlag = true
                    numberRangeStart = i
                    numberCount = 1
                } else if (!file[idx].isNumber && numberFlag == true) || numberCount >= 5 {
                    // 이때 number의 range가 정해진다.
                    let headIndex = file.index(file.startIndex, offsetBy: numberRangeStart)
                    let head = String(file[..<headIndex])
                    let number = String(file[headIndex..<idx])
                    let tail = String(file[idx...])

                    let data = (head, number, tail)
                    fileList.append(data)
                    numberFlag = false

                    break
                }
            }

            if numberFlag == true { // 여전히 true인 경우는 파일의 tail이 숫자인경우
                let headIndex = file.index(file.startIndex, offsetBy: numberRangeStart)
                let head = String(file[..<headIndex])
                let number = String(file[headIndex...])

                let data = (head, number, "")
                fileList.append(data)
            }
        }

        // 데이터 정렬
        // head -> number -> tail의 우선순위
        let sortedList = fileList.sorted {

            if $0.0.lowercased() == $1.0.lowercased() {
                return Int($0.1)! < Int($1.1)!
            }
            return $0.0 < $1.0
        }

        // 출력부
        var answer = [String]()
        sortedList.forEach { file in
            answer.append("\(file.0)\(file.1)\(file.2)")
        }



        return answer
    }

 

stable 정렬 문제인가 싶어 찾아봤는데, Swift 5부터는 정렬이 stable해서 원인이 아니었음. 카카오 해설까지 봐도 로직 자체는 맞아 보여, 직접 반례가 될 케이스를 만들어 봄.

 

원인은 정렬 비교자였음. head가 같은지 판단할 때는 lowercased()로 대소문자를 무시하는데, 같지 않을 때의 정렬은 $0.0 < $1.0으로 원래 대소문자를 그대로 비교하고 있었음. 두 기준이 어긋나 순서가 뒤틀린 것. 아래 코드처럼 정렬 쪽에도 lowercased()를 붙여 기준을 맞추니 통과함.

 

코드

 

func solution(_ files:[String]) -> [String] {
        
        // head, number는 무조건 1글자 이상이나 tail은 없을 수도 있다.
        var fileList = [(String, String, String)]()
        
        // 데이터 정제
        files.forEach { file in
            
            var numberFlag = false
            var numberRangeStart = -1
            
            var numberCount = 0 // 숫자는 최대 5개이므로
            for i in 0..<file.count {
                let idx = file.index(file.startIndex, offsetBy: i)
                
                if file[idx].isNumber && numberCount != 0 && file[idx] == "0" {
                    print(numberCount)
                    numberCount += 1
                }
                
                if file[idx].isNumber && numberFlag == false {
                    numberFlag = true
                    numberRangeStart = i
                    numberCount = 1
                } else if (!file[idx].isNumber && numberFlag == true) || numberCount >= 5 {
                    // 이때 number의 range가 정해진다.
                    let headIndex = file.index(file.startIndex, offsetBy: numberRangeStart)
                    let head = String(file[..<headIndex])
                    let number = String(file[headIndex..<idx])
                    let tail = String(file[idx...])
                    
                    let data = (head, number, tail)
                    fileList.append(data)
                    numberFlag = false
                    
                    break
                }
            }
            
            if numberFlag == true { // 여전히 true인 경우는 파일의 tail이 숫자인경우
                let headIndex = file.index(file.startIndex, offsetBy: numberRangeStart)
                let head = String(file[..<headIndex])
                let number = String(file[headIndex...])
                
                let data = (head, number, "")
                fileList.append(data)
            }
        }
        
        // 데이터 정렬
        // head -> number -> tail의 우선순위
        let sortedList = fileList.sorted {

            if $0.0.lowercased() == $1.0.lowercased() {
                return Int($0.1)! < Int($1.1)!
            }
            return $0.0.lowercased() < $1.0.lowercased() // 여기가 문제였음 !! 
        }

        // 출력부
        var answer = [String]()
        sortedList.forEach { file in
            answer.append("\(file.0)\(file.1)\(file.2)")
        }
        
        return answer
    }