백준 1032번 풀이

문제

https://www.acmicpc.net/problem/1032

백준 유의사항

1. readLine()을 통해 input을 취득해야 한다.
2. Input이 여러줄인 경우, readLine()이 nil 일 때까지 값을 취득해야 한다.
3. 백준 온라인 저지의 Swift 컴파일러가 지원하지 않는 버전의 문법이 포함되어있는 경우, 컴파일 에러가 발생할 수 있다.

// e.g. 옵셔널 바인딩 문법
guard let value else { return } // Swift 5.7 이상에서 지원, ❌
guard let value = value else { return } // ✅

제출 코드

var lines: [String] = []
while let line = readLine() {
    lines.append(line)
}

func run(input: [String]) -> String {
	// 파일 개수가 1개라면 유일한 파일 이름 반환
    guard Int(input[0]) ?? 0 > 1 else { return input.last ?? "" }
    // "파일 이름 문자열 -> 문자 배열" 변환
    let characterSet = input[1..<input.count].map({ $0.map({ $0 }) })
    var result: [Character] = []
    // 모든 파일명의 길이가 같다는 전제가 있기 때문에 파일명의 길이만큼만 순환
    Array(0..<(characterSet.first?.count ?? 0)).forEach { index in
        var comparedChar: Character?
        for chars in characterSet {
			// 첫 문자라면 저장
            guard comparedChar != nil else {
                comparedChar = chars[index]
                continue
            }
            // 첫 문자가 아니라면 비교하고, 문자가 다르면 패턴이 아니기 때문에 "?" 저장하고 순환 종료
            if comparedChar != chars[index] {
                comparedChar = "?"
                break
            }
        }
        // 문자 인덱스 별 결과 문자를 최종 문자 배열에 추가
        guard let comparedChar = comparedChar else { return }
        result.append(comparedChar)
    }
    // "문자 배열 -> 문자열" 병합
    return result.map({ String($0) }).joined()
}

print(run(input: lines))

개선 코드

// 파일 개수를 먼저 캐치하기
if let firstLine = readLine(), let fileCount = Int(firstLine) {
    var files: [String] = []
    while let file = readLine() {
        files.append(file)
    }
    
    let firstFile = files[0]
    if fileCount == 1 {
        print(firstFile)
    } else {
        var result: String = ""  // "문자 배열 -> 문자열" 수정
        let length = firstFile.count
        for index in 0..<length {
            let stringIndex = firstFile.index(firstFile.startIndex, offsetBy: index)  // String.Index
            let referenceChar = firstFile[stringIndex]  // 문자열 접근 가능
            var isMatched: Bool = true  // "result에 추가할 문자 저장 -> 패턴 해당 여부" 수정
        
            for file in files[1...] {
                let fileStringIndex = file.index(file.startIndex, offsetBy: index)  // String.Index
                if file[fileStringIndex] != referenceChar {  // 문자열 접근 가능
                    isMatched = false
                    break
                }
            }
            
            result.append(isMatched ? referenceChar : "?")
        }
        print(result)
    }
}

개선된 점

1. 입력 저장
   • 개선 전
     • 전체 입력을 배열로 저장
   • 개선 후
     • 첫번째 입력라인은 파일갯수(숫자)이기 때문에 첫번째 입력을 fileCount로 별도 저장하고, 이후 입력값은 파일명이기 때문에 files: [String]으로 저장
   • 필요한 값이 역할에 맞게 분리되어 저장되어 배열에 접근하는 등의 처리를 하지 않아 가독성이 향상되었습니다.
2. 문자 배열 변환 & 결과 저장
   • 개선 전
     • String 내 문자 배열에 Int 타입으로 접근할 수 없어 문자 배열로 변환
   • 개선 후
     • String.Index 타입의 인덱스를 구해 문자 배열 변환없이 바로 문자열에 subscript로 접근하여 해당 위치에 존재하는 문자 추출
     • startIndex로부터 offsetBy 값만큼 떨어진 인덱스 위치의 값을 구할 수 있기 때문에 index로 원하는 위치의 문자 추출 가능
   • 문자열에서 문자 배열로 변환하여 저장하면 O(N * L) 의 추가 공간을 사용하지만, 추가 변환없이 문자열을 그대로 사용하고 result도 문자배열이 아닌 문자열로 처리하게되어 최소한 O(L) 의 추가 공간 아용으로 메모리 효율이 개선되었습니다. (N : 파일 개수, L : 파일명 길이)
3. 시간 복잡도는 파일 길이(L)만큼 반복하고, 각 반복마다 파일 개수(N)를 순회하는 것은 동일하기 때문에 O(N · L) 로 같지만, 파일 문자열을 문자 배열로 변환하는 작업이 제거되어 상수 시간 즉 각 문자마다 발생할 수 있는 O(1) 시간들이 줄어들기 때문에 최적화가 되었다고 볼 수 있습니다.

	개선 전	개선 후
시간복잡도	O(N * L) + a a : 문자열 → 문자배열 반환으로 인한 상수 시간	O(N * L)
공간복잡도	O(N * L)	O(L)

상수 시간 오버헤드 개념은 처음 접한 개념이라서 최대한 이해한대로 작성했습니다.