# 문제
(심심할떄 풀어보기 1.)
-배터리 용량 관리하기 위해 두 개의 그룹에서 불량여부를 확인하고 있다. 두 개의 그룹 V1, V2를 입력받아 V1, V2 에서 각각 하나의 숫자를 골라 이진 수로 변환 시 가장 1의 개수가 많은 경우를 출력하시오.
예)
5 4 // 5 : V1 그룹 데이터 개수, 4 : V2 그룹 데이터 개수
2 3 5 7 8
1 4 6 8
# 접근 방법
각 리스트의 요소를 모두 변환하여 1의 갯수를 저장한 후 max() 함수를 이용하여 최대값 출력하는 방법으로 접근하였다.
모든 리스트를 순회하며 비교하므로 완전탐색 알고리즘을 사용하였다.
# 단계별 해석
풀이 1
- 입출력 처리
V1, V2 = map(int, input().split())
v1_list = list(map(int,input().split()))
v2_list = list(map(int,input().split()))
- 완전 탐색
v1_binNum = [] #이진값의 1 개수를 저장할 리스트
v2_binNum = []
단순히 두 개의 리스트의 요소를 파이썬의 bin() 함수로 변환 한 후 스트링 변수a 에 저장
변수a에 1을 세기 위해 다시 for 문 순회하며 1의 갯수 만큼 cnt 증가
최종 cnt 값을 v1_binNum 리스트에 append() 시킨다.
각 요소의 1의 값을 출력 하기 위해 cnt와 i (현재 숫자)를 출력
for i in v1_list: # v1의 모든 요소를 순회 하며
cnt = 0 # 각 요소당 1의 개수를 저장 할 변수
a = str(bin(i)) # 1의 개수를 세기 위해 str 값으로 변환
for j in a: # str을 순회하며 1갯수 세기
if j == "1":
cnt += 1
v1_binNum.append(cnt)
print(f'{i}의 이진값의 1개수는 : {cnt}')
- 최댓값 출력
v1_max = max(v1_binNum) #가장 많은 경우의 수
print(f'V1의 1이 가장 많은 경우의 수는 {v1_max}')
모든 리스트를 순회 한 후 그 중 가장 큰 값을 max() 함수를 이용하여 출력하였다.
V2 리스트 또한 같은 방법으로 처리
for i in v2_list:
cnt = 0
a = str(bin(i)).count('1')
for j in a:
if j == "1":
cnt += 1
v2_binNum.append(cnt)
print(f'{i}의 이진값의 1개수는 : {cnt}')
v2_max = max(v2_binNum)
print(f'V2의 이진값 중 1이 가장 많은 경우의 수는 {v2_max}')
- 최종
print(f'V1과 V2 리스트 중 1이 가장 많은 경우는 : {max(v1_max,v2_max)} 입니다.')
V1 과 V2 중 가장 큰 값 max() 함수를 이용하여 출력
- 전체 코드
V1, V2 = map(int, input().split())
v1_list = list(map(int,input().split()))
v2_list = list(map(int,input().split()))
v1_binNum = [] #이진값의 1 개수를 저장할 리스트
v2_binNum = []
for i in v1_list: # v1의 모든 요소를 순회 하며
cnt = 0 # 각 요소당 1의 개수를 저장 할 변수
a = str(bin(i)) # 1의 개수를 세기 위해 str 값으로 변환
for j in a: # str을 순회하며 1갯수 세기
if j == "1":
cnt += 1
v1_binNum.append(cnt)
print(f'{i}의 이진값의 1개수는 : {cnt}')
v1_max = max(v1_binNum) #가장 많은 경우의 수
print(f'V1의 1이 가장 많은 경우의 수는 {v1_max}')
for i in v2_list:
cnt = 0
a = str(bin(i)).count('1')
for j in a:
if j == "1":
cnt += 1
v2_binNum.append(cnt)
print(f'{i}의 이진값의 1개수는 : {cnt}')
v2_max = max(v2_binNum)
print(f'V2의 이진값 중 1이 가장 많은 경우의 수는 {v2_max}')
print(f'V1과 V2 리스트 중 1이 가장 많은 경우는 : {max(v1_max,v2_max)} 입니다.')
# 풀이 2
입출력과 출력은 동일
파이썬의 문자열 카운트 함수 count() 함수를 이용하여 1값 count하는 방식
# 풀이 2 전체 코드
V1, V2 = map(int, input().split())
# 이진 변환 bin()
v1_list = list(map(int,input().split()))
v2_list = list(map(int,input().split()))
v1_binNum = []
v2_binNum = []
for i in v1_list:
cnt = str(bin(i)).count("1")
v1_binNum.append(cnt)
print(f'{i}의 이진값의 1개수는 : {cnt}')
v1_max = max(v1_binNum)
print(f'V1의 1이 가장 많은 경우의 수는 {v1_max}')
for i in v2_list:
cnt = str(bin(i)).count("1")
v2_binNum.append(cnt)
print(f'{i}의 이진값의 1개수는 : {cnt}')
v2_max = max(v2_binNum)
print(f'V2의 이진값 중 1이 가장 많은 경우의 수는 {v2_max}')
print(f'V1과 V2 리스트 중 1이 가장 많은 경우는 : {max(v1_max,v2_max)} 입니다.')
# 테스트 케이스 실행
# 실행시간 비교
- 풀이 1 실행 시간
풀이 1 실행 시간
- 풀이 2 실행 시간
풀이 2 실행 시간
count() 함수를 이용한 코드가 약 실행시간이 2배 빨랐다.
풀이 1은 2중 for문을 사용하여 시간복잡도가 더 높다는 것을 짐작할 수 있다.
count() 함수 또한 O(n) 의 시간복잡도를 가지지만,
풀이 1은 if 조건문O(n)도 포함 되어 있으므로 좀더 시간 복잡도가 올라갈 수 있다
# 느낀점 및 배운점
같은 브루트포스를 이용한 문제이지만 파이썬의 함수를 이용하여 더욱 간결한 코드를 작성할 수 있다는 것을 알았다.
문제를 빨리 푸는 것도 중요하지만, 활용할 수 있는 요소들을 전체적으로 한번 꼼꼼히 작성 해보고 코드설계를 해야겠다고 생각하였다.