1주차 곱하거나 더하기, 반복되지 않는 문자

곱하거나 더하기

input에 있는 값을 적적히 더하거나 곱하여 가장 큰 수를 만들어라가 문제이다.

이 문제를 해결하기 위해서는 먼저 더하기보다 곱하였을 때가 무조건 큰가? 라는 것이다.

가장 쉬운 예로 아무리 큰 숫자일지라도 0을 곱해버린다면 0이 되는 점과

예를들어 4 * 1일 경우 4이지만 4 + 1 일경우 5가 된다. 즉 1이라는 숫자가 온다면 곱하는 것 보다 더하는 것이 더 값이 커질 수 있다는 점이다. 아래는 내가 작성한 코드이다.

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


def find_max_plus_or_multiply(array):
    num = 0
    for i in array:
        if i * num == num or i * num == 0:
            num += i
            continue
        num *= i
    return num


result = find_max_plus_or_multiply(input)
print(result)

 

먼저 for문을 돌리면서 i와 현재 있는 숫자를 곱했을 때 같거나(즉 i가 1이라는 뜻) 0이면(i or num이 0이라는 뜻) i를 num에 더하고 그렇지 않으면 num과 곱해주는 방식으로 풀어보았다.

 

 

반복되지 않는 문자

이 문제는 input에 있는 문자열 중에서 반복되지 않는 문자(c,d)중에 먼저 적힌 문자(d)를 출력하라 단

반복되지 않는 문자가 없다면 '_'를 출력하라 였다.

input = "abadabac"

def find_not_repeating_character(string):
    for fix_str in string:
        cnt = 0
        for iter in string:
            if fix_str == iter:
                cnt += 1
            if cnt == 2:
                break
        if cnt == 1:
            return fix_str
    return '_'


result = find_not_repeating_character(input)
print(result)

선생님의 풀이 방법은 전에 최빈값 구했던 것과 마찬가지로 26개 길이의 배열을 만든 후 아스키코드를 활용하여 알파벳의 빈도값을 담은 뒤에 반복되지 않는 것은 빈도값이 1이니까

요소의 값이 1인 인덱스를 따로 모아 모은 뒤 97을 더하여 다시 한번 아스키코드를 사용해 숫자를 문자로 반환하는 chr함수를 사용해 겹치지 않는 문자들이 담긴  리스트를 만들었고

for반복문을 사용해서 현재의 값이 리스트 안에 있다면 그 현재의 값을 반환하는 식으로 문제를 해결하셨다.

 

나의 풀이는 먼저 2개의 for를 돌리면서 'a'를 "abadabac"와 비교하면서 겹치는 횟수를 cnt로 표시하였고 2가 됬다는 뜻은 겹친다는 뜻이므로 break를 통해 탈출하였다. 그리고 1이라는 뜻은 반복되지 않았다는 의미이므로 fix_str를 바로 리턴해주는 방식이다. 만약 반복되는 문자가 없다면 이중 for문이 전부 끝나게 되므로 '_'를 반환하는 식을 짜보았다.

 

나의 풀이의 시간복잡도는 N*2이고 선생님의 시간복잡도는 N이다. 따라서 선생님의 풀이가 좀 더 효율적이라고 할 수 있다.

 

소수 구하기

input = 20

#2는 예외이므로..


def find_prime_list_under_number(number):
    primes = [2]
    for i in range(3, number+1):
        for k in primes:
            if i % k == 0:
                break
            if k == primes[-1]:
                primes.append(i)
    return primes


result = find_prime_list_under_number(input)
print(result)

 

야매로 풀었는데 일단 2는 유일한 짝수이므로 예외처리가 필요하다. 따라서 그냥 prims의 list에 두었다.

소수는 소수로 나누었을 때 안나누어 떨어지면 소수이다.   이중 for 반복문을 돌면서 i가 prims에 있는 값들 중 나뉘면 break로 빠져나가 다음 반복을 돌고 안나뉘면 prims를 전부다 돈다. 전부 다 돌았다는 뜻은 소수로 나누었을 때 안나누어 떨어진 것이므로 pimes에 추가해주는 식으로 하였다. 시간복잡도도 안좋고 뭔가 정석적으로 푼 것 같진 않은데 일단 코린이니까.. 소수는 여기까지만