[python code review] 8주차(뉴스 클러스터링, 연구소3, 순위 검색)

https://programmers.co.kr/learn/courses/30/lessons/17677

코딩테스트 연습 - [1차] 뉴스 클러스터링

[math 모듈 trunc, dic.values() 사용]

이번에 소수점 '버림' 문제를 처음봐서 trunc 함수에 대해 알게 되었다.

from collections import defaultdict
from math import trunc

def solution(str1, str2):
    s1_dic, s2_dic = defaultdict(int), defaultdict(int)
    answer = 0

    for i in range(len(str1)-1):
        s = str1[i:i+2].upper()
        if 'A' <= s[0] <= 'Z' and 'A' <= s[1] <= 'Z':
            s1_dic[s] += 1
    for i in range(len(str2)-1):
        s = str2[i:i+2].upper()
        if 'A' <= s[0] <= 'Z' and 'A' <= s[1] <= 'Z':
            s2_dic[s] += 1
    intersect = 0
    for k, v in s1_dic.items():
        if k in s2_dic.keys():
            intersect += min(s1_dic[k], s2_dic[k])
    union = sum(s1_dic.values()) + sum(s2_dic.values()) - intersect
    if not union:
        return 65536
    return trunc((intersect/union)*65536)

[코드 개선]

for문에서 slicing된 s에 upper 처리하지 않고 str1, str2 문자열에 먼저 upper 처리함

if 'A' <= s[0] <= 'Z' and 'A' <= s[1] <= 'Z': 라고 적었지만 그냥

문자열 내장함수인 isalpha()를 사용하면 된다. <- 풀려고 하면 막상 생각이 안난다.

from collections import defaultdict
from math import trunc

def solution(str1, str2):
    str1, str2 = str1.upper(), str2.upper()
    s1_dic, s2_dic = defaultdict(int), defaultdict(int)
    answer = 0

    for i in range(len(str1)-1):
        s = str1[i:i+2]
        if s.isalpha():
            s1_dic[s] += 1
    for i in range(len(str2)-1):
        s = str2[i:i+2]
        if s.isalpha():
            s2_dic[s] += 1
    intersect = 0
    for k, v in s1_dic.items():
        if k in s2_dic.keys():
            intersect += min(s1_dic[k], s2_dic[k])
    union = sum(s1_dic.values()) + sum(s2_dic.values()) - intersect
    if not union:
        return 65536
    return trunc((intersect/union)*65536)

https://www.acmicpc.net/problem/17142

17142번: 연구소 3

[BFS & Combinations]

from itertools import combinations
from collections import deque

n, m = map(int, input().split())
board = []
virus_lst = []
time = 1e9
for i in range(n):
    lst = list(map(int, input().split()))
    for j in range(n):
        if lst[j] == 2:
            virus_lst.append((0, i, j))
    board.append(lst)


def bfs(virus):
    global time
    move = [(1,0), (0,1), (-1,0), (0,-1)]
    visited = [[False]*n for _ in range(n)]
    tmp = [[0] * n for _ in range(n)]
    max_val = 0
    # 연구소 -> 임시 테이블에 복사
    for i in range(n):
        for j in range(n):
            tmp[i][j] = board[i][j]

    deq = deque(virus)
    while deq:
        count, x, y = deq.popleft()
        visited[x][y] = 1

        for dx, dy in move:
            nx = x + dx
            ny = y + dy
            if not (0 <= nx < n and 0 <= ny < n):
                continue
            if not visited[nx][ny] and tmp[nx][ny] != 1:
                # 비활성 바이러스도 방문 처리 
                visited[nx][ny] = True
                if tmp[nx][ny] == 0:
                    tmp[nx][ny] = 2
                    max_val = count + 1
                deq.append((count + 1, nx, ny))
    # 모든 빈칸에 바이러스가 퍼졌는지 검사
    for i in range(n):
        for j in range(n):
            if tmp[i][j] == 0:
                return False

    time = min(time, max_val)
    return True


check_lst = []
# virus_lst에서 바이러스 m개 조합 생성
for Virus in list(combinations(virus_lst, m)):
    check_lst.append(bfs(Virus))
# 하나라도 모든 빈 칸에 바이러스를 퍼뜨릴 수 있다면
if True in check_lst:
    print(time)
else:
    print(-1)

[접근했다가 틀린 코드]

from itertools import combinations
from collections import deque

n, m = map(int, input().split())
board = []
virus_lst = []
result = 1e9
for i in range(n):
    lst = list(map(int, input().split()))
    for j in range(n):
        if lst[j] == 2:
            virus_lst.append((i, j))
    board.append(lst)


def bfs(virus):
    global result
    move = [(1,0), (0,1), (-1,0), (0,-1)]
    tmp = [[0] * n for _ in range(n)]
    final_x, final_y = 0, 0
    # 연구소 -> 임시 테이블에 복사
    for i in range(n):
        for j in range(n):
            tmp[i][j] = board[i][j]

    deq = deque()
    for x, y in virus:
        deq.append((x, y))
        tmp[x][y] = 0

    while deq:
        x, y = deq.popleft()
        for dx, dy in move:
            nx = x + dx
            ny = y + dy
            if not (0 <= nx < n and 0 <= ny < n):
                continue
            if tmp[nx][ny] == 0:
                tmp[nx][ny] = tmp[x][y] + 1
                final_x, final_y = nx, ny
                deq.append((nx, ny))

    for i in range(n):
        for j in range(n):
            if tmp[i][j] == 0:
                return False

    max_val = tmp[final_x][final_y]
    result = min(result, max_val)
    return True


check_lst = []
for Virus in list(combinations(virus_lst, m)):
    check_lst.append(bfs(Virus))
if True in check_lst:
    print(result)
else:
    print(-1)

방문 여부를 체크하는 visited 배열을 두지 않고 활성화된 바이러스 좌표 값을 0으로 처리해주고 if tmp[nx][ny] == 0:
                tmp[nx][ny] = tmp[x][y] + 1 와 같은 방식으로 자리값을 갱신해주었다.

문제는 아래 예제와 같이 입력값이 오는 경우, 바이러스 좌표칸(0)을 빈칸 0으로 인식한다는 문제가 있었다.... oops   

 

https://programmers.co.kr/learn/courses/30/lessons/72412

코딩테스트 연습 - 순위 검색

[이분탐색 & 딕셔너리 사용]

from itertools import combinations
from bisect import bisect_left

def solution(info, query):
    answer = []
    info_dict = {}

    for i in range(len(info)):
        infol = info[i].split()  
        mykey = infol[:-1]  
        myval = infol[-1] 

        for j in range(5): 
            for c in combinations(mykey, j):
                tmp = ''.join(c)
                if tmp in info_dict:
                    info_dict[tmp].append(int(myval))
                else:
                    info_dict[tmp] = [int(myval)]
                    
    for k in info_dict:
        info_dict[k].sort()  

    for qu in query: 
        myqu = qu.split(' ')
        qu_key = myqu[:-1]
        qu_val = myqu[-1]
        for qk in qu_key[:]:
            if qk in ['and', '-']:
                qu_key.remove(qk)
        qu_key = ''.join(qu_key)

        if qu_key in info_dict: 
            scores = info_dict[qu_key]
            if scores: 
                enter = bisect_left(scores, int(qu_val))
                answer.append(len(scores) - enter)
        else:
            answer.append(0)

    return answer

info_dict에 저장된 데이터 일부

query 문부터 뽀개서 info에 접근하는 방식으로 구현했는데 효율성 에러 발생..

info로 나올 수 있는 경우의 수를 모두 문자열로 처리하여 key로, 숫자값만 꺼내서 value로 dic에 넣어준다는 개념과

이진 탐색을 사용해 특정 값 이상인 value들의 개수를 구하는 방식이 전혀 생각해보지 못한 방식이었다.. ^.ㅜ블로그 참고 : https://hongcoding.tistory.com/56 

 

Tips. 'and'랑 'in'을 리스트에서 제거할 때, while 문이 아니라 회색 코드와 같은 방식으로 처리 가능. 단 반드시 [:]가 붙어야 함

        for qk in qu_key[:]:
            if qk in ['and', '-']:
                qu_key.remove(qk)

        while 'and' in qu_key:  # and 제거
            qu_key.remove('and')
        while '-' in qu_key:  # - 제거
            qu_key.remove('-')

 

[효율성에서 시간초과 발생한 코드]

def Count(arr):
    global information
    result = 0
    
    for s in information:
        count = 0
        num = s.split()[-1]
        for target in arr:
            if target.isdigit():
                if int(target) <= int(num): count += 1
            else:
                if target in s: count += 1
        if len(arr) == count:
            result += 1

    return result
            
    
def solution(info, query):
    global information
    information = info
    query_lst = []
    answer = []
    for s in query:
        tmp = s.split(' ')
        for data in tmp[:]:
            if data in ['and', '-']:
                tmp.remove(data)
        query_lst.append(tmp)
        
    for lst in query_lst:
        answer.append(Count(lst))
    return answer