1주차_알고리즘 더 풀어보기

Q. 다음과 같이 0 혹은 양의 정수로만 이루어진 배열이 있을 때, 왼쪽부터 오른쪽으로 하나씩 모든 숫자를 확인하며 숫자 사이에 '✕' 혹은 '+' 연산자를 넣어 결과적으로 가장 큰 수를 구하는 프로그램을 작성하시오. 단, '+' 보다 '✕' 를 먼저 계산하는 일반적인 방식과는 달리, 모든 연산은 왼쪽에서 순서대로 이루어진다.

 

def find_max_plus_or_multiply(array):
    multiply_sum = 0
    for number in array:
        if number <= 1 or multiply_sum <= 1:
            multiply_sum += number
        else:
            multiply_sum *= number
    return multiply_sum


result = find_max_plus_or_multiply
print("정답 = 728 현재 풀이 값 =", result([0,3,5,6,1,2,4]))
print("정답 = 8820 현재 풀이 값 =", result([3,2,1,5,9,7,4]))
print("정답 = 270 현재 풀이 값 =", result([1,1,1,3,3,2,5]))

1 혹은 0 같은 경우는 곱하는 것보다 더하는 게 좋다!

3 x 1 = 3 보다, 3 + 1 = 4 를 하는 게 더 큰 수를 가질 수 있다!

총 계산된 값을 구하기 위한 합계 변수를 두고 이제 반복문을 돌면서 합계 변수에 더하거나 곱해 나갈텐테, 마찬가지로 합계가 1 이하일 때 더하는 게 좋다. (1 x 2 보다는 1 + 2 가 더 크기 때문!)

 

합계와 현재 숫자가 1보다 작거나 같다면 더하고 그 외에는 전부 곱하자!

 

시간복잡도는 O(N)

 

 

 

---

Q. 다음과 같이 영어로 되어 있는 문자열이 있을 때, 이 문자열에서 반복되지 않는 첫번째 문자를 반환하시오. 만약 그런 문자가 없다면 _ 를 반환하시오.

 

def find_not_repeating_first_character(string):
    alphabet_occurrence_array = [0] * 26

    for char in string:
        if not char.isalpha():
            continue
        arr_index = ord(char) - ord("a")
        alphabet_occurrence_array[arr_index] += 1

    not_repeating_character_array = []
    for index in range(len(alphabet_occurrence_array)):
        alphabet_occurrence = alphabet_occurrence_array[index]

        if alphabet_occurrence == 1:
            not_repeating_character_array.append(chr(index + ord("a")))

    for char in string:
        if char in not_repeating_character_array:
            return char

    return "_"


result = find_not_repeating_first_character
print("정답 = d 현재 풀이 값 =", result("abadabac"))
print("정답 = c 현재 풀이 값 =", result("aabbcddd"))
print("정답 =_ 현재 풀이 값 =", result("aaaaaaaa"))

반복되는지 아닌지를 확인하기 위해서는, 각 알파벳 별로 출현하는 횟수를 저장해 한다.

alphabet_occurrence_array 배열에 각 빈도수를 저장하고, 그 배열을 돌면서 not_repeating_character_array 라는 배열에 반복되지 않는 문자를 다 집어넣는다.

그리고 다시 한 번 문자열을 돌면서 해당 문자가 발견된다면 그 값을 반환!

이 때, 1의 빈도수를 가진 인덱스를 알파벳으로 변환해서 not_repeating_character_array 에 저장하면 됩니다. 그러면 not_repeating_character_array 에는 ["c", "d"]가 담기게 되는데, 그 중 첫 번째인 "c" 를 반환하면 될까요? 그렇지 않습니다! 입력된 문자열 내에서 반복되지 않는 첫번째 문자를 찾아서 반환해줘야 하기 때문에 string 을 다시 반복해서 돌면서 첫 번째 반복되지 않는 문자를 찾아 반환해주시면 됩니다! 이를 이용해서 해결해봅시다!

 

시간복잡도는 얘도 역시 O(N)