제로베이스 20220314

코딩테스트 연습

1. 안녕 2020 안녕 2021

• 2020년을 보내고 2021년을 맞이하는 기념으로 Albert는 재미있는 문제를 풀기로 했다. 양의 정수 중 첫 네 숫자가 “2020”이며 마지막 네 숫자가 “2021”이면 “안녕한 정수” 라고 정의 하자. 가령 202021 이나 20202021은 “안녕한 정수” 이며, 2020021 이나 2020221 은 안녕한 정수가 아니다.

• Albert는 n개의 정수 A[1], A[2], …, A[n]중 두 수를 골라 더했을 때 그 합이 “안녕한 정수”가 되는 쌍의 개수를 알고 싶다. 즉, 1 ≤ i < j ≤ n 을 만족하는 (i, j) 쌍 중 A[i] + A[j]가 안녕한 정수인 쌍의 개수를 알고 싶다. 예를 들어 A = [101010, 101010, 101011, 101011], 즉 n = 4개의 정수가 있다고 하자. 이 경우 A[1] + A[3] = A[1] + A[4] = A[2] + A[3] = A[2] + A[4] = 202021 이므로 총 4개의 쌍이 존재한다 ((1, 3), (1, 4), (2, 3), (2, 4)).

• 입력으로 n개의 정수가 주어졌을 때, 합이 안녕한 정수가 되도록 하는 쌍의 개수를 출력하시오.

입력

• 첫 줄에 테스트 케이스의 수 T가 주어진다. 각 테스트 케이스는 두 줄로 구성된다.

• 테스트 케이스의 첫 줄에 정수의 개수 n이 주어진다. 다음 줄에 n개의 정수가 공백으로 구분되어 주어진다.

출력

• 각 테스트 케이스에 대해 합이 안녕한 정수가 되는 쌍의 개수를 출력한다.

풀이

# your code goes here
 
import sys
from itertools import permutations
 
# 첫 줄에 테스트 케이스의 수 T가 주어진다. 각 테스트 케이스는 두 줄로 구성된다.
 
T = int(sys.stdin.readline())
 
# 첫 줄에 정수의 개수 n이 주어진다. 다음 줄에 n개의 정수가 공백으로 구분되어 주어진다.
 
for _ in range(0,T):
	n = int(sys.stdin.readline())
	arr = list(map(int,sys.stdin.readline().split()))
 
	cnt = 0
	# n개의 정수중 두개를 더한 값이므로, 순열이 옳다고 생각해 
	# itertools의 permutations를 사용했다.
	p = list((map(sum,permutations(arr,2))))
	for num in p:
		if num < 0:
			continue
		elif len(str(num)) < 6:
			continue
		# 마지막 글자가 2021이고, 첫 네글자가 2020이면 cnt를 증가.
		if str(num)[:4] == '2020' and str(num)[-4:] == '2021':
			cnt += 1
	# 전체 가짓수에서 한번씩 중복되므로 //2를 통해 중복 제거.
	print(cnt // 2)

채점 결과

• 오답(시간 초과)

• 해당 문제의 하단에 있는 사용 알고리즘을 통해 이 문제를 ‘이진 탐색’으로 풀어야 한다는것은 알았으나, 어떻게 접근해야 할지에 대해서 감이 오지 않는다.

  • 정답지 역시 맞춘 사람만 볼 수 있고, 이번 문제의 경우 푼 사람이 별로 없는지 블로그 글 역시 따로 존재하지 않아 해답을 알 수 없었다.