Alogorithm _ 2. 완전탐색, 이분탐색 (숫자카드2, 체스판 칠하기)

● 숫자카드 2

문제

숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 몇 개 가지고 있는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다.

셋째 줄에는 M(1 ≤ M ≤ 500,000)이 주어진다. 넷째 줄에는 상근이가 몇 개 가지고 있는 숫자 카드인지 구해야 할 M개의 정수가 주어지며, 이 수는 공백으로 구분되어져 있다. 이 수도 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다.

출력

첫째 줄에 입력으로 주어진 M개의 수에 대해서, 각 수가 적힌 숫자 카드를 상근이가 몇 개 가지고 있는지를 공백으로 구분해 출력한다.

 

문제 풀이

IDEA : 탐색의 문제는 탐색 시간을 줄이는 것이 목표이다.

완전 탐색의 방법으로 수행할경우 상근이의 카드를 모두 들쳐보아야 하는 시간이 소요되고 혹여나 중간에 하나를

발견하였더라도 다른 카드도 그 번호일 확률이 있기때문에 탐색을 중단할 수 없다.

 

중복된 두번째 리스트의 중복요소를 제거하고 타겟 넘버의 유무를 먼저 체크하고 그 후 존재하는 카드들 대상으로 몇개 있는지 탐색하면 더욱 시간을 절약할 수 있을 것으로 예상

 

기본 탐색은 이분탐색법을 이용

카드를 세는 과정은  list.count()메서드를 사용할 경우 시간 초과 발생.

collection 라이브러리의 Counter 사용하여 해결.

 

input_value = []
from collections import Counter

for i in range(4):
    input_value.append(list(map(int,input().split())))

cards_count_Sang = input_value[0]
cards_Sang = input_value[1]
cards_dict = Counter(cards_Sang)

target_count = input_value[2]
target = input_value[3]

cards_Sang.sort()
cards_Sang_dedup = list(set(cards_Sang))


def is_card(cards, targets):
    cards.sort()
    res_list =[]

    for tar in targets:
        left = 0
        right = len(cards)-1

        while(left<=right):
            mid = (left + right) // 2
            res = cards[mid]
            if res == tar:
                count = cards_dict[tar]
                res_list.append(count)

                break
            elif res < tar:
                left = mid+1
            elif res > tar:
                right = mid-1

            if (left>right):
                res_list.append(0)


    return res_list


res_list = is_card(cards_Sang_dedup,target)

print(*res_list)

● 체스판 칠하기

 

import sys

N, M = map(int, sys.stdin.readline().split())
board = [list(map(str, sys.stdin.readline().rstrip())) for _ in range(N)]
# 최솟값
minRes = 32

for rowS in range(N - 7):
    for colS in range(M - 7):
        count = 0
        for i in range(8):
            for j in range(8):
                if (i + j) % 2 == 0:
                    if board[rowS + i][colS + j] == 'B':
                        count += 1
                else:
                    if board[rowS + i][colS + j] == 'W':
                        count += 1
        if count > 32:
            count = 64 - count
        if minRes > count:
            minRes = count

print(minRes)