2371. [Python]파일 구별하기

1. 문제

 

https://www.acmicpc.net/problem/2371

2371번: 파일 구별하기

 

2. 접근 방법

 

• 시간 제한: 2초
• 메모리 제한: 128MB
• 튜플
• 브루트포스

 

3. 파이썬 코드

 

import sys
# 파일의 갯수
N = int(input())
# 각 파일별 길이
file_lengths = []
for _ in range(N):
    # 파일을 리스트 형태로 받아옴
    num_list = list(map(int, input().split()))
    file_lengths.append(num_list)
# 파일의 길이중 최대값을 max_length 에 저장
max_length = max(map(len, file_lengths))
# 파일에서 최소가 되는 값을 저장할 변수
min_value = sys.maxsize
# 1~최대 길이 까지 반복문 시행
for K in range(1, max_length + 1):
    # set 형태로 리스트를 받아올 변수
    unique = set()
    # 파일들이 담긴 리스트에서 파일들을 순회
    for file in file_lengths:
        # 만약 K 값보다 파일의 길이가 작은 경우
        if len(file) < K:
            # 튜플 형태로 파일 리스트에 부족한 0 추가
            file[-1] = 0
            unique.add(tuple(file + [0] * (K - len(file) - 1)))
            file[-1] = -1
        else:
            # 튜플형태로 0~K 까지 파일 리스트 추가
            unique.add(tuple(file[:K]))
    # 만약 리스트 갯수가 N 의 갯수와 같으면 min_value 값에 K 넣고 출력
    if len(unique) == N:
        min_value = K
        break

print(min_value)

 

4. 문제를 풀고난 후 생각

 

• 이 문제는 인풋값들이 리스트 형태로 값이 들어오는 구조를 가지고있다.
• 각 인풋값 별로 리스트 형태로 또 다른 리스트에 값들을 저장해준 후 가장 긴 리스트의 길이를 찾는 것을 우선으로 시작한다.
• 이렇게 찾은 가장 긴 길이의 리스트 만큼 반복문을 시행하게 되며 반복문 내부에서는 각 파일별로 또 반복문을 시행하게 된다.
• 1부터 가장긴 리스트 길이까지 탐색을 진행하게 되며 각 길이마다 파일별 슬라이싱을 통해서 set()을 통하여 중복되는 리스트를 제거해주는 방식으로 코드를 구현했다.
• 만약 N(파일의 갯수)와 중복제거된 리스트 갯수가 같을 경우 그때 우리가 원하는 최소로 필요한 리스트 길이가 된다.
• 이때 sys.maxsize를 통하여 가장 큰 값을 구해둔 변수에 K 값을 넣어준 후 break 를 통해서 반복문을 탈출하면 된다.

뭔가 리스트 형태로 값들이 들어오다 보니 접근하는 방법에 있어서 고민을 좀 많이 했던 것 같다. 문자열을 다루는 것은 익숙하지만 리스트를 다루는 것은 역시 아직 좀 어렵다.

 

5. 문제를 푸는데 도움이 되는 지식

 

• 브루트포스
• 튜플