-
2371. [Python]파일 구별하기Python_알고리즘/Silver III 2023. 6. 11. 22:18
1. 문제
https://www.acmicpc.net/problem/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. 문제를 푸는데 도움이 되는 지식
- 브루트포스
- 튜플
'Python_알고리즘 > Silver III' 카테고리의 다른 글
1449. [Python]수리공 항승 (0) 2023.06.14 2346. [Python]풍선 터뜨리기 (2) 2023.06.13 1448. [Python]삼각형 만들기 (1) 2023.06.06 1904. [Python]01타일 (0) 2023.06.05 2312. [Python]수 복원하기 (8) 2023.06.04