-
1337. [Python]올바른 배열Python_알고리즘/Silver IV 2023. 4. 13. 01:55
1. 문제
https://www.acmicpc.net/problem/1337
1337번: 올바른 배열
첫째 줄에 배열의 크기 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 배열의 원소가 한 줄에 하나씩 주어진다. 원소는 1,000,000,000보다 작거나 같은 음이 아닌 정수이
www.acmicpc.net
2. 접근 방법
- 시간 제한: 2초
- 메모리 제한: 128MB
- 구현
- 정렬
3. 파이썬 코드
import sys input = sys.stdin.readline N = int(input()) # 인풋값을 저장할 리스트 num_list = [] # 각 인풋값 별 +4 를 저장할 리스트 check_list = [] for _ in range(N): # 인풋값을 변수로 받는다 number = int(input()) # 기본 리스트 초기값으로 인풋값을 넣어준다 base_list = [number] # +4 까지 숫자를 바로 위의 리스트에 넣어준다 for i in range(1,5): base_list.append(number+i) # 넣은 리스트를 check_list 라는 곳에 넣어준다 check_list.append(base_list) # 인풋값을 num_list 에 넣어준다 num_list.append(number) # 리스트를 정렬 num_list.sort() # 정답 리스트 생성 answer_list = [] # +5값을 한 리스트를 반복문 순회한다. for i in check_list: # 몇개가 들어있는지 체크하는 변수 cnt = 0 # num_list 순회하며 리스트에 존재하면 cnt 값 추가 for j in num_list: if j in i: cnt += 1 # 5개의 값중 들어있는 갯수를 빼준 것을 리스트에 추가 answer_list.append(5-cnt) # 모든 값들 중 최솟값을 출력 print(min(answer_list))
4. 문제를 풀고난 후 생각
- 접근을 어떻게 해야할지 고민을 많이했던 문제이다.
- 처음 고민은 들어온 인풋값을 가지고 +1 씩해가며 다음 인덱스와 값이 같은지 아닌지 체크하는 방식으로 구현을 생각했다. => 결국에는 +4 까지한 값들을 비교해야 하므로 구현하는 방법이 생각이 나지 않았음
- 결국 들어온 인풋값으로 +4 까지의 리스트를 생성하여 이중 리스트로 값들을 탐색해가며 비교하는 방법을 선택했다. => 최대 50개의 값이 들어오기 때문에 이중리스트로 구현을 생각했다.
- 이중리스트로 완전탐색을 해가며 값이 있는 경우를 체크해주고 정답값들을 리스트로 만들어 추가해주었다. => 5-cnt 를 해준 이유로는 cnt는 리스트 안에 있으면 체크했기 때문에 5개의 값중 있는 값들을 빼주면 없는 값들의 갯수가 나온다.
- 이러한 방식으로 구현을 하여 리스트 중 최솟값을 출력하는 것으로 문제를 해결했다.
5. 문제를 푸는데 도움이 되는 지식
- 정렬
- 이중리스트
'Python_알고리즘 > Silver IV' 카테고리의 다른 글
2003. [Python]수들의 합 2 (0) 2023.04.18 1639. [Python]행운의 티켓 (0) 2023.04.17 1920. [Python]수 찾기 (0) 2023.04.12 1755. [Python]숫자놀이 (0) 2023.04.11 1120. [Python]문자열 (0) 2023.04.09