코딩 푸는 남자

안녕하세요, 코딩 푸는 남자 입니다.

​

오늘은 Programmers Level0 문제 중, "다음에 올 숫자" 문제를 풀어 보겠습니다.

​

우선 문제를 이해해 보겠습니다.

common은 정수 등비 수열 혹은 정수 등차 수열중 한가지로 이루어져 있습니다.

common이 [1, 2, 3, 4] 인 경우, 등차 수열로, 4 다음에 올 값을 예상해 보면 5 입니다.

common이 [2, 4, 8] 인 경우, 등비 수열로, 8 다음에 올 값은 16 입니다.

이번 문제는 주어진 common 배열이, 등차 수열인지, 등비 수열인지 알아보고, 마지막 인자 다음에 올 값을 return 하는 문제 입니다.

오홋! Level1을 한번 찍고 와서인지, 뭔가 쉽게 풀수 있을거 같은 느낌적인 느낌이 듭니다. 

제가 푼 방식은 다음과 같습니다.

def solution(common):
    answer = 0
    
    if( (common[1] - common[0]) == (common[2] - common[1]) ):
        answer = common[len(common) - 1] + (common[1] - common[0])
    elif( (common[1] / common[0]) == (common[2] / common[1])):
        answer = common[len(common) - 1] * (common[1] / common[0])
    else:
        pass
    
    
    return answer

이 코드로 코딩 테스트를 통과 할수 있지만, 잠재적인 문제가 있습니다.

과연 무엇일까요?

10/3과 10//3의 차이점은 무엇일까요?

10/3은 float 객체를 반환하며, 결과는 3.3333... 입니다.

10//3은 int 객체를 반환하며, 따라서 결과는 3 입니다.

common은 정수형 배열이므로, / 보다는 // 를 사용하여 int 객체를 반환하는 것이 더 좋을것 같습니다.

def solution(common):
    answer = 0
    
    if( (common[1] - common[0]) == (common[2] - common[1]) ):
        answer = common[len(common) - 1] + (common[1] - common[0])
    elif( (common[1] // common[0]) == (common[2] // common[1])): #/를 //로 변경
        answer = common[len(common) - 1] * (common[1] / common[0])
    else:
        pass
    

    return answer

오늘은 "다음에 올 숫자"를 풀어 보았습니다.

감사합니다.

안녕하세요 코딩 푸는 남자 입니다.

이번에 Level0 두개 풀고 쓸데없이 생긴 자신감이 생긴것 같습니다.

정신 차리라는 의미에서, 현실 파악용 Level1에 한번 도전해 보겠습니다. 

우선 문제를 이해해 보겠습니다. 문제는 다음과 같습니다.

우선 이해를 위해, player와 동일한 내용을 result에 저장했다고 가정 하겠습니다.

kai가 호출 되었기 때문에, poe와 kai의 자리가 바뀌게 됩니다.

다시 kai가 호출 되었네요? 이번에는 soe와 kai가 자리를 바꾸게 됩니다.

이제 mine이 호출 되었네요? 자 poe와 mine의 위치를 바꿔 줍니다.(영차영차)

끝으로, mine이 호출 되었기 때문에, soe와 mine이 위치를 바꾸고 최종 결과가 기록 됩니다.

음... 고민을 조금 해 보다가, index() method를 통해 문제를 풀어 보기로 합니다.

index() method는 index 함수에 전달되는 인자와 일치하는 list의 index를 리턴하게 됩니다.

즉, player.index("kai")를 하는 경우, 3을 리턴 하게 되고, list[3]과 list[2]을 바꾸면 순위를 바꿀수 있습니다.

해당 알고리즘은 다음과 같이 코딩 하였습니다.

def solution(players, callings):
    answer = []
    
    # 1. find calling data in callings
    for call in callings:
        find_index = players.index(call)
        swich_value = players[find_index - 1]
        players[find_index - 1] = call
        players[find_index] = swich_value
        
    answer = players
    
    return answer

Level1도 별거 아니네? 잠시 건방을 떨어 보았습니다.

실행시간 초과가 떳습니다...

문제의 원흉을 이리저리 찾아보다가 문제는 바로!! index() 가 아니라 그렇게 알고리즘짠 나 라는걸 알게 되었습니다.

Index를 사용하는 경우 발생할수 있는 문제점을 표현하기 위해, player의 가장 마지막인 mine만을 호출하는 형태로 변경해 보겠습니다.

첫번째 mine을 찾기위해, player.index("mine")을 호출한 경우, player의 list 0(처음)부터 n-1(끝)까지 search를 하게 됩니다.

다시 두번째 mine을 찾기 위해, player.index("mine")을 호출한 경우 역시, player의 list 0(처음)부터 n-1(끝)까지 search를 다시 하게 됩니다.

예제는 그래도 n==4였기에 다행 입니다.

만약 n == 10000이라면? 100000이라면? 10000000이라면?

n의 값에 따라 실행 속도가 증가하게 되며, 이로 인해 시간 복잡도에서 통과 하지 못했습니다.

잠시 거만했던 과거를 후회하며, 다시 고민해 보았습니다.

10분, 20분, 1시간...

아이가 놀아달라 칭얼대지만, 안들리는척 버텨 보았습니다.

아내가 뒤통수에 레이저를 쏘는것이 느껴지지만, chatGPT인것 마냥 아무것도 못느끼는 사람인척 해 보았습니다. 

때로는 미간에 주름을 힘껏 주며, "나 지금 큰일하고 있어" 라고 속으로 혼자 어필해 보았습니다.

그래도 나름 한시간 정도 후에 좋은 아이디어가 생각났고, 다음과 같이 코딩해 보았습니다.

def solution(players, callings):
    answer = []
    
    index_dic = {}    
    
    for i in range(len(players)):
        index_dic[players[i]] = i
    
    for call in callings:
        if(call in index_dic):
            find_index = index_dic[call]
        else:
            pass
        
        swich_value = players[find_index - 1]
        players[find_index - 1] = call
        players[find_index] = swich_value
        
        index_dic[call] = find_index - 1
        index_dic[swich_value] = find_index
        
    answer = players
    
    return answer

이번에는 데이터 입력 양 및 worst case에 따라 시간 복잡도가 증가하지 않도록 하기 위해 dictionary를 이용해 보았습니다.

우선 for loop를 돌면서 player에 있는 값과 순서를 dictionary에 저장해 두었습니다.

1. callings의 첫번째 data인 kai를 dictionary에서 찾아서

2. 현재 player중 3에 위치해 있다는걸 파악했습니다.

3. 그런다음 player[3]과 바로 앞인 player[2]의 위치를 바꾸었고

4. 마지막으로 dictionary에서도 해당하는 위치를 바꿨습니다.

다행히 이렇게 하면 모든 테스트가 통과 되었습니다.

이 경우, n값이 크게 들어와도, for loop는 한번만 수행하고, 이후 부터는 map 방식인 dictionary를 사용하여,

이전 방식보다는 실행 시간에서 이점을 본것 같습니다.

그럼 오늘은 이만 마치겠습니다.

안녕하세요, 코딩 푸는 남자 입니다.

​

오늘은 Programmers Level0 문제 중, 영어가 싫어요 문제를 풀어 보겠습니다.

​

우선 문제를 이해해 보겠습니다.

예를들어 입력값이 "onefourzerosixseven"인 경우, result로 정수 14067을 만들어야 합니다.

​

해당 문제를 풀기 위해 우선 저는 영어 숫자 문자열을 숫자 문자열로 대치하기 위해

다음 list를 만들었습니다.

num_string = [ ['zero', '0'], ['one', '1'], ['two', '2'], ['three', '3'], ['four', '4'], 
                    ['five', '5'], ['six', '6'], ['seven', '7'], ['eight', '8'], ['nine', '9'] ]

그런 다음, startswith()함수를 통해 num_string과 일치하는 값이 있는지 찾아 보겠습니다.

numbers가 'zero'로 시작하지 않기 때문에 첫번째 시도는 False 입니다.

​

이제 다음 num_string을 찾아 보겠습니다.

numbers가 one으로 시작하기 때문에, True입니다.

이 경우, 'one'에 해당하는 '1'을 answer_str에 저장 하고, numbers의 'one'은 제거 합니다.

​

numbers 'fourzerosixseven'로 다시 num_string의 처음 부터 반복 합니다.

four를 찾고나면, numbers = 'zerosixseven'이 되고, answer_str = '14'가 됩니다.

​

이렇게 반복 하다 보면, numbers=''가 되고 answer_str='14067'이 됩니다.

​

그리고 마지막으로 문자열인 answer_str을 int()함수를 통해 상수로 변환 하면 됩니다.

answer = int(answer_str)

지금까지 작성한 항목을 코딩하면 다음과 같습니다.

def solution(numbers):
    answer = 0
    answer_str = ''
    num_string = [ ['zero', '0'], ['one', '1'], ['two', '2'], ['three', '3'], ['four', '4'], 
                    ['five', '5'], ['six', '6'], ['seven', '7'], ['eight', '8'], ['nine', '9'] ]
    while len(numbers): 
        for i in num_string:
            if numbers.startswith(i[0]):
                answer_str += i[1]
                numbers = numbers[len(i[0]): ]
    
    answer = int(answer_str)
    
    return answer

저는 이렇게 풀었는데요, 풀고 나서 고수분들의 solution을 보니, 제가 참 무식하게 풀었다는 것을 깨닫게 되었습니다.ㅠㅠ

고수분들의 solution중, 제가 공유 드리고 싶은 solution이 하나 있어 같이 공유 드릴까 합니다.

​

우선 고수분의 solution은 다음과 같습니다.

def solution(numbers):
    for num, eng in enumerate(["zero", "one", "two", "three", "four",
                               "five", "six", "seven", "eight", "nine"]):
        numbers = numbers.replace(eng, str(num))
    return int(numbers)

해당 코드가 동작하는 원리는 다음과 같습니다.

​

다음과 같이 enumerate를 for loop로 돌리면, num 에는 0,1,2,... 이 eng 에는 enumerate의 인자가 하나씩 반환 됩니다.

for num, eng in enumerate(["zero", "one", "two", "three", "four",
                               "five", "six", "seven", "eight", "nine"]):

즉 첫번째 loop에서 num = 0, eng = "zero"가 반환 됩니다.

이 인자를 가지고 replace() 함수를 통해 값을 변환 해 봅니다.

이제 num = 1, eng = "one"으로 replace()를 동작 시키 겠습니다.

어떠신가요?

제가 작성한 코드보다 훨씬 간결하고, 깔끔 하네요.

​

알고리즘이란 어떤식으로 접근하느냐에 따라 코드의 간결성, 가독성, 시간 복잡도, 공간 복잡도 등

다양한 방면에서 보다 나은 효율성을 찾을수 있는 매력적인 부분 인것 같습니다.

​

추운 날씨 감기 조심하시고, 오늘 포스팅은 여기서 마치도록 하겠습니다.

안녕하세요, 코딩 푸는 남자 입니다.

​

오늘은 Programmers Level0 문제 중, 순서쌍의 개수 문제를 풀어 보겠습니다.

​

우선은 문제를 이해해 보겠습니다.

예를 들어 입력값 n이 10인 경우,

곱이 10이 되는 순서쌍은 1* 10, 2 * 5, 5 * 2, 10 * 1로 총 4개 이므로, 정답은 4 입니다.

​

해당 문제를 풀기 위해 저는 우선 나머지 연산자를 이용해 보기로 했습니다.

즉 i를 1부터 n까지 반복하면서 나머지가 0인 경우, 값을 증가 시키는 방식을 사용 하였습니다.

해당 알고리즘을 코딩한 결과는 다음과 같습니다.

def solution(n):
    answer = 0
    for i in range(n): #0부터 n-1까지 반복
        if(n%(i+1) == 0): #i+1을 해줌으로써, 1부터 n까지 대입
            answer += 1
    return answer

그럼 첫번째 포스팅을 마치겠습니다. 감사합니다.