To Lower Case | 알고달레

LeetCode의 709번째 문제인 To Lower Case 문제를 함께 풀어보도록 하겠습니다.

문제

문자열 s가 주어졌을 때, 모든 영어 대문자를 대응하는 소문자로 바꾼 문자열을 반환하라. 소문자와 숫자, 공백, 특수 기호는 그대로 두면 된다.

입력 문자열의 길이는 1 이상 100 이하이며, 출력 가능한 ASCII 문자로만 이루어져 있다.

예제

입력: s = "Hello"
출력: "hello"

입력: s = "here"
출력: "here"

입력: s = "LOVELY"
출력: "lovely"

풀이 1

문자열의 대소문자를 바꾸는 기능은 많은 프로그래밍 언어에서 기본으로 제공하는데요. 파이썬에서는 문자열의 lower() 메서드를 사용하면 대문자를 소문자로 바꿀 수 있습니다.

예를 들어, "Hello".lower()를 호출하면 대문자 H가 소문자 h로 바뀌어서 "hello"가 반환됩니다. 이미 소문자인 글자나 숫자, 특수 기호는 바뀌지 않으므로, "Hello, World! 123"은 "hello, world! 123"이 되겠죠?

따라서 이 문제는 다음과 같이 한 줄로 구현할 수 있습니다.

class Solution:
    def toLowerCase(self, s: str) -> str:
        return s.lower()

n을 입력 문자열의 길이라고 했을 때, 이 풀이의 시간 복잡도는 O(n)입니다. 코드는 한 줄이지만, lower() 메서드 내부에서는 문자열의 각 문자를 확인해야 하기 때문입니다.

공간 복잡도도 O(n)인데요. 파이썬의 문자열은 변경할 수 없으므로, 원래 문자열을 수정하는 대신 변환된 문자열을 새로 만들어 반환하기 때문입니다.

풀이 2

만약에 대소문자를 바꿔주는 메서드를 사용할 수 없다면 어떻게 풀어야 할까요? 문자에 대응하는 숫자인 문자 코드를 이용해서 직접 소문자로 바꿔보겠습니다.

이 문제의 입력은 ASCII 문자로 제한되어 있는데요. ASCII에서 영어 대문자와 소문자는 각각 알파벳 순서대로 연속된 코드 값을 가집니다. 대문자 A의 코드 값은 65, 소문자 a의 코드 값은 97입니다. 마찬가지로 Z는 90, z는 122이므로, 같은 알파벳의 소문자와 대문자 사이에는 항상 32만큼 차이가 나네요. 32는 2의 5제곱이라서, 이진수로 보면 대문자와 소문자는 여섯 번째 비트 하나만 다릅니다(A는 1000001, a는 1100001).

문자	대문자 코드	소문자 코드	차이
A → a	65	97	32
B → b	66	98	32
Z → z	90	122	32

따라서 대문자의 코드 값에 32를 더한 후 다시 문자로 바꾸면 소문자를 얻을 수 있습니다. 파이썬에서는 ord() 함수로 문자의 코드 값을 구하고, chr() 함수로 코드 값에 해당하는 문자를 얻을 수 있는데요. 예를 들어, ord("H")는 72이고, chr(72 + 32)는 "h"가 됩니다.

단, 모든 문자에 무조건 32를 더하면 안 됩니다. 숫자나 특수 기호까지 다른 문자로 바뀌기 때문인데요. "A" <= ch <= "Z" 조건으로 영어 대문자인지 확인한 후, 대문자일 때만 변환하면 됩니다.

이제 문자열을 처음부터 끝까지 살펴보면서 변환한 문자를 리스트에 모으겠습니다. 대문자가 아닌 문자는 그대로 넣고, 마지막에 join() 메서드로 리스트의 문자들을 하나의 문자열로 합치면 되겠죠?

class Solution:
    def toLowerCase(self, s: str) -> str:
        output = []
        for ch in s:
            if "A" <= ch <= "Z":
                output.append(chr(ord(ch) + 32))
            else:
                output.append(ch)
        return "".join(output)

이 풀이의 시간 복잡도는 O(n)입니다. 문자열의 각 문자를 한 번씩 확인하고, 마지막에 문자들을 합치는 작업도 문자열의 길이에 비례하는 시간이 걸리기 때문입니다.

공간 복잡도도 O(n)입니다. 변환된 문자들을 저장하는 리스트와 반환할 문자열의 크기가 모두 입력 문자열의 길이에 비례하기 때문입니다.

마치면서

이상으로 내장 메서드를 사용하는 방법과 문자 코드를 이용하는 방법으로 문제를 풀어보았습니다. 간단한 문제지만 직접 구현해보면 문자와 숫자 사이의 관계를 이해하는 데 도움이 됩니다.

문자 코드를 활용하는 다른 문제를 풀어보고 싶으시다면 Caesar Cipher 문제도 함께 살펴보세요.