[파이썬 알고리즘 문제풀이 입문] 탐색&시뮬레이션 - 두 리스트 합치기

*문제 본문은 강의 내용과 관련되어 있어 자세하게 적지 않았습니다.

 

 

 

문제

오름차순으로 정렬이 된 두 리스트가 주어지면 두 리스트를 오름차순으로 합쳐 출력하는 프로그램을 작성하세요.

 

 

 

풀이

• 내 풀이

import sys
input = sys.stdin.readline

N = int(input())
N_list = list(map(int, input().split()))
M = int(input())
M_list = list(map(int, input().split()))

result = N_list + M_list
result.sort()

for i in result:
    print(i, end=' ')

• 답안 : Python

import sys
input = sys.stdin.readline

N = int(input())
N_list = list(map(int, input().split()))
M = int(input())
M_list = list(map(int, input().split()))

p1 = p2 = 0
result = list()

while p1 < N and p2 < M:
    if N_list[p1] <= M_list[p2]:
        result.append(N_list[p1])
        p1 += 1
    else:
        result.append(M_list[p2])
        p2 += 1

if p1 < N:
    result = result + N_list[p1:]
if p2 < M:
    result = result + M_list[p2:]

for i in result:
    print(i, end=' ')

• 답안 : Kotlin (내가 바꿔본 것 / 정확X)

import java.io.*
import java.util.*

fun main(args: Array<String>) = with(BufferedReader(InputStreamReader(System.`in`))){
    var N = readLine().toInt()
    var N_list = (readLine().split(" ").map { it.toInt() })
    var M = readLine().toInt()
    var M_list = (readLine().split(" ").map { it.toInt() })

    var p1 = 0
    var p2 = 0
    var result : MutableList<Int> = mutableListOf()

    while(p1 < N && p2 < M)     {
        if(N_list[p1] <= M_list[p2]) {
            result.add(N_list[p1])
            p1 += 1
        } else {
            result.add(M_list[p2])
            p2 += 1
        }
    }

    if(p1 < N) {
        result = (result + N_list.slice(p1..N-1)).toMutableList()
    }
    
    if(p2 < M) {
        result = (result + M_list.slice(p2..M-1)).toMutableList()
    }

    for(i in result) {
        print("${i} ")
    }
}

- 정렬하면 기본적으로 sort()를 써왔었기 때문에 sort()를 사용해서 문제를 풀었으나, 문제에서 애초에 오름차순으로 정렬된 리스트로 조건이 주어졌기 때문에 시간복잡도가 더 빠른 방법으로 해결할 수 있다는 것을 답안을 통해 알게 되었다.

- 기존에 sort()를 사용해서 합쳐진 리스트 구하는 시간복잡도 : NlogN

  오름차순으로 정렬된 리스트로 합쳐진 리스트 구하는 시간복잡도 : N

  (NlogN과 N의 차이는 데이터가 많아졌을 때 확연히 나타난다고 한다.)

 

cf.) Kotlin에서 Python의 인덱싱처럼 처리하는 방법 : 리스트.slice(범위1..범위2)

 

 

 

** 리스트 합치는 방법

(1) Python

→ '+'로 합치는 방법 : 리스트A + 리스트B [새로운 리스트 반환]

→ 하나의 리스트에 '리스트A.extend(리스트B)' 로 다른 리스트 합치는 방법 [기존의 리스트에 새로운 리스트 추가]

 

(2) Kotlin

→ '+'로 합치는 방법 : 리스트A + 리스트B [리스트가 MutableList 이어야 함]

→ 'plus'로 합치는 방법 : 리스트A.plus(리스트B)

→ 'addAll(리스트)'로 합치는 방법 : 리스트변수.addAll(리스트A) → 리스트변수.addAll(리스트B)

→ 'union'으로 중복 제거하면서 리스트 합치는 방법 : 리스트A.union(리스트B)

 

 

 

*** 리스트 정렬 방법

(1) Python

→ 리스트.sort()

 

(2) Kotlin

→ Mutable : 리스트.sort() 

→ Immutable : 리스트변수 = 리스트.sorted() [원본변경X]