제로베이스 20220603 코테 연습

1차원 배열 탐색

1. 수열 축소

• 길이가 n인 수열이 주어지면 인접한 두 수의 차이를 이용해 길이가 N-1인 수열을 만듭니다.

• 만약 수열이 [5, 3, 7, 9, -2]라면 [(3-5), (7-3), (9-7), (-2-9)] => [-2, 4, 2, -11]로 수열의 길이를 줄일 수 있습니다.

• 이런 과정을 길이축소작업이라 하겠습니다.

• n길이의 수열 nums 주어지면 m번의 길이축소작업을 한 결과인 배열을 반환하는 프로그램을 작성하세요.

제한사항

• nums의 길이 3<= n <=30
• m(m<n)

풀이

def solution(nums, m):
    answer = nums

    for _ in range(m):
        for i in range(len(answer)-1):
            answer[i] = answer[i+1]-answer[i]

        del answer[-1]

    return answer


print(solution([5, 3, 7, 9, -2], 2))

리뷰

• i+1번째 항목에 i번째 항목을 빼서 i번째 항목의 값으로 갱신한다.

• 해당 행위를 m번 반복한다.

2. 제곱수 정렬

• 오름차순 정렬되어 있는 길이가 n인 수열이 주어집니다. 수열의 원소를 제곱하여 오름차순 정렬한 배열을 반환하는 프로그램을 작성하세요.

제한사항

• 주의 : sort 함수를 사용하면 안됩니다.
• nums의 길이 3<= n <=100,000

풀이 1

def solution(nums):
    answer = []

    answer = [x**2 for x in nums]

    for i in range(len(answer)):
        for j in range(i,len(answer)):
            if answer[i] > answer[j]:
                tmp = answer[i]
                answer[i] = answer[j]
                answer[j] = tmp

    return answer


print(solution([-7, -3, 2, 3, 11]))

리뷰

• 주어진 배열의 각 항목을 전부 제곱하고, 수동으로 정렬했다.
• sort함수를 쓰지 말라니까 수동으로 sort를 돌렸다.
• 내가 해놓고도 어이가 없는 풀이법이지만, 일단 답은 잘 나오기에 기록은 해두었다.

풀이 2 (정렬 없는 풀이)

def solution(nums):
    answer = [0]*len(nums)
    left = 0
    right = len(nums)-1
    for i in range(len(nums)-1,-1,-1):
        if abs(nums[left])<abs(nums[right]):
            tmp=nums[right]
            right-=1
        else:
            tmp=nums[left]
            left += 1
        answer[i]=tmp*tmp

    return answer


print(solution([-7, -3, 2, 3, 11]))

리뷰

• left와 right 포인터를 양쪽 끝에 생성하고, 리스트에 nums[left]와 nums[right] 중 절댓값이 큰 값을 넣어가며 좁혀나간다.

• 주어진 배열은 오름차순 정렬 되어있으므로, 절댓값이 가장 작은 값은 배열의 가운데에 위치한다.

• 따라서 리스트에 넣은 값들을 제곱해준 후, 리스트를 역순으로 돌리면 제곱수들이 정렬되어 나오게 된다.

3. 수열의 높이 조정

• n길이의 수열이 주어집니다.
• 수열의 높이 조정은 수열의 원소값 중 가장 큰 원소에서 1을 빼 가장 작은 원소에 더해주는 것을 말합니다.
• 가장 큰 원소와 가장 작은 원소가 여러개면 그 중 아무거나 선택하면 됩니다.
• 만약 수열이 [2, 1, 3, 7, 5]라면 1회의 높이조정을 거치면 [2, 2, 3, 6, 5]가 됩니다.
• n길이의 수열 nums가 주어지면 높이조정을 m회 한 후 가장 큰 값과 가장 작은 값을 차를 반환하는 프로그램을 작성하세요.
• 단 m회의 높이조정을 하던 중 모든 값이 같아지면 이 조정을 중단하고 0을 반환합니다.

제한사항

• nums의 길이 3<= n <=100,000
• 배열 nums의 원소는 1,000을 넘지 않습니다.
• m(1<=m<=10,000)

풀이

def solution(nums, m):
    answer = 0

    for _ in range(m):
        if min(nums) == max(nums):
            break
        else:
            min_idx = nums.index(min(nums))
            max_idx = nums.index(max(nums))
            nums[min_idx] += 1
            nums[max_idx] -= 1

    answer = max(nums) - min(nums)

    return answer


print(solution([3, 2, 3, 3, 4] , 3))

리뷰

• 배열의 가장 큰 값과 가장 작은값이 같아진다면, 배열 내 모든 값이 같은것이므로 높이 조정을 중단한다.

• 높이 조정이 끝나면, 배열의 최대값과 최소값의 차를 리턴한다.

4. 가장 높은 증가 수열

• 길이가 n인 수열이 주어지면 이 수열에서 연속된 부분 증가수열을 찾습니다.
• 각 부분증가수열은 높이가 있습니다.
• 증가수열의 높이란 증가수열의 첫항과 마지막항의 차를 의미합니다.
• 수열이 주어지면 여러 증가수열 중 가장 높은 부분증가수열을 찾는 프로그램을 작성하세요.
• 만약 수열이 [5, 2, 4, 7, 7, 3, 9, 10, 11]이 주어지면 가장 높은 부분증가수열은 [3, 9, 10, 11]이고, 높이는 8입니다.

제한사항

• 주의 : 이웃하는 두 수가 같을 경우 증가수열로 보지 않습니다.
• nums의 길이 3<= n <=100,000
• 배열 nums의 원소는 자연수입니다.

풀이

def solution(nums):
    answer = 0

    head = 0
    tail = 0
    max_gap = 0
    for i in range(1, len(nums)):
        if nums[i - 1] < nums[i]:
            tail += 1
        else:
            if max_gap < nums[tail] - nums[head]:
                max_gap = nums[tail] - nums[head]
            head = i
            tail = i

    if max_gap < nums[tail] - nums[head]:
        max_gap = nums[tail] - nums[head]

    answer = max_gap

    return answer


print(solution([8, 12, 2, 3, 7, 6, 20, 3]))

리뷰

• head와 tail 두 포인터를 설정한다.

• nums가 증가하고 있다면(nums의 i-1번보다 i번 항목이 크다면) tail을 증가시킨다.

• nums가 더이상 증가하지 않는다면, 찾아낸 증가수열의 각 끝에 위치한 포인터들인 tail과 head에서의 값의 차를 구하고, 최대값보다 클 경우 최대값을 갱신한다.

  • 해당 작업이 끝난 후, head와 tail은 증가수열이 종료된 인덱스로 초기화를 진행한다.

• nums가 마지막 항목까지 증가하고 있었다면, tail과 head에서의 값의 차를 구하고, 최대값보다 클 경우 최대값을 갱신한다.

5. 가장 긴 수열

• 길이가 N인 수열이 주어지면 이 수열에서 연속으로 증가하거나, 또는 연속으로 작아지는 부분 수열 중 가장 길이가 긴 수열을 찾으려고 합니다.

• 만약 [5, 3, 6, 7, 9, 8, 5, 3, 1, 2]이 주어지면 우리가 찾는 가장 긴 수열은 [9, 8, 5, 3, 1]입니다.

• 수열 [1, 2, 3, 3, 4, 5, 6]과 같이 같은 값이 연속으로 있는 것은 증가 또는 감소로 보지 않기 때문에 가장 긴 수열은 [3, 4, 5, 6]이 됩니다.

• 매개변수 nums에 수열이 주어지면 nums에서 연속 증가하거나 연속 감소하는 부분수열 중 가장 긴 수열의 길이를 반환하는 프로그램을 작성하세요.

제한사항

• nums의 길이 3<= n <=100,000
• 배열 nums의 원소는 자연수입니다.

풀이

def solution(nums):
    answer = 0

    ih = 0
    it = 0
    dh = 0
    dt = 0
    max_len = 0

    for i in range(1,len(nums)):
        if nums[i-1] < nums[i]:
            it += 1
            if max_len < dt-dh+1:
                max_len = dt-dh+1
            dh = i
            dt = i
        elif nums[i-1] > nums[i]:
            if max_len < it-ih+1:
                max_len = it-ih+1
            ih = i
            it = i
            dt += 1
        else:
            if max_len < it-ih+1:
                max_len = it-ih+1
            if max_len < dt-dh+1:
                max_len = dt-dh+1
            dh = i
            dt = i
            ih = i
            it = i

    answer = max_len

    return answer


print(solution([1, 2, 3, 3, 4, 5, 6, 7, 7]))

리뷰

• 강사님은 반복문 두번으로 증가수열과 감소수열을 각각 구하셨지만, 나는 코드가 다소 더러워지더라도 반복문 한번으로 끝내고 싶어 두개를 한번에 구했다.

• 증가수열과 감소수열의 최대 길이를 각각 구한후, 비교해서 최대값을 리턴한다.

6. 바이토닉 수열

• 바이토닉 수열이란 수열이 증가했다가 감소하는 수열을 의미합니다.

• 길이가 n인 수열이 매개변수 nums에 주어지면 이 수열이 바이토닉 수열인지 판별하는 프로그램을 작성하세요.

• 만약 [1, 2, 3, 4, 2, 1]이면 바이토닉 수열입니다.
• 하지만 [1, 2, 2, 3, 2, 1]과 같이 같은 값이 연속으로 있으면 바이토닉 수열이라 하지 않습니다.

제한사항

• nums의 길이 3<= n <=30
• 배열 nums의 원소는 자연수입니다.

풀이

def solution(nums):
    answer = ''

    max_idx = nums.index(max(nums))
    head = max_idx
    tail = max_idx

    while head > 0 or tail < len(nums)-1:
        if head > 0:
            if nums[head-1] >= nums[head]:
                return "NO"
            head -= 1

        if tail < len(nums)-1:
            if nums[tail+1] >= nums[tail]:
                return "NO"
            tail += 1

    if tail == max_idx or head == max_idx:
        return "NO"

    return "YES"


print(solution([1, 2, 3, 4, 5]))

리뷰

• 배열 내에서 최대값을 잡고, 그 최대값을 기준으로 양 옆으로 감소 수열이 유지되는지 검사한다.

• 감소수열이 유지되지 않는다면 해당 수열은 바이토닉 수열이 아니므로, NO를 리턴한다.

• 최대값이 양쪽 끝에 존재하는 경우, 반대쪽으로 가는 수열이 존재할수 없으므로 NO를 리턴한다.

• 나머지 경우에는 YES를 리턴한다.

7. 거리 두기

• 현수는 영화관에 도착했습니다.
• 영화상영 시간보다 약간 늦은 현수는 남은 좌석을 빨리 선택 하고 영화를 보려고 합니다.
• 일렬로된 n개의 좌석정보가 매개변수 nums에 주어지면, 이미 앉아 있는 사람들 중 가장 가까운 사람과 최대한 멀리 떨어져 앉을 자석을 선택해야 그 거리를 반환하는 프로그램을 작성하세요.

제한사항

• nums의 길이 3<= n <=100
• 배열 nums의 원소 1은 이미 사람이 앉은 좌석이고, 0은 빈 좌석입니다.

풀이

def solution(nums):
    answer = 0

    head = 0
    tail = 0
    max_len = 0
    max_head = 0
    max_tail = 0
    for i in range(len(nums)):
        if nums[i] == 1:
            if max_len < tail - head+1:
                max_len = tail - head+1
                max_head = head
                max_tail = tail+1
            head = i
            tail = i
        else:
            tail += 1

    answer = (max_head + max_tail) // 2

    return answer


print(solution([1, 0, 0, 0, 1, 0, 0, 1, 0, 1]))

리뷰

• head와 tail을 설정하고, 1이 나올때마다 해당 지점에서 head와 tail을 해당 인덱스로 초기화한다.

• 최대 길이가 갱신될때마다 해당 부분에서의 tail과 head의 인덱스를 저장한다.

• 최대 길이의 리스트를 구했다면, 해당 부분의 거리인 (tail + head의 절반)을 구해 리턴한다.

8. 빈도수 구하기

• 길이가 n인 수열이 nums주어집니다.
• 자연수 k가 주어지면 수열의 원소 중 빈도수가 가장 많은 것 순으로 K개를 배열형태로 반환하는 프로그램을 작성하세요.

제한사항

• nums의 길이 3<= n <=30
• m(m<n)

풀이

from collections import Counter


def solution(nums, m):
    answer = [x for y, x in sorted([(y, x) for x, y in Counter(nums).items()], reverse=True)][:m]

    return answer


print(solution([1, 1, 1, 2, 2, 3], 2))

리뷰

• 원래라면 포인터를 이용한 탐색이 주가 되었겠지만, 또 도져버린 한줄코딩병으로 인해 list comprehension을 주로 사용한 코드가 되어버렸다.

  • 사실 한줄코딩병이 아니더라도 Counter를 이용해 풀었을것같아 어차피 강사님의 의도와는 멀어졌을것 같긴 하다.

• Counter의 items에서 key,value값을 꺼내 값과 그 값의 빈도수를 구하고, 빈도수가 많은 순서로 정렬한다.

• 정렬된 배열에서 키값만을 빼낸 후, m번째 순서까지만 표시하여 리턴한다.

9. 최대길이 바이토닉

• 바이토닉 수열이란 수열이 증가했다가 감소하는 수열을 의미합니다.

• 길이가 n인 수열이 주어지면 이 수열의 연속부분수열 중 가장 긴 바이토닉 수열을 찾아 그 길이를 반환하는 프로그램을 작성하세요.

• 만약 [1, 3, 2, 5, 7, 4, 2, 5, 1]수열이 주어지면 이 수열의 연속부분수열 중 가장 긴 바이토닉 수열은 [2, 5, 7, 4, 2]이고, 답은 5입니다.

제한사항

• nums의 길이 3<= n <=10,000
• 배열 nums의 원소는 자연수입니다.

풀이 (내 풀이)

def solution(nums):
    answer = 0
    max_len = 0
    
    for i in range(len(nums)):
        head = i
        tail = i
        flag = False
        for j in range(i + 1, len(nums)):
            if nums[j - 1] >= nums[j]:
                flag = True
            elif flag:
                if nums[j - 1] <= nums[j]:
                    if max_len < tail - head + 1:
                        max_len = tail - head + 1
                    break
            tail += 1
    
    answer = max_len

    return answer


print(solution([1, 3, 2, 5, 7, 4, 2, 5, 1]))

리뷰

• 배열 내의 각 위치로부터 시작하는 바이토닉 수열을 검사한다.

• 가장 긴 값을 리턴한다.

풀이 2 (강사님 풀이)

def solution(nums):
    answer = 0
    max_len = 0
    
    peak = []
    for i in range(1, len(nums) - 1):
        if nums[i - 1] < nums[i] and nums[i + 1] < nums[i]:
            peak.append(i)

    length = []
    for idx in peak:
        left = idx
        right = idx
        cnt = 1
        while left >= 0 and nums[left-1] < nums[left]:
            cnt += 1
            left -= 1
        while right < len(nums)-1 and nums[right+1] < nums[right]:
            cnt += 1
            right += 1

        length.append(cnt)

    answer = max(length)

    return answer


print(solution([1, 3, 2, 5, 7, 4, 2, 5, 1]))

리뷰

• 양 옆의 항목이 자신보다 낮은 항목들을 peak에 저장.

• 각 peak에서 바이토닉 수열을 검사하여 길이를 length에 저장.

• length의 최대값을 리턴.

10. 수열의 경우수

• 바이토닉 수열이란 수열이 증가했다가 감소하는 수열을 의미합니다.

• 길이가 n인 수열이 주어지면 이 수열의 연속부분수열 중 바이토익 수열이 몇 개 있는지 알아내는 프로그램을 작성하세요.

• 만약 [1, 3, 2, 5, 7, 4, 2, 5, 1]수열이 주어지면 이 수열의 연속부분 수열 중 바이토닉 수열은 [1, 3, 2], [2, 5, 7, 4], [2, 5, 7, 4, 2], [5, 7, 4], [5, 7, 4, 2], [2, 5, 1]로 6개가 있습니다.

제한사항

• nums의 길이 3<= n <=100
• 배열 nums의 원소는 자연수입니다.

풀이

def solution(nums):
    answer = 0

    peak = []
    for i in range(1,len(nums)-1):
        if nums[i-1] < nums[i] and nums[i+1] < nums[i]:
            peak.append(i)

    for idx in peak:
        left = idx
        right = idx

        lc = 0
        rc = 0
        while left >= 0 and nums[left - 1] < nums[left]:
            lc += 1
            left -= 1
        while right < len(nums) - 1 and nums[right + 1] < nums[right]:
            rc += 1
            right += 1

        answer += lc * rc

    return answer


print(solution([1, 3, 2, 5, 7, 4, 2, 5, 1]))

리뷰

• 양 옆의 항목이 자신보다 작은 경우, peak에 저장.

• 각 peak에서 시작되는 바이토닉 수열의 최대 범위인 head와 tail을 구한다.

• 최대 범위의 바이토닉 수열에서 나올수 있는 바이토닉 수열의 개수는 해당 수열의 head * tail로 표현되므로, answer에 누적하여 더해준다.

• answer를 리턴.

11. 키보드

• 당신은 키보드의 자판 중에서 스페이스바 외에 n개의 자판만 사용할 수 있습니다.

• 만약 n=5이면, 당신은 “time to time”이라는 문장을 완성할 수 있습니다.

• 만약 “Time to Time”라는 문장을 완성하려면 대문자 ‘T’를 써야 하는데 이 때는 shift키와 소문자 ‘t’키를 누르면 됩니다. 그래서 “Time to Time”문장을 완성하기 위해서는 n=6이어야 가능합니다.

• 하나의 문장을 n개의 키로 완성할 수 있으면 그 문장에 쓰인 문자개수만큼 점수를 얻을 수 있습니다.

• “Time to Time” 문장을 완성했을 경우 12점을 얻을 수 있습니다.

• 매개변수에 하나의 문장을 담은 s문자열 변수와 사용 가능한 키의 개수인 n이 주어지면 여러분이 얻을 수 있는 점수를 리턴하는 함수를 작성하세요.

• 만약 문장을 완성할 수 없다면 -1을 리턴합니다.

제한사항

• 1 ≤ s의 길이 ≤ 1,000
• 1 ≤ n ≤ 20

풀이

def solution(nums, m):
    used = [0] * 27

    for x in s:
        if x.islower():
            used[ord(x) - 97] = 1
        elif x.isupper():
            used[ord(x) - 65] = 1
            used[26] = 1

    if len([x for x in used if x > 0]) <= n:
        return len(s)
    else:
        return -1


print(solution("Big Life is Good", 10))

리뷰

• 모 대기업의 코드 테스트 문제를 강사님께서 난이도를 낮추어 낸 문제이다.

• 알파벳 26글자 + shift 한글자를 해싱할 27 크기의 리스트를 생성한다.

• 소문자일경우 아스키코드값 97을 빼준 번호를 1로 설정하고, 대문자일 경우 shift에 해당하는 used[26]번 값과 아스키코드값 65를 빼준 값을 1로 설정한다.

• used에서 1로 설정된 값들의 갯수를 리턴하고, used가 설정되지 않았다면 -1을 리턴한다.