eyebrow93

코딩테스트 연습 - 불량 사용자 | 프로그래머스 (programmers.co.kr)

상당한 고민을 하게 만들었던 문제이다..

최대한의 효율로 풀고자 노렸했었으나. 결국 마지막 관문에서 순열조합을 어찌 사용할지 고민하다가.. 결국 permutations를 사용해서 모든 경우의 수를 다 탐색하기로 변경했다..

첫번째 풀이..

import re
from collections import defaultdict
import itertools
def solution(user_id, banned_id):
    answer = 1
    bands=list(map(lambda x:x.replace('*','.'), banned_id))
    tmpdic=defaultdict(list)
    diccnt={}
    for band in bands:
        comp = re.compile(band)
        for user in user_id:
            if comp.match(user) and len(band)==len(user):
                tmpdic[band].append(user)
        if diccnt.get(band): diccnt[band]+=1
        else: diccnt[band]=1
    
    print(tmpdic)
    print(diccnt)
    for key in tmpdic.keys():
        list(itertools.combinations(tmpdic[key], diccnt[key]))
        

    return answer

# user_id, banned_id=["frodo", "fradi", "crodo", "abc123", "frodoc"],["fr*d*", "abc1**"]	#2
# user_id, banned_id=["frodo", "fradi", "crodo", "abc123", "frodoc"],["*rodo", "*rodo", "******"]	#2
user_id, banned_id=["frodo", "fradi", "crodo", "abc123", "frodoc"],["fr*d*", "*rodo", "******", "******"]	#3
solution(user_id,banned_id)

이 이후의 과정에서 막혔따.. 
문제는, 몇개의 banned_id 가 등장할 지 모르는 상황에서, 이것을 제대로 이어나가지 못하였다..

그리하여, 순열을 활용했따..

import re
import itertools
def solution(user_id, banned_id):
    # answer = 0
    permu = list(itertools.permutations(user_id, len(banned_id)))
    bands=list(map(lambda x:x.replace('*','.'), banned_id))
    comps=[]
    for band in bands:
        comps.append([len(band),re.compile(band)])
    tmp=[]
    for perm in permu:
        if check(comps,perm):
            perm = set(perm)
            if set(perm) not in tmp:
                tmp.append(perm)
    # print(tmp)
    return len(tmp)
def check(comps,perm):
    for comp, user in zip(comps,perm):
        if comp[1].match(user)==None or comp[0]!=len(user):
            return False
    return True

user_id, banned_id=["frodo", "fradi", "crodo", "abc123", "frodoc"],["fr*d*", "abc1**"]	#2
# user_id, banned_id=["frodo", "fradi", "crodo", "abc123", "frodoc"],["*rodo", "*rodo", "******"]	#2
# user_id, banned_id=["frodo", "fradi", "crodo", "abc123", "frodoc"],["fr*d*", "*rodo", "******", "******"]	#3
solution(user_id,banned_id)

링크 : 코딩테스트 연습 - [1차] 캐시 | 프로그래머스 (programmers.co.kr) , LRU Cache Algorithm 정리 :: Jins' Dev Inside (tistory.com) , [프로그래머스] 캐시 / 2018 카카오 블라인드 1차 / 파이썬 (tistory.com)

문제에 대한 설명은 링크를 참조하는것이 좋을것같다. 

일단 LRU에 대한 기본개념을알아야하는데.. 

가장 최근에 사용된 항목은 리스트의 맨 앞에 위치하고 가장 최근에 사용되지않은 항목 순서대로 리스트에서 제거된다.

LRU 알고리즘의 구현은 Linked List 를 이용한 Queue 로 이루어지고, 접근의 성능 개선을 위해 Map 을 같이 사용한다.

중요한점 ! 가장 최근에 사용한 항목은 리스트의 맨 앞에 위치하고, 큐 속에 가장 오래된녀석이 다음번의 교체대상이되는것. 

처음 문제를 풀 땐 Queue에 대해 조금 방심하고, heap을 사용해도 되지않을까? 라고 생각했었다.. 

solution함수에서는 cache를 준비하고, city별로 연산을 진행한다. 
그리하여 findNidx라는 함수를 통해서 큐내부의 프로그램 마지막 사용시간을 -1씩 업데이트하고, 원하는 city가 있다면 해당 인덱스를 저장, 해당 사용시간 0으로 초기화를 진행
이후 리스트끝까지 돌고, city인덱스 return (city 없다면 -1) 방식을 사용했다. 

그리하여 인덱스 -1이 리턴되면  cache에 연산을 진행해주고, 
[-사용시간, 도시이름] 을 담은 heap을 사용했으며, 그렇기에 heappop하면 가장 오래된 (가장작은값) 녀석이 나오고 
 인덱스 -1이 아니라면 hit처리를 하는것으로 진행. 

import heapq
def findNidx(lru, city):
    idx=-1
    for i,v in enumerate(lru):
        lru[i][0]-=1
        time,ct = v
        if ct==city:
            idx = i
            lru[i][0]=0
    return idx

def solution(cacheSize, cities):
    answer = 0
    if cacheSize:
        lru = [[0,i] for i in range(cacheSize)]
        for city_ in cities:
            city=city_.lower()
            idx = findNidx(lru,city)
            if idx == -1: # Not in Cache
                print(lru, 'NOhit', city)
                answer+=5
                heapq.heappop(lru)
                heapq.heappush(lru,[0,city])
            else: # In Cache
                print(lru, 'hit', city)
                answer+=1
        return answer
    else:
        return 5*len(cities)

어느부분에서 잘못된건지를 모르겠다.. 

캐시사이즈 0 처리와, 동일한것들만 들어오는것, 등등 몇가지 예외를 생각해봤지만.. 도저히 모르겠다..

공부해볼만한 코드 deque의 maxlen이라는 옵션을 사용했다..!

# 공부할코드
def solution(cacheSize, cities):
    import collections
    cache = collections.deque(maxlen=cacheSize)
    time = 0
    for i in cities:
        print(i,'\n',cache)
        s = i.lower()
        if s in cache:
            cache.remove(s)
            cache.append(s)
            time += 1
        else:
            cache.append(s)
            time += 5
    return time
cacheSize, cities=5,["Jeju", "Pangyo", "Seoul", "NewYork", "LA", "SanFrancisco", "Seoul", "Rome", "Paris", "Jeju", "NewYork", "Rome"]#52
solution(cacheSize, cities)

코딩테스트 연습 - [3차] 파일명 정렬 | 프로그래머스 (programmers.co.kr)

문제에 대한 설명은 위 링크에서 읽어보는것이 훨씬 좋을 거에요

일단. 저는 문제를 두파트로 나눴습니다. 

1. 입력받은 files를 파일명, HEAD, NUMBER, TAIL로 나누는 부분
여기서 직접적인 변환을 해줄까 하다가.. 결국 출력할때, 원본 파일명이 필요했기에 그대로 나눠주도록했고, 
나누는 과정에서 toggle을 2개 사용했습니다. 
1번토글은 head까지만 1이고, 그 이후 0으로 변환시켜서 if문 분기하는데 사용됩니다 
2번토글은 number를 받는곳에만 사용되며 이때 사용된 조건문은 해당단어가 숫자이며 tog2==1이어야지만 실행되도록 구성했습니다. 
그리하여 head, number, tail을 나눠서줍니다.

2. 이후 sorted를 사용하여 조건에 맞게 소팅해주는것입니다.
key=lambda x : ~~ 를 사용하여, 문제의 조건에 맞게 소팅되도록 하였습니다. 
이후, 소팅순서에 맞게 HEAD,NUMBER,TAIL을 붙여줘서 return하도록 구성하였습니다.

def solution(files):
    flist=[]
    for i,file in enumerate(files):
        flist.append(splitfilename(file))
    flist = sorted(flist, key=(lambda x : (x[0].lower(), int(x[1]))))
    answer=[]
    for file in flist:
        tmp=''
        for i in file:
            tmp+=str(i)
        answer.append(tmp)
    # print(answer)
    return answer
def splitfilename(file):
    head,num,tail = '','',''
    tog1,tog2 = 1,1
    for i in range(len(file)):
        if file[i].isdigit()==False and tog1:
            head+=file[i]
        elif file[i].isdigit() and tog2:
            num+=file[i]
            tog1 = 0
        else:
            tail+=file[i]
            tog2 = 0
    # print(head,num,tail)
    return head, num, tail

# splitfilename('foo010bar020.zip')

files = ["img12.png", "img10.png", "img02.png", "img1.png", "IMG01.GIF", "img2.JPG"]
# files = ["F-5 Freedom Fighter", "B-50 Superfortress", "A-10 Thunderbolt II", "F-14 Tomcat"]
solution(files)

코딩테스트 연습 - [1차] 프렌즈4블록 | 프로그래머스 (programmers.co.kr)

문제설명은 위의링크에서 읽고 진행하는것을 추천합니다.

일단. 이 문제를 풀려면 최소 3개의 파트와 기능이 구현되어야한다고 생각되었다.

1번으로 Check!
보드의 인덱스에 따라 그녀석을 왼쪽위로하는 4칸을 터트릴 수 있는지 확인해야한다. 
Stride개념 (칸 건너뛰기) 을 줘서 풀면 안되는데, 그 이유는 6칸이 터져야하는데, 이걸 한칸건너뛰는 방식으로 갈 경우, 4칸만 터지고 넘어갈 것이라 그러하다.

2번으로 breaking!
찾았으면 터트려야한다. 
난 이부분을 check함수에 if문 분기를 달리하여 재활용했다. 그 이유는 어짜피 체크에서도 4칸을 뒤져봐야하고, 터트릴때고 4칸을 돌아야하기때문데, 굳이 새로운함수를 만들 필요가 없다고 생각했다.
그리하여 breaking이라는 파라미터를 줘서, 이게 체크용도로 쓰는것인지, 터트리는 용도로 쓰는것인지 조건에 따라 분기시켰다. 

3번으로 clead!
터트렸으면, 위에있는녀석들이 아래로 떨어지는것을 구현해야했다. 
사실상 코딩할때 가장 고민되었던 부분이며, 좀 더 효율적으로 짜고싶다는 욕심으로 이미 비어버린 보드row,col은 지워버릴까..도했지만, 그러면 m,n을 다시 계산해주면서 해야하는데, 그게 사실 너무 귀찮아서 다시 이터레이션을 돌도록 만들어버렸다.
만들땐 각 column마다 아래로 내려끌도록하였으며, 그 함수안에 Queue 개념을 사용했고, 맨 아랫층부터 시작하는형태로 iteration을 돌렸다.

def solution(m,n,board):
    answer=0
    bd=[[i for i in row] for row in board]
    while True:
        bklist=[]
        for i in range(m-1): # 맨오른쪽과, 맨아랫라인은 체크할 필요가 없음 
            for j in range(n-1):
                tf,_=check(bd,i,j,m,n,0)
                if tf: # check
                    bklist.append([i,j])
        if bklist :
            for i,j in bklist:
                answer += check(bd,i,j,m,n,1)[1]
            for col in range(n):
                clearbd(bd,m,col)
        else:
            break
    return answer

def check(bd,i,j,m,n,breaking):
    if bd[i][j]==0 and breaking!=1: return False, 0
    adx=[0,0,1,1]
    ady=[0,1,0,1]
    bkcnt=0
    for dx,dy in zip(adx,ady):
        x=i+dx
        y=j+dy
        if breaking:
            if bd[x][y]==0 : pass
            else: 
                bd[x][y] = 0
                bkcnt+=1
        elif x<m and y<n:
            if bd[x][y] != bd[i][j]: 
                return False, bkcnt
    return True, bkcnt

def clearbd(bd,m,col):
    tmp=[]
    tog=1
    for row in range(m-1,-1,-1):
        if bd[row][col]!=0:
            tmp.append(bd[row][col])
            bd[row][col]=0
    for row in range(m-1 , m-len(tmp)-1 , -1):
        bd[row][col] = tmp.pop(0)
# m,n,board = 4,5,["CCBDE", "AAADE", "AAABF", "CCBBF"]#14
m,n,board = 6,6,["TTTANT", "RRFACC", "RRRFCC", "TRRRAA", "TTMMMF", "TMMTTJ"]#15
solution(m,n,board)

참조 : python decorator (데코레이터) 어렵지 않아요 (tistory.com) , Python 데코레이터(Decorator). 데코레이터란? | by 홍찬기 | Medium

데코레이터에 대하여 위의 블로그에서 이미 잘 설명해놓았다.

데코레이터를 활용해서 간단히 팩토리얼을 메모이제이션을 통해 구하는 함수를 만들어보았다.

그런데,, 뭐가 제일 Pythonic한지, 데코레이터와 메모이제이션을 잘 활용했다고 해야할지 모르겠어서.. 혹시나 이 글을 보게되는 여러분들께 어떤게 더 파이썬스러운 코드인지 의견을 여쭙고싶다.

1번코드

def memoize_factorial(f): 
    memory = {1:1,2:2} 
    def wrapper(*args, **kargs):
        k=f(*args,**kargs)
        i=2
        while i<k:
            i+=1
            memory[i] = memory[i-1] * i
        return memory[k]
    return wrapper

@memoize_factorial
def facto(num): 
    return num
facto(5)

2번코드

def memoize_factorial(func): 
    memory = {1:1,2:2}
    def wrapper(*args, **kargs):
        k=args[0]
        if k in memory : return memory[k]
        else:
            i = len(memory)
            while i<k:
                memory[i+1] = memory[i]*(i+1)
                i+=1
        return memory[k]
    return wrapper

@memoize_factorial
def facto(num):
    if num==1: return 1
    else: return num * facto(num-1)
facto(3) , facto(5)

3번코드

def memoize_factorial(f): 
    memory = {} 
    def wrap(args):
        if args in memory:
            return memory[args]
        memory[args]=f(args)
        return memory[args]
    return wrap

@memoize_factorial
def facto(num): 
    if num==1:
        return 1
    else :
        return num * facto(num-1)    
facto(5)

코딩테스트 연습 - [1차] 뉴스 클러스터링 | 프로그래머스 (programmers.co.kr)

일단 나는 문자열을 토대로 str1 과 str2 의 딕셔너리를 만들어주고, 

이후, 교집합과, 합집합을 계산해준다음

최종적으로, 65536 계산을 통해 return하는 형식으로 풀었다. 

import re
# str1,str2,answer='FRANCE,french,16384'.split(',')
# str1,str2,answer='handshake,shake hands,65536'.split(',')
# str1,str2,answer='aa1+aa2,AAAA12,43690'.split(',')
# str1,str2,answer='E=M*C^2,e=m*c^2,65536'.split(',')
def mkstdic(str):
    dic={}
    for i in range(len(str)-1):
        now = str[i]+str[i+1]
        now = re.sub('[^a-z]','',now)
        if len(now)<2: continue
        if dic.get(now):
            dic[now]+=1
        else:
            dic[now]=1
    return dic

def solution(str1,str2):
    a,b = mkstdic(str1.lower()), mkstdic(str2.lower())
    kyo={}
    hap={}
    for ak in a:
        if ak in b:
            kyo[ak] = min(a[ak],b[ak])
            hap[ak] = max(a[ak],b[ak])
        else:
            hap[ak] = a[ak]
    for bk in b:
        if bk in a: continue
        else: hap[bk] = b[bk]
    oper = sum(map(lambda x : kyo[x], kyo))
    div = sum(map(lambda x : hap[x], hap))
    if div == 0 : return 65536
        return int((oper/div)*65536)
solution(str1,str2)