JungPadak 블로그

level 2. 가장 긴 팰린드롬

11 May 2017 | 알고리즘 프로그래밍

문제출처

문제

앞뒤를 뒤집어도 똑같은 문자열을 palindrome이라고 합니다. longest_palindrom함수는 문자열 s를 매개변수로 입력받습니다. s의 부분문자열중 가장 긴 palindrom의 길이를 리턴하는 함수를 완성하세요. 예를들어 s가 “토마토맛토마토”이면 7을 리턴하고 “토마토맛있어”이면 3을 리턴합니다.

풀이코드

def longest_palindrom(s):
    list_s = list(s)
    if list_s == list_s[::-1]:
        return len(list_s)

    result = []
    for idx, item in enumerate(list_s):
        if item in list_s[idx+1:]:
            idx2 = list_s[idx+1:].index(item) + idx+2

            if list_s[idx:idx2] == (list_s[idx:idx2])[::-1]:
                result.append(len(list_s[idx:idx2]))

    if len(result) == 0:
        return 1
    return max(result)

print(longest_palindrom("토마토맛토마토")) # 7
print(longest_palindrom("토마토맛있어")) # 3
print(longest_palindrom("맛있어토마토")) # 3

level 2. 괄호 확인하기

11 May 2017 | 알고리즘 프로그래밍

문제출처

문제

is_pair함수는 문자열 s를 매개변수로 입력받습니다. s에 괄호가 알맞게 짝지어져 있으면 True를 아니면 False를 리턴하는 함수를 완성하세요. 예를들어 s가 “(hello)()”면 True이고, “)(“이면 False입니다. s가 빈 문자열(““)인 경우는 없습니다.

풀이코드

  • stack을 활용한다.
  • 빈 stack 에는 “(“ 만 들어갈 수 있다.
  • ”)” 이 올때까지 “(“ 를 쌓다가, “)” 이 오면 “(“ 하나와 함께 pop
  • 마지막에 빈 stack 이 남으면 True, 아니면 False
def is_pair(s):
    stack = []
    for ch in s:
        if ch == "(":
            stack.append(ch)
        elif ch == ")":
            try:
                stack.pop()
            except IndexError:
                return False

    return len(stack) == 0

codility 4-2. Perm Check

07 May 2017 | 알고리즘 프로그래밍

문제출처

문제

A non-empty zero-indexed array A consisting of N integers is given.
A permutation is a sequence containing each element from 1 to N once, and only once.
For example, array A such that:

    A[0] = 4
    A[1] = 1
    A[2] = 3
    A[3] = 2
is a permutation, but array A such that:

    A[0] = 4
    A[1] = 1
    A[2] = 3
is not a permutation, because value 2 is missing.
The goal is to check whether array A is a permutation.
Write a function:
def solution(A)

that, given a zero-indexed array A, returns 1 if array A is a permutation and 0 if it is not.
For example, given array A such that:

    A[0] = 4
    A[1] = 1
    A[2] = 3
    A[3] = 2
the function should return 1.
Given array A such that:

    A[0] = 4
    A[1] = 1
    A[2] = 3
the function should return 0.
Assume that:

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

expected worst-case time complexity is O(N);
expected worst-case space complexity is O(N), beyond input storage
(not counting the storage required for input arguments).

풀이코드

풀이코드 1

  • Detected time complexity: O(N) or O(N * log(N))
def solution(A):
    M = max(A)
    B = list(set(A))
    if len(B) == M and len(A) == len(B) and sum(range(M+1)) == sum(B):
        return 1
    return 0

풀이코드 2

  • Detected time complexity: O(N^2)
  • 문제점 : A = [1000000000] 와 같은 인자가 주어지면, sum(range(max(A)+1)) 부분에서 많은 시간이 소요된다.
def solution(A):
    B = list(set(A))
    if len(A) == len(B) and sum(range(max(A)+1)) == sum(B):
        return 1
    return 0

풀이코드 3

  • Detected time complexity: O(N^2)
def solution(A):
    if len(A) == max(A):
        for idx, var in enumerate(A): # O(N)
            if var in A[idx+1:]: # O(N^2)
                return 0
        return 1
    return 0

다른사람 풀이

def solution(A):
    N = len(A)

    xorSum = 0
    for i in range(1, N+1):
        xorSum ^= i ^ A[i-1]

    if xorSum == 0:
        return 1
    else:
        return 0
  • or 연산자 활용
def solution(A):
    if max(A) != len(A) or len(set(A)) != len(A):
        return 0
    return 1

codility 3-3. TapeEquilibrium

05 May 2017 | 알고리즘 프로그래밍

문제출처

문제

A non-empty zero-indexed array A consisting of N integers is given.
Array A represents numbers on a tape.
Any integer P, such that 0 < P < N,
splits this tape into two non-empty parts: A[0], A[1], ..., A[P − 1] and A[P], A[P + 1], ..., A[N − 1].
The difference between the two parts is the value of: |(A[0] + A[1] + ... + A[P − 1]) − (A[P] + A[P + 1] + ... + A[N − 1])|
In other words, it is the absolute difference between
the sum of the first part and the sum of the second part.

For example, consider array A such that:

  A[0] = 3
  A[1] = 1
  A[2] = 2
  A[3] = 4
  A[4] = 3

We can split this tape in four places:

P = 1, difference = |3 − 10| = 7
P = 2, difference = |4 − 9| = 5
P = 3, difference = |6 − 7| = 1
P = 4, difference = |10 − 3| = 7

Write a function: def solution(A)
that, given a non-empty zero-indexed array A of N integers, returns the minimal difference that can be achieved.
For example, given:

  A[0] = 3
  A[1] = 1
  A[2] = 2
  A[3] = 4
  A[4] = 3

the function should return 1, as explained above.

Assume that:
N is an integer within the range [2..100,000];
each element of array A is an integer within the range [−1,000..1,000].
Complexity:

expected worst-case time complexity is O(N);
expected worst-case space complexity is O(N),
beyond input storage (not counting the storage required for input arguments).

풀이코드

  • Detected time complexity: O(N * N)
  • list slice 후, sum() 을 통해서 합계를 구하는 부분이 O(N^2)의 시간 복잡도를 가진다.
def solution(A):
    li = []
    for P in range(1,len(A)):
        sum1 = sum(A[:P]) # O(N^2)
        sum2 = sum(A[P:])
        diff = sum1 - sum2 if sum1 >= sum2 else sum2 - sum1
        li.append(diff)
    return min(li)

다른사람 풀이

  • Detected time complexity: O(N)
  • abs() 내장 함수를 통해서 숫자의 절대값을 구할 수 있다. abs(-3) » 3, abs(1,2) » 1.2
  • list slice를 사용하지 않는다.
  • min_difference 변수에 None을 담아서 시작한다.
def solution(A):
    sum_of_part_one = 0
    sum_of_part_two = sum(A)
    min_difference = None

    for i in range(1, len(A)):
        sum_of_part_one += A[i-1]
        sum_of_part_two -= A[i-1]
        difference = abs(sum_of_part_one - sum_of_part_two)

        if min_difference == None:
            min_difference = difference
        else:
            min_difference = min(min_difference, difference)

    return min_difference

programmers - 직사각형 만들기

04 May 2017 | 알고리즘 프로그래밍

문제출처

문제

직사각형을 만드는 데 필요한 4개의 점 중 3개의 좌표가 주어질 때, 나머지 한 점의 좌표를 반환하는 solution 함수를 완성해 주세요. 단, 직사각형의 각 변은 x축, 혹은 y축에 평행하며, 반드시 직사각형을 만들 수 있는 경우만 입력으로 주어집니다.

제한사항 좌표값 : 10억이하의 자연수 입출력 예

v [[1, 4], [3, 4], [3, 10]] result [1, 10] v [[1, 1], [2, 2], [1, 2]] result [2, 1]

입출력 예 설명 입출력 예 1 주어진 점의 좌표가 [[1, 4], [3, 4], [3, 10]] 일때, [1, 10]에 점이 위치하면 직사각형이 됩니다.

입출력 예 2 주어진 점의 좌표가 [[1, 1], [2, 2], [1, 2]] 일때, [2, 1]에 점이 위치하면 직사각형이 됩니다.

풀이코드

def solution(v):
    answer = []
    v1 = []
    v2 = []
    for i in v:
        if i[0] not in v1:
            v1.append(i[0])
        else:
            v1.remove(i[0])
        if i[1] not in v2:
            v2.append(i[1])
        else:
            v2.remove(i[1])
    answer = v1 + v2
    return answer