[파이썬] 프로그래머스 LV1 숫자문자열과 영단어

프로그래머스 숫자 문자열과 영단어

나의 풀이

바로 나왔던 풀이

def solution(s):
    s = s.replace('zero','0')
    s = s.replace('one','1')
    s = s.replace('two','2')
    s = s.replace('three','3')
    s = s.replace('four','4')
    s = s.replace('five','5')
    s = s.replace('six','6')
    s = s.replace('seven','7')
    s = s.replace('eight','8')
    s = s.replace('nine','9')
    return int(s)

성능 고민 없이 바로 생각난 풀이이다.
lv0에서 비슷하지만 좀더 어려운게 있었는데..🤔

딕셔너리를 이용해 보기

def solution(s):
    thisdict= {
        'zero':'0',
        'one':'1',
        'two':'2',
        'three':'3',
        'four':'4',
        'five':'5',
        'six':'6',
        'seven':'7',
        'eight':'8',
        'nine':'9'
    }
    for x in thisdict.keys():
        if x in s:
            s = s.replace(x,thisdict[x])
    return int(s)

다른 사람 풀이에서 같은 방식으로 푼 코드의 댓글 중..

이건 O(N)처럼 보이지만 replace가 그 자체로 O(N) 이상이고 심지어는 O(N^2)까지도 가능한 메소드라 최악의 경우 O(N^3)까지 나옵니다. 풀이는 짧지만 시간 복잡도는 많이 커집니다.

따라서 replace를 쓰면 딕셔너리를 쓰는 의미가 없음

#성능 분석에서 쓴 방법으로 해보기..

다른 사람 풀이

비슷한 방식을

성능 비교

            첫 시도                   dictionary
테스트 1 〉	통과 (0.01ms, 10.3MB)	통과 (0.02ms, 10.5MB)
테스트 2 〉	통과 (0.02ms, 10.5MB)	통과 (0.02ms, 10.4MB)
테스트 3 〉	통과 (0.01ms, 10.5MB)	통과 (0.02ms, 10.3MB)
테스트 4 〉	통과 (0.02ms, 10.4MB)	통과 (0.02ms, 10.3MB)
테스트 5 〉	통과 (0.02ms, 10.5MB)	통과 (0.02ms, 10.3MB)
테스트 6 〉	통과 (0.02ms, 10.4MB)	통과 (0.02ms, 10.4MB)
테스트 7 〉	통과 (0.02ms, 10.3MB)	통과 (0.02ms, 10.4MB)
테스트 8 〉	통과 (0.02ms, 10.5MB)	통과 (0.02ms, 10.4MB)
테스트 9 〉	통과 (0.03ms, 10.4MB)	통과 (0.02ms, 10.4MB)
테스트 10 〉	통과 (0.02ms, 10.3MB)	통과 (0.02ms, 10.3MB)

• dictionary가 해쉬를 써서 빠르다고는 하지만 이번 문제에서는 문자열 replace를 주로 쓰기 때문에 그런 강점이 잘 드러나지는 않았던 것 같다
• 모두 숫자로만 이루어진 인풋의 경우 바로 리턴을 가능하게 하는 것도 좋겠다.
• for loop으로 하나하나 문자를 체크하면서 딕셔너리 인덱스와 매칭 될때까지 문자를 하나씩 더 읽으면서 slice하고 매칭 되면 새로운 지역변수에 그 인덱스의 value를 더해주고, 문자열을 읽는 인덱스를 아직 읽지 않은 그 다음 문자로 업데이트. 인풋 문자열 끝에 도달할 때까지 해주는 방법이 replace를 보다 효율이 좋을 것 같다.
  • 왜냐면.. 인풋스트링을 한번만 읽게되고 O(n), 매칭 되는 키가 있는지는 딕셔너리로 확인하기 때문에 O(1), 또 그 value를 갖고 오는데 O(1) 이라 O(n)에 맞출 수 있을 것 같음..