[파이썬] 5110. 수열 합치기

※ SW Expert 아카데미의 문제를 무단 복제하는 것을 금지합니다.


여러 개의 수열을 정해진 규칙에 따라 합치려고 한다. 다음은 3개의 수열이 주어진 경우의 예이다.
 

수열 1

2

3

4

5

수열 2

4

8

7

6

수열 3

9

10

15

16

수열 4

1

2

6

5

수열 2의 첫 숫자 보다 큰 숫자를 수열 1에서 찾아 그 앞에 수열 2를 끼워 넣는다.
 

2

3

4

4

8

7

6

5

합쳐진 수열에 대해, 수열 3의 첫 숫자보다 큰 숫자를 찾아 그 앞에 수열 3을 끼워 넣는다. 큰 숫자가 없는 경우 맨 뒤에 붙인다.
 

2

3

4

4

8

7

6

5

9

10

15

16

마지막 수열까지 합치고 나면, 맨 뒤의 숫자부터 역순으로 10개를 출력한다.
 

1

2

6

5

2

3

4

4

8

7

6

5

9

10

15

16

[입력]

첫 줄에 테스트케이스의 수 T가 주어진다. 1<=T<=50

다음 줄부터 테스트 케이스의 별로 첫 줄에 수열의 길이 N, 수열의 개수 M, 이후 M개의 줄에 걸쳐 1000이하의 자연수로 구성된 수열이 주어진다. 4<=N<=1000, 1<=M<=1000

[출력]

각 줄마다 "#T" (T는 테스트 케이스 번호)를 출력한 뒤, 완성된 수열의 맨 뒤부터 10개의 숫자를 역순으로 출력한다.

입력

출력

3 4 4 2 3 4 5 4 8 7 6 9 10 15 16 1 2 6 5 5 5 273 415 58 798 251 675 193 494 506 365 479 390 224 334 387 107 402 569 422 183 88 709 994 206 916 10 10 178 778 659 231 274 123 788 16 483 404 36 14 602 74 287 689 730 703 611 339 445 468 126 821 946 212 218 143 999 923 288 792 249 142 996 999 570 757 141 921 98 87 800 892 401 244 661 179 403 985 474 315 694 816 838 525 288 94 609 6 789 433 474 883 927 841 242 233 286 749 7 667 875 986 107 957 887 520 430 649 721 206 65 776 328 807 845 908 382 836 707 811 790 652 805 190 407 257 668 307

#1 16 15 10 9 5 6 7 8 4 4 #2 251 798 365 506 494 193 675 387 334 224 #3 404 483 16 788 123 274 231 659 778 178

 

👻 나의 풀이

 

# 시간초과
T = int(input())
# 여러개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
for test_case in range(1, T + 1):
    N, M =  map(int, input().split())
    num=[list(map(int, input().split())) for _ in range(M)]
    for i in num[1:] :
        for idx, j in enumerate(num[0]) :
            if i[0] < j :
                temp=num[0][idx:]
                num[0]=num[0][:idx]
                num[0].extend(i)
                num[0]+=temp
                break
            elif idx == len(num[0])-1 :
                num[0].extend(i)
                break
    print('#%d' %test_case, end='')
    for i in num[0][:-11:-1] :           
        print(f" {i}", end=' ')
    print()

 

temp에 수열n의 첫 번째 값보다 큰 수열1의 값 index를 기준으로 슬라이싱해서 temp에 넣는다.

num[0](수열1)에 idx 전까지 슬라이싱한 값을 넣고 수열n 전체를 넣고 num[0]을 extend한다.

num[0]에 temp를 이어붙인다.

끝까지 비교했다면 i를 num[0]에 extend한다.

num[0][:-11:-1]로 끝에서 부터 10개의 값을 출력한다.

 

# 통과한 코드
T = int(input())
# 여러개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
for test_case in range(1, T + 1):
    N, M =  map(int, input().split())		# 수열 길이, 수열 개수
    num=[list(map(int, input().split())) for _ in range(M)]		# M개의 수열
    S=num.pop(0)		# 수열1
    for i in num :
        for idx, j in enumerate(S) :
            if i[0] < j :
                S[idx:idx]=i
                break
        else :			# break가 실행되지 않았을 때
            S.extend(i)		
                    
    print('#%d' %test_case, end=" ")
    for i in S[:-11:-1] :           
        print(f"{i}", end=' ')
    print()

 

s[idx:idx]=i로 간단하게 표현했다.

 

😼 다른사람 풀이

 

for t in range(1, int(input()) + 1):
    N, M = map(int, input().split())
    #첫 리스트 입력받기
    linked_list = list(map(int, input().split()))
    #리스트 하나 받았으니까 개수 -1
    for _ in range(M-1):
        #삽입할 리스트 받고
        temp = list(map(int, input().split()))
        check = True
        #반복해서 체크
        for i in range(len(linked_list)):
            #삽입할 원소보다 크다면
            if linked_list[i] > temp[0]:
                #슬라이싱을 이용하여 삽입
                linked_list[i:i] = temp
                #체크변수 변경하고
                check = False
                #반복문 탈출
                break
        #끝까지 못찾았다면 제일 뒤에 추가
        if check:
            linked_list.extend(temp)
    #뒤에 10개를 출력해야 하므로 슬라이싱 하고 뒤집기
    print_list = reversed(linked_list[len(linked_list)-10:])
    #결과 출력
    print('#{} '.format(t), end='')
    print(*print_list)

 

check가 True면 linked_list에 temp를 extend한다.

reversed를 사용해서 10개를 뒤집는다.

가변형 매개변수를 사용해서 print_list를 반복문 없이 출력한다. 

 

def mergeSeqLists() :
  first_seq=list(map(int, input().split()))

  for _ in range(M-1) :
    seq_len=len(first_seq)
    next_seq=list(map(int, input().split()))

    for i in range(seq_len) :
      if first_seq[i] > next_seq[0] :
        first_seq[i:0] = next_seq
        break

    if seq_len == len(first_seq) :		# 큰 숫자가 없는 경우
      first_seq.extend(next_seq)

  return first_seq

T=int(input())
for test_case in range(1, T+1) :
  N, M = map(int, input().split())

  ans=mergeSeqLists()

  print('#{} '.format(test_case), end='')
  print(' '.join(str(n) for n in ans[-1:-11:-1]))

 

first_seq에 수열1을 입력받는다.

나머지 수열들은 입력받고 수열 합치기 과정을 반복한다.

수열1에 수열 n의 첫 번째 값보다 큰 값이 없으면 초기에 할당했던 first_seq의 길이 seq_len과 현재 first_seq가 같을 것이다. extend한다.