SWEA 5110 - 수열 합치기

https://swexpertacademy.com/main/learn/course/subjectDetail.do?courseId=AVuPDN86AAXw5UW6&subjectId=AWOVJ1r6qfkDFAWg

 

처음 든 생각

- 반복문으로 새로운 수열의 첫째 원소랑 기존 배열의 원소들과 하나씩 비교해주면서 위치를 찾은 다음 합쳐주면 되겠다

 

나의 답

T = int(input())
for test_case in range(1, T + 1):
    N, M = map(int, input().split())
    arr = [float('inf')]
    cnt = 0
    for _ in range(M):
        a = list(map(int, input().split()))
        for i in range(N*cnt+1):
            if a[0] < arr[i]:
                arr[i:i] = a
                break
        cnt +=  1
    print(f'#{test_case}',end=' ')
    print(*arr[-11:-1][::-1])

 

 

무한대를 비교하여 기존 배열 안의 모든 원소들보다 첫째 항이 더 클 경우의 예외 처리를 간단하게 했다.

 

그 다음 기존의 배열들과 원소를 하나씩 비교해가면서 큰 놈을 발견하면 바로 수열을 합쳐준다.

 

처음 제출했던 답

T = int(input())
for test_case in range(1, T + 1):
    N,M = map(int,input().split())
    s =[float('inf')]
    for _ in range(M):
        new = list(map(int, input().split()))  
        for i in range(len(s)+1):
            if new[0] < s[i]:
                s= s[:i] + new + s[i:]
                break
    print(f"#{test_case}", end=" ")
    print(*s[-11:-1][::-1])

 

위의 답을 제출했더니 1개가 계속 시간 초과로 안되는 것이었다.

len(s)가 시간복잡도가 혹시 큰가 해서 수정했다. 

-> 사실 찾아보니 len 함수의 시간 복잡도도 O(1)이라 지장없었다.

 

그리고 수열을 합쳐주는 부분을 구글링해서 다른 방법이 있나 찾아본건데...솔직히 뭔 차이인지 모르겠다.

아시는 분 있으면 댓글로 알려주세요ㅠㅠ

 

복습할 부분

 

1. 리스트를 합치는 방법

 list[i:i] = new_list

list의 i번째 인덱스부터 new_list의 원소들을 추가해준다.

 

2. 인덱스 슬라이싱 음수

-11이면 오른쪽 끝에서부터 11번째 원소이다. -11:-1 이라면 맨 오른쪽 원소를 제외하고 오른쪽에서부터 2번째 원소~11번째 원소를 가리키는 것이다.

 

3. 리스트 역순

슬라이싱 기법을 활용해서 [::-1]을 추가하면 리스트의 원소가 역순으로 배치된다.