금속막대 Python(SW Expert Academy, SWEA)

난이도 : D5

문제번호 : 1259

문제 주소 및 출처입니다.

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV18NaZqIt8CFAZN&categoryId=AV18NaZqIt8CFAZN&categoryType=CODE

SW Expert Academy

---

목차

1. 문제 설명

2. 문제 해석

3. 소스 코드

---

1. 문제 설명

원형 금속 막대를 가장 길게 연결하고자 한다. 원형 금속 막대는 한 쪽 면에 수나사와 다른 쪽에 암나사로 이루어져 있다. 수나사와 암나사는 굵기가 서로 다르다. 아래 그림에서 수나사의 굵기는 3을 암나사의 굵기는 4를 나타내고 있다. 이후 나사의 굵기를 수나사의 굵기 x 암나사의 굵기로 표현한다. 연결은 +로 표현한다.   이와 같은 원형 금속 막대를 연결하기 위해서는 수나사의 굵기와 암나사의 굵기가 서로 일치해야 한다. 예를 들어 두 개의 원형 금속 막대 3x4와 4x5가 있을 때 3x4+4x5로 연결해야 연결되며 4x5+3x4로 연결하면 연결되지 않는다. 수나사와 암나사의 크기가 서로 다른 여러 개의 원형 금속 막대를 가장 많이 연결하려고 한다. 어떤 순서로 연결해야 가장 많이 연결하는지를 찾는 프로그램을 작성하시오.

 

입력

맨 첫 줄에는 테스트 케이스의 개수가 주어진다. 그리고 테스트 케이스가 각 라인에 주어진다. 각 테스트 케이스는 2줄로 구성되며, 첫 줄에는 원형 금속 막대의 개수 n이 주어지고, 다음 줄에는 2n개의 수가 주어진다.  숫자는 공백으로 구분한다. 앞에서부터 2개씩 하나의 원형 금속 막대의 수나사 굵기와 암나사 굵기를 의미한다.

출력

각 테스트 케이스 각각에 대한 답을 출력한다. 각 줄은 ‘#x’로 시작하고 공백을 하나 둔 다음, 각 테스트 케이스에 주어진 수열로부터 가장 많이 연결하기 위한 원형 금속 막대의 수나사 굵기와 암나사 굵기를 순서대로 출력한다.

예시

입력	출력
10 3 3 4 2 3 4 5 4 1 2 5 1 2 4 4 3 …	#1 2 3 3 4 4 5 #2 5 1 1 2 2 4 4 3 …

---

2. 문제풀이

오래전에 풀었던 문제라 코드가 마음에 들지 않지만... 입력으로 들어오는 나사를 묶어서 리스트로 표현하였다. 제일 앞에 데이터를 기준으로 모든 나사를 돌면서 확인했다. 현재 리스트에서 선택한 나사의 뒷부분이 기준 나사 앞부분과 크기가 일치한다면 리스트에 있는 나사를 앞쪽에 연결해준다. 혹은 선택한 나사의 앞부분이 기준 나사의 둣부분과 크기가 일치한다면 리스트에 있는 나사를 뒷쪽에  연결해준다. 연결을 할 수 없다면 리스트의 다음 부분을 확인했다. 연결을 했다면 돌아가 리스트의 처음부분부터 다시 탐색했다. 모든 나사가 연결했다면 연결된 구조를 출력한다.

---

3. 소스코드

#D5 1259 금속막대
 
#반복횟수만큼 입력받고 반복
T = int(input())
for t in range(1, T+1):
    abc = input()
    #입력받고 공백을 기준으로 분리
    lst =list(map(int, input().split())) 
    temp = []
    result = []
    #숫나사, 암나사 가 한묶음이므로 2개씩 끊어서 넣는다.
    for i in range(0, len(lst), 2):
        temp.append((lst[i], lst[i+1]))
    #결과창에 제일앞내용을 넣는다.
    result.append(temp.pop(0))
    #인덱스 추적을 위한 변수 i
    i = 0
    #temp의 길이가 0이 될때까지 반복한다.
    while len(temp):
        #앞에 연결할수있다면 결과에 추가하고 인덱스 초기화
        if temp[i][1] == result[0][0]:
            result.insert(0, temp.pop(i))
            i = 0
        #뒤에 연결할 수 있다면 추가하고 인덱스 초기화
        elif temp[i][0] == result[len(result)-1][1]:
            result.append(temp.pop(i))
            i = 0
        #아무것도 연결못한다면 다음것을 확인
        else:
            i += 1
    #출력하기
    print("#{}".format(t), end='')
    for r in result:
        print(' ', end='')
        print(*r, end = '')
    print()