[프로그래머스] 10/04 (5)

[방문 길이]-[Summer/Winter Coding(~2018)]

My answer

def solution(dirs):
    answer = set()
    posx,posy,tmpx,tmpy=0,0,0,0
    
    for i in dirs:
        tmpx,tmpy=posx,posy
        if(i=='U' and posy!=5):
            posy+=1
        elif(i=='D' and posy!=-5):
            posy-=1
        elif(i=='R' and posx!=5):
            posx+=1
        elif(i=='L' and posx!=-5):
            posx-=1
        if((posx,posy)==(tmpx,tmpy)): continue
        answer.add((posx,posy,tmpx,tmpy))
        answer.add((tmpx,tmpy,posx,posy))
    return len(answer)//2

Another answer

def solution(dirs):
    s = set()
    d = {'U': (0,1), 'D': (0, -1), 'R': (1, 0), 'L': (-1, 0)}
    x, y = 0, 0
    for i in dirs:
        nx, ny = x + d[i][0], y + d[i][1]
        if -5 <= nx <= 5 and -5 <= ny <= 5:
            s.add((x,y,nx,ny))
            s.add((nx,ny,x,y))
            x, y = nx, ny
    return len(s)//2

경로를 이전좌표랑 옮긴좌표를 집합에 넣어주고 반대에서 오는 것도 똑같은 경로이기 때문에 옮긴좌표,이전좌표도 미리 넣어준다. 이러면 집합은 중복을 허용하지 않기 때문에 나중에 반대에서 돌아오는 것도 이미 집합안에 있어서 추가 되지 않고 마지막에 경로를 두배씩 해서 넣어준거기 때문에 //2해준다. 아래 코드는 나와 같은 방법인데 u,d,l,r 을 딕셔너리로 만들어서 내 코드처럼 if문을 여러번을 안써도 풀 수 있게 했다.

[스킬트리]-[Summer/Winter Coding(~2018)]

My answer

def solution(skill, skill_trees):
    answer = 0
    tmp=""
    
    for i in skill_trees:
        for j in range(len(i)):
            if(i[j] in skill):
                tmp+=i[j]
        for j in skill:
            if(j not in tmp):
                tmp+=j
        if(tmp == skill):
            answer+=1
        tmp=""
    
    return answer

Another answer

def solution(skill, skill_trees):
    answer = 0
    tmp=""
    
    for i in skill_trees:
        for j in range(len(i)):
            if(i[j] in skill):
                tmp+=i[j]
        if(tmp == skill[0:len(tmp)]):
            answer+=1
        tmp=""
    
    return answer
-------------------------------------------
def solution(skill, skill_trees):
    answer = 0

    for skills in skill_trees:
        skill_list = list(skill)

        for s in skills:
            if s in skill:
                if s != skill_list.pop(0):
                    break
        else:
            answer += 1

    return answer

아래 코드중 우선 첫번째는 나와 비슷한데, 나는 그냥 tmp에서 skill중에 없는 문자를 맨뒤에 붙여버려서 확인했는데, 아래코드는 tmp의 길이만큼만 skill에서 확인했다. 어차피 결과랑 푸는 방법은 똑같지만 아래코드가 더 꼼수없이?푼 것 같다. 다음으로 두번째 코드는 for, else구문을 사용했는데 for-else구문은 for이 중단되지 않고 실행되면 else구문을 실행한다. 따라서 중간에 break가 안걸리면 answer+=1을 하는 방식으로 풀었다.

[점프와 순간이동]-[Summer/Winter Coding(~2018)]

My answer

def solution(n):
    ans = 0
    while(n!=0):
        if(n%2==1):
            n-=1
            ans+=1
        n=n//2 
    return ans

Another answer

def solution(n):
    return bin(n).count('1')

 n 위치에서 0으로 갈 때 순간이동이 가능하지 못한 순간에 1칸씩만 점프를 뛰는 과정이 n을 이진화 할때 나오는 1의 개수를 구하는 과정과 동일하다.

[이진변환 반복하기]-[월간 코드 챌린지 시즌 1]

My answer

def solution(s):
    answer = [0,0]
    i=0
    while(s!='1'):
        while('0' in s):
            if(s[i]=='0'):
                answer[1]+=1
                s=s[:i]+s[i+1:]
                i-=1
            i+=1
        s=bin(len(s))[2:]
        answer[0]+=1
        i=0
    return answer

Another answer

def solution(s):
    answer = [0,0]
    while s!='1':
        tmp = s.count('1')
        answer[1]+= len(s) - tmp
        s = bin(tmp)[2:]
        answer[0]+=1
    return answer

나는 문제에서 말하는 순서 그대로 따라갔는데, 아래 코드는 그걸 함축했다. 내가 0을 제거하고 길이를 재는 부분을 1의 갯수를 세는 거 하나로 끝내서 훨씬 시간이 적게 걸린다.

[[1차]캐시]-[2018 KAKAO BLIND RECRUITMENT]

My answer

def solution(cacheSize, cities):
    arr=[]
    answer = 0
    
    cities=[i.upper() for i in cities]
    
    if(cacheSize==0):
        return 5*len(cities)
    
    for i in cities:
        if(i not in arr):
            if(len(arr)==cacheSize):
                arr.remove(arr[0])
            answer+=5
        else:
            answer+=1
            arr.remove(i)
        arr.append(i)
    return answer

Another answer

def solution(cacheSize, cities):
    import collections
    cache = collections.deque(maxlen=cacheSize)
    time = 0
    for i in cities:
        s = i.lower()
        if s in cache:
            cache.remove(s)
            cache.append(s)
            time += 1
        else:
            cache.append(s)
            time += 5
    return time

[LRU]

가장 오랫동안 참조되지 않은 캐시를 교체하는 캐시 교체 알고리즘이다. 캐시교체는 캐시의 총 크기만큼 정보를 저장하는데, 이미 있으면 건너뛰고 없으면 알고리즘에 따라 교체한다. 캐시교체 알고리즘에는 총 3가지가 있는데, FIFO, LFU, LRU가 있다. 각각의 알고리즘에 대한 장단점은 https://j2wooooo.tistory.com/121 이 분의 블로그를 참고했다. 아래 코드는 나와 동일한 방법으로 풀었는데, DEQUE를 사용하여 append와 remove하는 시간을 단축시켰다. deque는 큐를 양방향으로 만드는 것이다. 이로인해 삽입,제거하는 시간복잡도가 O(1)로 줄어든다. 자세한 deque사용법은 https://leonkong.cc/posts/python-deque.html 를 참고했다.