곱하기 or 더하기, 반복되지 않는 숫자

[곱하기 or 더하기]

 

문제설명

0 혹은 양의 정수로만 이루어진 배열이 있을 때, 왼쪽부터 오른쪽으로 하나씩 모든 숫자를 확인하며 숫자 사이에 '✕' 혹은 '+' 연산자를 넣어 결과적으로 가장 큰 수를 구하는 프로그램을 작성하시오.

 

단, '+' 보다 '✕' 를 먼저 계산하는 일반적인 방식과는 달리, 모든 연산은 왼쪽에서 순서대로 이루어진다.

 

의사코드(수도코드)

- 총합을 구하는 변수 -> sum = 0이 필요

- 반복문을 돌면서 요소를 하나씩 빼온다.

- sum에 요소를 더하거나 곱할 때 sum이 더 큰 연산을 실행한다.

(0, 1에는 무조건 + 연산을 해야 한다.)

(0, 1에 곱하기 연산을 진행 하는 것보다 더하기 연산을 하는 게 sum이 더 크기 때문에)

- 총합을 return 한다.

 

문제 풀이

input = [0, 3, 5, 6, 1, 2, 4]

def find_max_plus_or_multiply(array):

    # 총합을 구하는 변수 -> sum = 0 필요
    sum = 0

    # 반복문을 돌면서 요소를 하나씩 빼온다.
    for num in array: ## array의 길이만큼 아래의 연산을 진행
        # sum에 요소를 더하거나 곱할 때 sum이 더 큰 연산을 실행한다.

        # 0, 1에는 무조건 + 연산을 해야 한다.
        # 0, 1에 곱하기 연산을 진행하는 것보다 더하기 연산을 하는 게 sum이 더 크기 때문에
        if sum <= 1 or num <= 1:
            sum += num
        else:
            sum *= num

    # 총합을 return 한다.
    return sum

result = find_max_plus_or_multiply(input)
print(result)

-> 이 함수의 시간 복잡도는 O(N)만큼의 시간 복잡도를 가진다.

---

[반복되지 않는 숫자]

 

문제설명

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

 

의사코드(수도코드)

- 해당 문자가 몇번 나왔는 지 담을 배열 -> indexArr = []

- for문을 사용해서 문자열에 문자를 하나씩 뽑아온다.

- for문을 한번 더 사용해서 문자와 문자를 비교한다.

- if문을 사용해서 같은 문자면 배열에 +1을 한다.

- 문자가 없다면 _를 반환한다.

- 배열에서 값이 0인 요소 중에 첫번째 요소를 return 한다.

 

선생님의 문제 풀이

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

    for char in string: ## N
        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: ## N
        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"))

이 함수의 시간 복잡도는 N + N = 2N 결국 O(N)의 시간 복잡도를 가진다.