Level 1 숫자 문자열과 영단어<2021 카카오 인턴십> Python 3

https://programmers.co.kr/learn/courses/30/lessons/81301

코딩테스트 연습 - 숫자 문자열과 영단어

 

최종 코드

• GitHub -> https://github.com/hwayeon351/Programmers-Algorithms/blob/main/level1_숫자문자열과영단어.py

GitHub - hwayeon351/Programmers-Algorithms: 프로그래머스 알고리즘 소스 코드 모음

def solution(s):
    answer = ""
    number = {"zero": "0", "one": "1", "two": "2", "three": "3", "four": "4", "five": "5", "six": "6", "seven": "7", "eight": "8", "nine": "9"}
    num = ""
    for c in s:
        if c.isdigit():
            answer += c
        else:
            num += c
            if num in number.keys():
                answer += number[num]
                num = ""
    return int(answer)

---

• GitHub -> https://github.com/hwayeon351/Programmers-Algorithms/blob/main/level1_숫자문자열과영단어_2.py

GitHub - hwayeon351/Programmers-Algorithms: 프로그래머스 알고리즘 소스 코드 모음

def solution(s):
    number = {"zero": "0", "one": "1", "two": "2", "three": "3", "four": "4", "five": "5", "six": "6", "seven": "7", "eight": "8", "nine": "9"}
    for key, value in number.items():
        s = s.replace(key, value)
    return int(s)

---

풀이 과정

풀이 시간 14분

1.

def solution(s):
    answer = ""
    number = {"zero": "0", "one": "1", "two": "2", "three": "3", "four": "4", "five": "5", "six": "6", "seven": "7", "eight": "8", "nine": "9"}
    num = ""
    #문자열을 하나씩 체크
    for c in s:
    	#숫자인 경우, 바로 answer에 추가한다
        if c.isdigit():
            answer += c
        #문자인 경우,
        else:
        	#num에 c를 추가한다
            num += c
            #num이 number 딕셔너리 key에 존재하는 경우, 숫자로 바꾸고 answer에 추가한다
            if num in number.keys():
                answer += number[num]
                num = ""
    #문자열로 되어있는 answer을 int형으로 바꾼다
    return int(answer)
#시간복잡도 = T(len(s)) -> O(n), 공간복잡도 = O(n)

 

 

2.

 문자열 내장함수 replace의 시간복잡도는 O(문자열의 길이 * (교체할 문자열의 길이 + 교체되는 문자열의 길이/교체할 문자열의 길이))이다.

 즉, str.replace(a, b)라면 O(len(str) * (len(a) + len(b)/len(a)))이다.

replace 함수는 문자열 str의 길이만큼 전체적으로 문자열을 하나씩 탐색하고 교체할 문자열의 길이만큼 이전값을 탐색해서 교체해야하는 문자열인지 아닌지를 판별한다.

교체해야 하는 경우, 교체되는 문자열의 길이에 따라 추가 연산이 필요하다.

교체되는 문자열의 길이가 교체할 문자열의 길이와 같은 경우, 할당된 길이만큼(교체할 문자열의 길이만큼)만 연산을 수행하면 되기 때문에 O(len(b)/len(a)) = O(1)로 상수의 시간이 소요된다.

교체되는 문자열의 길이가 교체할 문자열의 길이보다 큰 경우, 초과된 길이만큼 새 위치를 만들고 교체가 이뤄지므로 O(len(b)/len(a))만큼의 추가 연산이 소요된다. 따라서 이 경우가 최악의 경우다.

 

 이 문제는 replace를 모든 number의 item에 관하여 수행해야 하므로,  O(10*(len(s) * (1 + len(key)/1)))의 시간이 소요된다.

최악의 경우를 생각해보면, s = 50, len(key) = 5일 때, 10*(1+5/1) = 60번의 연산이 소요된다.

def solution(s):
    number = {"zero": "0", "one": "1", "two": "2", "three": "3", "four": "4", "five": "5", "six": "6", "seven": "7", "eight": "8", "nine": "9"}
    for key, value in number.items():
        s = s.replace(key, value)
    return int(s)
#시간복잡도 = O(n), 공간복잡도 = O(n)

---

참고

• 2. 거리 두기 확인하기 -> https://hwayomingdlog.tistory.com/146

Level 2 거리두기 확인하기 <2021 카카오 인턴십> Python 3

 

• 3. 표 편집 -> 2021.08.27 - [코테 노트/프로그래머스] - Level 3 표 편집 <2021 카카오 인턴십> Python 3

Level 3 표 편집 <2021 카카오 인턴십> Python 3

• 4. 미로 탈출
• 5. 시험장 나누기