Python_알고리즘/Silver III
2371. [Python]파일 구별하기
최근영
2023. 6. 11. 22:18
1. 문제
https://www.acmicpc.net/problem/2371
2371번: 파일 구별하기
메모리에 N개의 파일이 저장되어 있다. 이 문제에서는 편의상 각각의 파일을 수열과 같이 생각하자. 이와 같은 파일들을 구별하기 위해서는 두 개의 파일을 맨 끝까지 읽어보는 작업을 수행해야
www.acmicpc.net
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. 문제를 푸는데 도움이 되는 지식
- 브루트포스
- 튜플