[코딩 테스트 합격자 되기 - 10주차] 정렬(Sort) - 2

문제 56 - 문자열 내 마음대로 정렬하기

프로그래머스

 

문제 분석하고 풀기

파이썬의 정렬 함수인 sorted() 함수를 사용해서 풀이

def solution(strings, n) :
    return sorted(strings, key=lambda x:(x[n], x))

첫 번째 매개변수 strings는 정렬 대상, 두 번째 매개변수 key는 정렬 방법을 람다 함수로 전달한 것이다.

lambda x:(x[n], x)는 x[n]을 기준으로 오름차순 정렬하겠다는 의미

 

N은 strings의 길이이다. sorted() 함수의 시간 복잡도를 고려하면 최종 시간 복잡도는 O(NlogN)이다.

 

 

문제 57 - 정수 내림차순으로 배치하기

프로그래머스

 

문제 분석하고 풀기

제한 조건 : n은 1이상 8,000,000,000(80억)까지 매개 변수로 들어올 수 있는데 이렇게 큰 숫자를 다루는 문제는 숫자를 무자열로 다뤄도 되는지 고민해보는 것이 좋다. 수를 계산하거나 하는 것이 아니라면 문자열로 처리했을 때 얻을 수 있는 이점이 많기 때문이다(80억은 문자열로 생각하면 길이가 20도 되지 않는 짧은 문자열이다.) 지금과 같은 경우, 문제에서 요구하는 건 숫자를 다시 거꾸로 배치하는 것이므로 입력을 정수형으로 생각할 필요가 없다.

1. 저자 풀이

def solution(n):
    digits = list(str(n))       # 정수 n을 문자열로 변환하고 각 자릿수를 리스트로 저장
    digits.sort(reverse=True)   # 내림차순으로 정렬
    answer = int(''.join(digits))   # 정렬된 자릿수를 다시 하나의 문자열로 합쳐 정수로 변환
    
    return answer

1. 숫자 n을 list(str(n))로 처리하여 문자열 -> 리스트로 변환. 그러면 숫자를 하나씩 떼어서 리스트에 저장할 수 있음.
2. 내림차순으로 문자 리스트를 정렬한다. 내림차순으로 정렬하면 높은 숫자가 앞으로 오게 된다.
3. 정렬된 문자를 1의 반대 순서로 진행하여 정수로 만든다.

시간 복잡도 분석

N은 주어진 숫자이다. 주어진 숫자의 자릿수는 대략 logN이다. 따라서 이를 list로 만드는 작업에 필요한 시간 복잡도는 O(logN)이다. 이후 list를 sort() 메서드로 정렬하려면 O(logN * log(logN))의 시간 복잡도가 필요하고, 이를 다시 문자열로 조합할 때 필요한 시간 복잡도는 logN이다.

따라서 최종 시간 복잡도는 O(logN * log(logN)) 이다.

 

2. 내 풀이

def solution(n):
    str_n = str(n)
    lst = sorted([i for i in str_n], reverse=True)
    answer = ''
    for i in lst :
        answer += i
    return int(answer)

 

문제 58 - K번째 수

프로그래머스

 

문제 분석하고 풀기

def solution(array, commands):
    answer = []
    for i, j, k in commands:
        arr = array[i - 1: j]               # i번째 부터 j번째까지 자르기
        sorted_arr = sorted(arr)            # 자른 배열 정렬

        answer.append(sorted_arr[k - 1])    # k번째 원소 구하기
    return answer

1. 슬라이싱으로 commands로 주어진 범위의 원소를 확보
2. 확보된 원소를 정렬
3. k번째 위치의 원소를 반환

시간 복잡도 분석

N은 array의 길이, M은 commands의 길이라고 했을 때, commands의 각 원소에 대해 배열을 자르는 시간 복잡도는 O(N)이며, 이후 정렬을 포함한 시간 복잡도는 O(NlogN)이다.

이를 M번 반복하므로 최종 시간 복잡도는 O((M*N)logN)

 

문제 59 - 가장 큰 수 

프로그래머스

 

제한 사항

• numbers의 길이는 1 이상 100,000 이하입니다.
• numbers의 원소는 0 이상 1,000 이하입니다
• 정답이 너무 클 수 있으니 문자열로 바꾸어 return 합니다.

문제 분석하고 풀기

def solution(numbers):
    numbers_str = [str(num) for num in numbers]
    numbers_str.sort(key=lambda x:x*3, reverse=True)

    return str(int(''.join(numbers_str)))

정렬 기준을 문자열 숫자를 3번 반복해서 사전식 배열(lexicographical order) 기준으로 배열하였다. 

문자열 배열을 정렬하는데, 정렬 기준을 lambda 함수를 사용하여 각 문자열을 3번 반복한 후, 그 결과를 기준으로 내림차순 정렬한다. 이렇게 하는 이유는 숫자들을 문자열로 변환했을 때, 1,000 이하의 숫자들에 대해 문자열의 정렬 기준을 정확하게 맞추기 위함이다.

예를 들어, '3'과 '30'을 비교하였을 때, 단순히 문자열로만 비교하면 '30'이 '3'보다 앞에 오게 되지만, 3번씩 반복한 결과로, '333'과 '303030'을 비교하면 '333'이 '303030'보다 크기 때문에, 3번 반복한 문자열을 기준으로 정렬을 하면 가장 큰 숫자를 얻을 수 있게 된다.

정렬된 문자열 배열을 하나의 문자열로 합치는 과정에서 '0'에 대한 예외처리만 진행하면 되는데, 이는 int() 메서드를 활용하여 예외처리를 진행하였다.

 

책에서는 다른 풀이를 활용하였으니 각자 비교해보길 바란다. 

 

문제 60 - 튜플

프로그래머스

 

문제 분석하고 풀기

이 문제는 파이썬 문법을 잘 활용하지 못하면 문자열 처리가 복잡해질 수 있는 문제이다. 

def solution(s):
    # [1] 문자열 s를 파싱하여 리스트로 변환
    answer = []
    s = s[2:-2].split("},{")
    s = sorted(s, key=len)
    
    # [2] 각 원소를 순회하면서 이전 원소와 차이나는 부분을 구함.
    for nums in s :
        nums = nums.split(',')
        for num in nums :
            num = int(num)
            if num not in answer :
                answer.append(num)
    return answer

1. 문자열을 파싱해서 리스트로 만들고 문자열 길이 기준으로 정렬. 
2. 변환된 s를 순환하며 각 원소를 "," 기준으로 split()한다. 이후 반복문을 수행하며 nums의 각 원소를 체크하고 현재까지 구한 answer에 없는 원소들만 answer에 추가.

 

문제 61 - 지형 이동

프로그래머스

 

문제 분석하고 풀기

문제에서 2가지 포인트를 짚고 넘어가보자. 1. 최소 비용으로 사다리 설치, 2. height 

BFS + 우선순위 큐를 활용하여 풀이를 진행하였다.

 

import heapq
def solution(land, height):
    answer = 0
    n = len(land)
    # [1] 주변 노드 탐색을 위한 direction
    di = [-1, 0, 1, 0]
    dj = [0, 1, 0, -1]
    # [2] 초기 노드 설정
    q = []
    heapq.heappush(q, [0, 0, 0])    # [비용, i, j]
    v = [[0] * n for _ in range(n)]
    
    # [3] BFS + 우선순위 큐로 노드 관리
    while q :
        cost, i, j = heapq.heappop(q)
        # [4] 방문하지 않은 경로면 방문
        if not v[i][j] :
            v[i][j] = 1
            # [5] 비용 합산
            answer += cost
            for d in range(4) :
                ni, nj = i + di[d], j + dj[d]
                # [6] 범위 내
                if 0<=ni<n and 0<=nj<n :
                    tmp_cost = abs(land[i][j] - land[ni][nj])
                    # [7] 입력으로 주어진 height보다 높이차가 큰 경우
                    if tmp_cost > height :
                        new_cost = tmp_cost
                    else :
                        new_cost = 0
                    # [8] 다음 경로 푸시
                    heapq.heappush(q, [new_cost, ni, nj])
                
    return answer

1. 방향 설정
2. 입력값을 받아오고 초기 값을 설정
3. BFS + 우선순위 큐로 모든 노드를 방문
4. 방문하지 않은 노드면 방문 후 방문 체크
5. 비용을 합산
6. 다음 노드가 범위 내 인지 체크함.
7. 임시 값으로 현재 노드와 다음 노드의 높이 차를 계산하고 height보다 높은 경우 사다리 설치 비용으로 입력
8. 다음 경로로 푸시 while문을 반복한다.

이 챕터를 공부하면서 큰값부터 혹은 작은값부터 정렬하는 것 보다는 조금 더 똑똑하게 정렬을 하면서 문제풀이에 이용할 수 있는 요령 등을 배울 수 있었음. 어려운 문제면 접근 방법이 생각나지 않기 때문에 반복이 필요해 보임.