배열 - 제시된 합을 가진 부분 배열 찾기

카테고리 Python, DataStructure, Array

제시된 합을 가진 부분 배열 찾기

정렬되지 않은 양의 정수로 이루어진 배열 A가 있다. 연속된 원소를 더한 값이 제시된 값 S와 같은 부분 배열을 찾아라. (인덱스 기준은 1이다.)

  • 입력: arr = [1, 2, 3, 7, 5], s = 12, 출력: [2, 4]
    • 인덱스 2부터 4까지의 합: 2 + 3 + 7 = 12
  • 입력: arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], s = 15, 출력: [1, 5]

방법

1. 이중 반복문 사용

1
2
3
4
5
6
7
def solution(arr,s):
    for i in range(len(arr)):
        sum = s
        for j in range(i,len(arr)):
            sum -= arr[j]
            if (sum == 0):
                return [i+1,j+1]

2-1. O(n) 시간복잡도로 풀기

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def solution(arr,s):
    sum = s
    index = 0
    position = 0
    while sum != 0:
        if position == len(arr) - 1:
            return [-1]
        sum -= arr[position]
        if sum < 0:
            index += 1
            position = index
            sum = s
            continue
        position += 1
    return [index+1,position]
  • sum에 s를 할당하여 position 위치의 요소를 하나씩 빼면서 sum 값이 0 보다 작은지 체크
  • 0 보다 작다면 연속되는 부분합이 아니므로 리셋시켜주고 시작 index도 우측으로 이동시킨다.
  • 만약 시작 index가 배열의 끝까지 도달했는데도 sum이 0이 되지 않으면 연속되는 부분합을 만들 수 없다.

2-2. O(n) 시간복잡도로 풀기

1
2
3
4
5
6
7
8
9
10
def solution(arr,s):
    left,sum = 0,0
    for right in range(len(arr)):
        sum += arr[right]
        while (left < right and sum > s):
            sum -= arr[left]
            left += 1
        if sum == s:
            return [left+1,right+1]
    return [-1]
  • 배열의 첫번째 요소부터 하나씩 sum에 더해준다.
  • sum이 s보다 작거나 같으면 계속 배열의 요소를 더해준다.
  • sum > s를 만족하면, sum에 left 위치의 요소를 빼주면서 sum이 s보다 작거나 같으면 중단
  • 이 때, sum == s를 만족하면 [left+1, right+1]을 반환한다.
  • left == right 일 때, sum == s를 만족하지 않으면 연속되는 부분합이 없다.

댓글 공유

배열 - 0과 1로 구성된 배열 정렬

카테고리 Python, DataStructure, Array

0과 1로 구성된 배열 정렬

0과 1로 이루어진 배열이 있다. 배열 자체를 오름차순으로 정렬하라.

  • 입력: [1, 0, 1, 1, 1, 1, 1, 0, 0, 0], 출력: [0, 0, 0, 0, 1, 1, 1, 1, 1, 1]
  • 입력: [1, 1], 출력: [1, 1]

방법

1. sort() 사용

1
2
3
4
5
arr = [1, 0, 1, 1, 1, 1, 1, 0, 0, 0]

def get_increased_arr(arr):
    arr.sort()
    return arr
  • sort() 메서드는 원본 배열을 오름차순으로 변경한다.

2. sorted() 사용

1
2
3
4
5
arr = [1, 0, 1, 1, 1, 1, 1, 0, 0, 0]

def get_increased_arr(arr):
    answer = sorted(arr)
    return answer

3. count() 사용

1
2
3
def get_increased_arr(arr):
    arr[:] = [0] * arr.count(0) + [1] * arr.count(1)
    return arr
  • arr[:]을 사용하여 원본에 영향을 미치지 않고 복사할 수 있다.

4. 포인터 2개 사용

1
2
3
4
5
6
7
8
9
10
11
12
13
def get_increased_arr(arr):
    left = 0
    right = len(arr) - 1

    while left < right:
        while arr[left] == 0:
            left += 1
        while arr[right] == 1 and right >= 0:
            right -= 1
        if left < right:
            arr[left], arr[right] = 0, 1
            left, right = left + 1, right + 1
    return arr

댓글 공유

배열 - 회문(Pelindromes) 찾기

카테고리 Python, DataStructure, Array

회문(Palindrome) 찾기

주어진 문자열이 회문이면 True, 아니면 False를 반환하라.

  • 입력: madam, 출력: True
  • 입력: tomato, 출력: False

방법

1. reversed(), join(), 리스트 컴프리헨션 사용

1
2
3
4
def isPelindrome(str):
    reverse_str = "".join(list(reversed([x for x in str])))

    return str == reverse_str

2. 슬라이싱 사용

1
2
3
4
5
6
word = 'racecar'

if word == word[::-1]:
    print(True)
else:
    print(False)
  • 슬라이싱은 [startIndex:endIndex:interval]로 사용하는데, startIndex, endIndex 없이 interval만 사용하여 역순을 표현했다.

3. 포인터 2개 사용

1
2
3
4
5
6
7
8
def is_palindrome(word):
    left,right = 0, len(word) - 1

    while left < right:
        if (word[left] != word[right]):
            return False
        left, right = left + 1, right - 1
    return True

댓글 공유

loco9939

author.bio


author.job