코딩 인터뷰 완전 분석 1.3 파이썬3 풀이

문제

1.3 URL화: 문자열에 들어 있는 모든 공백을 ‘%20’으로 바꿔 주는 메서드를 작성하라. 최종적으로 모든 문자를 다 담을 수 있을 만큼 충분한 공간이 이미 확보되어 있으며 문자열의 최종 길이가 함께 주어진다고 가정해도 된다(자바로 구현한다면 배열 안에서 작업할 수 있도록 문자 배열(character array)을 이용하길 바란다).

 

입력: “Mr John Smith”, 13

출력: “Mr%20John%20Smith”

 

제한 사항

1. 공백은 스페이스 몇 개이든 상관이 없는가?
2. 충분한 공간이 이미 확보 -> 이게 무슨 말인지?, 공간복잡도를 O(1)로 풀라는 이야기인가?, 공간을 사용해도 된다는 이야기인가?
3. 최종 길이가 함께 주어진다.

 

아이디어1

문자열을 하나하나 검사한다.

새로운 문자 변수에 공백이 아닐시 기존 문자를 추가하고, 공백이면 ‘%20’을 추가한다.

 

공간복잡도

O(1)

 

시간복잡도

O(n)

 

아이디어2

길이를 왜 주었을까? 길이를 어떻게 이용할까?

모르겠다.

 

테스트케이스

• ‘     ‘
• ‘ I love you’
• ‘ I love you ‘
• ‘I love you ‘
• ‘ a’
• ‘a’
• ‘a ‘
• ‘asdf   aasdf’

 

코드

def replace_space_to_char(origin_url):
    result_url = ''

    for char in origin_url:
        if char == ' ':
            result_url += '%20'
        else:
            result_url += char

    return result_url


print(replace_space_to_char('     '))
print(replace_space_to_char(' I love you'))
print(replace_space_to_char(' I love you '))
print(replace_space_to_char('I love you '))
print(replace_space_to_char(' a'))
print(replace_space_to_char('a'))
print(replace_space_to_char('a '))
print(replace_space_to_char('asdf   aasdf'))

 

힌트

#53 문자열 끝에서 시작해서 앞으로 읽어 나가면서 수정하는 것이 보통 가장 쉽다.

#118 필요한 공백을 알아야 할지도 모른다. 하나씩 세어 볼 수 있는가?

 

해답

자바로 풀어서 문자열 조작이 조금 복잡해 보인다. 파이썬이 좋긴 좋다.