코딩하는 eroke

문제

id_list의 유저들이 각각 본인이 신고한 유저가

k번 이상 본인 포함 다른 사람들에게 신고당했을 시 게시판 이용을 정지당하는데,

각 유저가 신고해서 정지당한 유저들 수를 출력하는 문제이다.

한 유저가 특정 유저를 여러번 신고할 수 있지만 해당 경우는 신고 1회로 친다.

풀이

import collections as c

def solution(id_list, report, k):
    result = []
    rpdict = c.defaultdict(list) 
    stop = c.defaultdict(int)
    
    for i in range(len(report)):
        who, rp = report[i].split()
        
        if rp not in rpdict[who]: #이미 신고한 유저는 추가 스킵
            rpdict[who].append(rp)
            stop[rp]+=1
    
    for x in id_list:
        cnt=0
        for y in rpdict[x]:
            if stop[y]>=k:
                cnt+=1
        result.append(cnt)
    
    return result

유저마다 신고한 유저를 추가할 list형 딕셔너리 rpdict 와

정지대상 유저를 구하기 위한 int형 딕셔너리 stop을 이용해 풀었다. 

코딩테스트환경에 익숙해질겸 프로그래머스에서는 IDE를 사용하지 않고있는데

한번에 정답처리가 뜨면 그렇게 기분이 좋을 수 없다 ㅎㅎ..

문제

그림이 있어서 일단 풀기 싫었지만 레벨 1이기도 하고 문제를 읽어보니 쉬워보여서 풀어보았다.

그림처럼 인형 정보가 있는 2차원 배열에서 movies 배열로 명령하는 열의 인형을 맨 위에것 부터 하나씩 뽑으면 된다.

큐를 이용해 풀었다.

풀이

from collections import deque

def solution(board, moves):
    
    answer = 0  
    dq=deque()
    for m in moves:
        y = m-1

        for x in range(len(board)):
            if board[x][y]!=0:
                tmp=board[x][y]
                board[x][y]=0
                
                if dq and dq[-1]==tmp:
                    answer+=2
                    dq.pop()               
                else:
                    dq.append(tmp)
                
                break #한번만 수행
    return answer

문제

짝지어 제거하기는, 알파벳 소문자로 이루어진 문자열을 가지고 시작합니다. 

먼저 문자열에서 같은 알파벳이 2개 붙어 있는 짝을 찾습니다. 

그다음, 그 둘을 제거한 뒤, 앞뒤로 문자열을 이어 붙입니다. 

이 과정을 반복해서 문자열을 모두 제거한다면 짝지어 제거하기가 종료됩니다.

풀이

from collections import deque
def solution(s):
    dq=deque()
    
    dq.append(s[0]) 
    for i in range(1,len(s)):
        if len(dq)>0 and dq[-1]==s[i]:
            dq.pop()
        else:
            dq.append(s[i])

    if len(dq)==1:return 0

    while dq:
        x=dq.popleft()
        if len(dq)>0 and dq[0]==x: dq.popleft()
        else: return 0

    return 1

첫번째 문자를 deque에 넣고 다음 문자와 같으면 pop, 다르면 push 했다.

1차 연산이 끝난 뒤엔 큐가 빌때까지 큐 앞뒤 원소들을 비교하며 pop 해서 풀이하였다.

프로그래머스 '더맵게' 로 힙을 접한 뒤 복습할 겸 힙문제를 풀어봤다.

> 더맵게 문제 풀이 (https://rokroks.tistory.com/111)

문제

문자열로 들어오는 명령어로 값을 push하거나 최대/최소값을 pop 한뒤

최종적으로 [최댓값,최솟값]을 return하는 문제이다.

파이썬 heapq는 기본적으로 최소힙인데 해당 문제는 최대힙도 이용해야한다.

파이썬에서 최대힙을 이용하는 방법은 push/pop 시에 데이터를 음수로 넣는 것이다.

풀이

import heapq as h

def solution(operations):
    answer = []
    
    h1=[] #최소힙
    h2=[] #최대힙
    h3=[] #빈큐 확인용 힙
    
    for s in operations:
        o,n=s.split()
        n=int(n)
        
        if o=='I':
            h.heappush(h1,n) #최소힙
            h.heappush(h2,-n) #최대힙
            h.heappush(h3,n) 
            
        elif o=='D':
            try:
                if n==1:
                    h.heappop(h2)               
                    h.heappop(h3)
                elif n==-1:
                    h.heappop(h1)
                    h.heappop(h3)
                if len(h3)==0: #초기화
                    h1=[]
                    h2=[]
            except IndexError: continue
                    
    if len(h3)==0:
        answer=[0,0]
    else:
        answer.append(-h2[0]) #최대값
        answer.append(h1[0])  #최소값
        
    return answer​

최소힙, 최대힙, 빈큐 확인용 힙 총 3개의 힙으로 풀었다..

문제

프로그래머스 heap 카테고리에 있는 문제이다. 두번이나 힙이 아닌 다른 자료구조로 푸는 뻘짓을 했다가 .. 

파이썬 힙 자료구조 (heapq)를 공부하며 반성했다 ㅠㅠ 

풀이1 (실패 : deque - 정확도 100, 효율성 0)

from collections import deque
def solution(scoville, K):
    cnt = tmp = 0

    scoville.sort()
    dq = deque(scoville)
    while 1:
        if dq[0]>=K: return cnt
        if cnt==len(scoville)-1: return -1
        
        if dq[0]<K:
            tmp = dq[0]+(dq[1]*2)
            dq.popleft()
            dq.popleft()
            dq.appendleft(tmp)
            cnt+=1
        
        dq = deque(sorted(dq))

자주 쓰는 자료구조인 deque로 풀곤 효율성 시간초과가 나서

혹시 pop을 계속해주는게 문제일까 싶어 리스트로 풀어봤다.

풀이2 (실패 : list - 정확도 100, 효율성 0)

def solution(scoville, K): 
    cnt = tmp = 0
    scoville.sort()
    sc=scoville
    while sc[0]<K:
        if cnt==len(scoville)-1: return -1

        tmp = sc[0]+(sc[1]*2)
        if len(sc)>2:
            sc=sc[2:]
            sc.insert(0,tmp)
        else:
            sc.insert(0,tmp)
            sc=sc[0:1]
        cnt+=1      
        sc.sort()
    return cnt

고작 그런 문제가 아니었고,.. 매번 sort하는 부분이 문제였다.

심지어 슬라이싱 하는게 pop보다 더 느리다고 한다...TT

(웬만해선 리스트보다 데큐가 빠름,, > https://brownbears.tistory.com/452, https://wellsw.tistory.com/122 )

파이썬의 heap 자료구조인 heapq는 이진트리 구조인데 항상 최소힙의 상태를 유지한다!

(최소힙 : 부모 노드의 키값이 자식 노드의 키값보다 항상 작은 힙)

=> 항상 정렬상태 => 이 문제에서 효율성을 위해 heap을 사용해야 하는 이유..

풀이3 (성공 : heap - 정확도 100, 효율성 100)

import heapq as h
def solution(scoville, K): 
    cnt = tmp = 0
    hq=scoville #s리스트 복사 
    h.heapify(hq) #heapq 리스트로 생성 
    
    while hq[0]<K:
        try: h.heappush(hq, h.heappop(hq)+(h.heappop(hq)*2))
        except IndexError: return -1
        cnt+=1
    return cnt

heapq 라는 내장 라이브러리를 사용했다. 

heapq.heappush(리스트, 값)
heapq.heappop(리스트, 값)
heapq.heapify(리스트)

이런 식으로 사용해야 하기 때문에 import 할때 heapq자료구를 h로 별칭을 지었고

초기에 heapify() 메소드로 바로 리스트로 heapq를 초기화 했다.

파이썬 알고리즘에서 try-except 문도 처음 사용해봤는데 앞으로 유용하게 사용할 것 같다.

무지성으로 코딩하는걸 반성하자...

Reference

문제

동물 테이블에서 두번 이상 사용된 이름을 이름순대로 출력하는 문제이다.

동물 이름을 Group by하여 COUNT()로 집계후 HAVING으로 2개 이상인 것을 출력했다.

풀이 (MySQL)

SELECT NAME, COUNT(NAME) AS COUNT
    FROM ANIMAL_INS 
    GROUP BY NAME
    HAVING COUNT(NAME)>=2
ORDER BY NAME

문제

입양간 동물이 2마리 이상인 경우에, 가장 보호기간이 길었던 동물 두마리를 보호기간이 긴 순으로 출력한다.

단순하게 OUTS 테이블의 DATETIME에서 INS 테이블의 DATETIME을 뺀걸 기준으로 LIMIT 2 해서 풀었다.

- 풀이 (MySQL)

SELECT A1.ANIMAL_ID, A1.NAME
    FROM ANIMAL_INS A1, ANIMAL_OUTS A2
    WHERE A1.ANIMAL_ID = A2.ANIMAL_ID
    ORDER BY A2.DATETIME-A1.DATETIME DESC
LIMIT 2

 문제

Milk와 Yogurt 를 동시에 구매한 장바구니 ID를 출력하는 문제이다. 

단순하게 CART_ID를 키로 셀프조인해서 NAME에 Milk와 Yogurt가 있는 CART_ID를 출력했다.

- 풀이 (MySQL)

SELECT C1.CART_ID
    FROM CART_PRODUCTS C1, CART_PRODUCTS C2
    WHERE C1.CART_ID = C2.CART_ID
    AND C1.NAME='Milk'AND C2.NAME='Yogurt'
ORDER BY CART_ID
;

문제

ANIMAL_INS 테이블에서 중성화를 안한 동물이 ANIMAL_OUTS 테이블에서 중성화 된 경우를 출력한다.

ANIMAL_ID를 키로 LEFT JOIN하여 풀었다.

- ORACLE

SELECT A1.ANIMAL_ID, A1.ANIMAL_TYPE, A1.NAME
    FROM ANIMAL_INS A1 LEFT JOIN ANIMAL_OUTS A2
    ON A1.ANIMAL_ID = A2.ANIMAL_ID
    WHERE A1.SEX_UPON_INTAKE LIKE 'Intact%'
    AND A2.SEX_UPON_OUTCOME IN ('Spayed Female','Neutered Male')
ORDER BY ANIMAL_ID
;

- MySQL

SELECT i.ANIMAL_ID, i.ANIMAL_TYPE,i.NAME
    FROM ANIMAL_INS i, ANIMAL_OUTS o
    WHERE i.ANIMAL_ID=o.ANIMAL_ID 
    AND i.SEX_UPON_INTAKE LIKE 'Intact%' 
    AND (o.SEX_UPON_OUTCOME LIKE 'Spayed%' 
    OR o.SEX_UPON_OUTCOME LIKE 'Neutered%')
ORDER BY ANIMAL_ID
;

문제 (2019 KAKAO BLIND RECRUITMENT)

record 문자열배열을 입력받을 때 사용자가 들어오고 나간 이력을 출력하는 문제이다.

닉네임은 변경할 수 있고 최종적으로 변경된 닉네임으로 결과를 출력한다.

풀이

def solution(record):
    dic={}
    res=[]
    id=[]
    
    for i in range(len(record)):
        s = record[i].split()

        if s[0]=='Enter':
            res.append(s[1]+'님이 들어왔습니다.')
            dic[s[1]]=s[2] #id별 이름저장
            id.append(s[1])

        elif s[0]=='Leave':
            res.append(s[1]+'님이 나갔습니다.')
            id.append(s[1])

        elif s[0]=='Change':
            dic[s[1]] = s[2] #이름변경

    for j in range(len(res)):
        tmp=dic[id[j]]
        res[j]=res[j].replace(id[j],tmp)
        
    return res

딕셔너리로 id당 바뀌는 닉네임을 관리하고 사용자가 채팅방에 들어오고 나갈때마다 

'id님이 들어왔습니다/나갔습니다' 로 저장해서 마지막에 id 부분을 최종 닉네임으로 바꿨다.

저 replace() 부분을,,, 좀더 좋은 방법으로 쓸 수 있을 것 같긴한데..

어쨌든 한번에 성공했더니 기분은 좋균 ㅎㅎ

이번주는 구현 위주로 풀고 담주부터 진짜진짜 알고리즘 공부해야지;;