문제출처

문제

A zero-indexed array A consisting of N different integers is given. The array contains integers in the range [1..(N + 1)], which means that exactly one element is missing.

Your goal is to find that missing element.

Write a function:

def solution(A)
that, given a zero-indexed array A, returns the value of the missing element.

For example, given array A such that:

  A[0] = 2
  A[1] = 3
  A[2] = 1
  A[3] = 5
the function should return 4, as it is the missing element.

Assume that:

N is an integer within the range [0..100,000];
the elements of A are all distinct;
each element of array A is an integer within the range [1..(N + 1)].
Complexity:

expected worst-case time complexity is O(N);
expected worst-case space complexity is O(1), beyond input storage (not counting the storage required for input arguments).
Elements of input arrays can be modified.

풀이코드

• Detected time complexity: O(N) or O(N * log(N))

def solution(A):
    li = [0] * (len(A) + 1)
    for i in A:
        li[i-1] = 1  
    return li.index(0) + 1

다른사람 코드

• 와! 이렇게 쉬운 방법이 있었다니..

def solution(A):
  return sum (range(len(A)+2)) - sum(A)

문제출처

문제

A small frog wants to get to the other side of the road. The frog is currently located at position X and wants to get to a position greater than or equal to Y. The small frog always jumps a fixed distance, D.

Count the minimal number of jumps that the small frog must perform to reach its target.

Write a function:

def solution(X, Y, D)

that, given three integers X, Y and D, returns the minimal number of jumps from position X to a position equal to or greater than Y.

For example, given:

  X = 10
  Y = 85
  D = 30
the function should return 3, because the frog will be positioned as follows:

after the first jump, at position 10 + 30 = 40
after the second jump, at position 10 + 30 + 30 = 70
after the third jump, at position 10 + 30 + 30 + 30 = 100
Assume that:

X, Y and D are integers within the range [1..1,000,000,000];
X ≤ Y.
Complexity:

expected worst-case time complexity is O(1);
expected worst-case space complexity is O(1).

풀이코드

• Detected time complexity: O(1)

def solution(X, Y, D):
    return (Y - X) // D if (Y - X) % D == 0 else (Y - X) // D + 1

문제출처

문제

You are given N counters, initially set to 0, and you have two possible operations on them:

increase(X) − counter X is increased by 1,
max counter − all counters are set to the maximum value of any counter.
A non-empty zero-indexed array A of M integers is given. This array represents consecutive operations:

if A[K] = X, such that 1 ≤ X ≤ N, then operation K is increase(X),
if A[K] = N + 1 then operation K is max counter.
For example, given integer N = 5 and array A such that:

    A[0] = 3
    A[1] = 4
    A[2] = 4
    A[3] = 6
    A[4] = 1
    A[5] = 4
    A[6] = 4
the values of the counters after each consecutive operation will be:

    (0, 0, 1, 0, 0)
    (0, 0, 1, 1, 0)
    (0, 0, 1, 2, 0)
    (2, 2, 2, 2, 2)
    (3, 2, 2, 2, 2)
    (3, 2, 2, 3, 2)
    (3, 2, 2, 4, 2)
The goal is to calculate the value of every counter after all operations.

Write a function:

def solution(N, A)
that, given an integer N and a non-empty zero-indexed array A consisting of M integers, returns a sequence of integers representing the values of the counters.

The sequence should be returned as:

a structure Results (in C), or
a vector of integers (in C++), or
a record Results (in Pascal), or
an array of integers (in any other programming language).
For example, given:

    A[0] = 3
    A[1] = 4
    A[2] = 4
    A[3] = 6
    A[4] = 1
    A[5] = 4
    A[6] = 4
the function should return [3, 2, 2, 4, 2], as explained above.

Assume that:

N and M are integers within the range [1..100,000];
each element of array A is an integer within the range [1..N + 1].
Complexity:

expected worst-case time complexity is O(N+M);
expected worst-case space complexity is O(N),
beyond input storage (not counting the storage required for input arguments).
Elements of input arrays can be modified.

풀이코드

def solution(N, A):
    result = [0] * N
    for i in A:
        if 1 <= i <= N:
            result[i-1] += 1
        else:
            result = [max(result)] * N # O(N)
    return result

다른사람 코드

def solution(N, A):

    counters = N * [0]
    next_max_counter =  max_counter = 0

    for oper in A:
        if oper <= N:
            current_counter = counters[oper-1] = max(counters[oper-1] +1, max_counter+1)
            next_max_counter = max(current_counter, next_max_counter)
        else:
            max_counter = next_max_counter

    return [c if c > max_counter else max_counter for c in counters]

문제출처

문제

A non-empty zero-indexed array A consisting of N integers is given. The array contains an odd number of elements, and each element of the array can be paired with another element that has the same value, except for one element that is left unpaired.

For example, in array A such that:

A[0] = 9 A[1] = 3 A[2] = 9 A[3] = 3 A[4] = 9 A[5] = 7 A[6] = 9 the elements at indexes 0 and 2 have value 9, the elements at indexes 1 and 3 have value 3, the elements at indexes 4 and 6 have value 9, the element at index 5 has value 7 and is unpaired. Write a function:

def solution(A)

that, given an array A consisting of N integers fulfilling the above conditions, returns the value of the unpaired element.

For example, given array A such that:

A[0] = 9 A[1] = 3 A[2] = 9 A[3] = 3 A[4] = 9 A[5] = 7 A[6] = 9 the function should return 7, as explained in the example above.

Assume that:

N is an odd integer within the range [1..1,000,000]; each element of array A is an integer within the range [1..1,000,000,000]; all but one of the values in A occur an even number of times. Complexity:

expected worst-case time complexity is O(N); expected worst-case space complexity is O(1),

beyond input storage (not counting the storage required for input arguments). Elements of input arrays can be modified.

풀이과정

• 빈 배열 idxs 를 정의
• list A 를 for문으로 순환하면서 해당 item과 동일한 요소가 list A 안에 있다면
  • 배열 idxs 에 해당하는 요소들의 index 값을 추가한다.
  • 배열 idxs 에 추가된 index에 해당하는 요소들은 비교를 수행하지 않는다.(continue 처리)
• list A 를 for문으로 순환하면서 해당 item과 동일한 요소가 list A 안에 없다면
• 해당 item을 리턴한다.

풀이코드

• detected time complexity: O(N**2)
• for 문 안에서 if 문을 통해 배열을 탐색 => N^2
• 시간복잡도 O(N**2)이라서 몇가지 테스트는 시간 초과로 통과하지 못했다.

def solution(A):
    idxs = []
    for idx, item in enumerate(A):
        if idx in idxs:
            continue
        elif item in A[idx+1:]:
            idxs.append(idx)
            idxs.append(A[idx+1:].index(item) + idx + 1)
        else:
            return item

다른사람 코드 1

• Detected time complexity: O(N) or O(N*log(N))
• 파이썬에서 sorted() 메소드는 O(N*log(N)) 의 성능을 가진다고 한다.
• 간단하고 빠르다! 이렇게 단순하게 문제에 접근하는 습관을 들여야겠다. 이런 코드 좋다 :)

def test3(A):
    if len(A) == 1:
        return A[0]

    A = sorted(A)
    print(A)
    for i in range(0, len(A), 2):
        if i+1 == len(A):
            return A[i]
        if A[i] != A[i+1]:
            return A[i]

test3([1,2,1,2,3])

다른사람 코드 2

• Detected time complexity: O(N) or O(N*log(N))
• 한 줄로 풀어버리다니..
• 파이썬의 ^ 연산자에 대한 설명
• 2개의 수를 2진수로 바꿔서 비교한다. 각 자리수가 같으면 0, 다르면 1

def solution(A):
  return reduce(lambda x,y: x^y, A)

문제출처

문제

A binary gap within a positive integer N is any maximal sequence of consecutive zeros that is surrounded by ones at both ends in the binary representation of N.

For example, number 9 has binary representation 1001 and contains a binary gap of length 2. The number 529 has binary representation 1000010001 and contains two binary gaps: one of length 4 and one of length 3. The number 20 has binary representation 10100 and contains one binary gap of length 1. The number 15 has binary representation 1111 and has no binary gaps.

Write a function:

def solution(N)

**that, given a positive integer N, returns the length of its longest binary gap. The function should return 0 if N doesn’t contain a binary gap.

For example, given N = 1041 the function should return 5, because N has binary representation 10000010001 and so its longest binary gap is of length 5.**

Assume that:

N is an integer within the range [1..2,147,483,647].

Complexity:

**expected worst-case time complexity is O(log(N));

expected worst-case space complexity is O(1).**

풀이과정

• 함수의 인자로 받은 N을 2진수로 바꾼다
• 2진수 N의 각 자릿수 중에 1에 해당하는 자릿수의 인덱스 값을 찾아 빈 배열에 담는다.
• 배열에 담긴 요소를 인접한 요소와 뺀 결과를 새로운 빈 배열에 담는다.
• 그중에서 최댓값을 리턴한다.

풀이코드

def solution(N):
    N = bin(N)[2:] # 함수의 인자로 받은 N을 2진수로 바꾼다, format(N, 'b') 도 가능
    arr = []

    for idx, value in enumerate(N):
        if value == '1':
            arr.append(idx) # 2진수 N의 각 자릿수 중에 1에 해당하는 자릿수의 인덱스 값을 찾아 빈 배열에 담는다.

    arr2 = []    

    for i in range(len(arr)-1):
        arr2.append(arr[i+1] - arr[i] - 1) # 배열에 담긴 요소를 인접한 요소와 뺀 결과를 새로운 빈 배열에 담는다.

    return max(arr2) # 그 중에서 최댓값을 리턴한다.

Big-O

• (1) ~ (9)를 더하면 5N + 4 Big-O 로 표현하면 O(N)

def solution(N):
    N = bin(N)[2:] # (1) Big-O : constant 1
    arr = [] # (2) Big-O: constant 1

    for idx, value in enumerate(N): # (3) Big-O: N
        if value == '1': # (4) Big-O: N
            arr.append(idx) # (5) Big-O: N

    arr2 = [] # (6) Big-O: constant 1    

    for i in range(len(arr)-1): # (7) Big-O : N
        arr2.append(arr[i+1] - arr[i] - 1) # (8) Big-O: N

    return max(arr2) # (9) Big-O: constant 1

다른 사람 코드

• Big-O : O(N)

#1
def solution(N):
  return len(max(bin(N)[2:].strip('0').strip('1').split('1'))) # Big-O : N

#2
def solution(N):
  return len(max(format(N, 'b').strip('0').split('1'))) # Big-O : N  

.strip() / .split()

• str.strip() 메소드를 활용하여 문자열 양 끝에서 원하는 연속된 문자열을 삭제할 수 있다.

# 2진수 '100100010000' 의 경우,

'100100010000'.strip('0')
# '10010001'
# 좌, 우 끝의 모든 연속된 0을 삭제

'100100010000'.strip('0').strip('1')
# '001000'
# 좌,우 끝의 모든 연속된 1을 삭제

'100100010000'.strip('0').strip('1').split('1')
# ['00', '000']
# 1을 기준으로 문자열을 나눠 배열에 담는다

시간 복잡도 측정 (time complexity)

• 참고자료-추천, 참고자료,
• Big O 표기법은 컴퓨터 공학에서 알고리즘의 복잡도 또는 성능을 표현하기 위해 사용된다. Big O는 특히 최악의 경우를 표현하며, 특정 알고리즘을 수행하는데 특정 시간안에 수행된다는 것을 보장한다는 의미를 가진다.
• Bio 표기법 종류 (상세 내용은 자료 참고)
  • O(1), O(N), O(N^2), O(2^N), O(log N), O(N log N)
  • 이진 탐색 같은 알고리즘은 O(log N)의 성능을 가지며 대용량의 데이터를 처리하는데 아주 효율적이다.
• 알고리즘의 계산복잡도를 결정하는 요소는 크게 네 가지로 구분할 수 있다.
  • 단순 반복문(루프)
  • 재귀호출
  • 테스트 문(IF, WHILE, 또는 UNTIL)
  • 함수의 호출
• 반복문의 계산복잡도는 반복되는 횟수를 통해 쉽게 구할 수 있고, 입력값의 수에 대해 항상 일정하고, 입력되는 값에 좌우되지 않는다. (각 명령이 끝날 때마다 실행 횟수를 적고 더한 후, 상수는 생략하고 최고차항만 고려한다.)
• 반면에 재귀호출이나 테스트 문의 경우에는 새로운 문제를 야기시키는데, 입력되는 값이 따라 계산 복잡도가 바뀌는 것이다. 일반적으로 세 가지 경우를 생각한다. Best Case, Average Case, Worst Case가 그것이다.