문제

 

코딩테스트 연습 - 신고 결과 받기

문제 설명 신입사원 무지는 게시판 불량 이용자를 신고하고 처리 결과를 메일로 발송하는 시스템을 개발하려 합니다. 무지가 개발하려는 시스템은 다음과 같습니다. 각 유저는 한 번에 한 명의

programmers.co.kr

 

출처 : 프로그래머스

 

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를 사용하지 않고있는데

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

반응형

문제

 

코딩테스트 연습 - 크레인 인형뽑기 게임

[[0,0,0,0,0],[0,0,1,0,3],[0,2,5,0,1],[4,2,4,4,2],[3,5,1,3,1]] [1,5,3,5,1,2,1,4] 4

programmers.co.kr

 

출처 : 프로그래머스 - 크레인 인형뽑기 문제

 

그림이 있어서 일단 풀기 싫었지만 레벨 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개 붙어 있는 짝을 찾습니다. 그다음, 그 둘을 제거한 뒤, 앞뒤로 문자열을 이어 붙

programmers.co.kr

 

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

먼저 문자열에서 같은 알파벳이 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)

 

 

문제

 

코딩테스트 연습 - 이중우선순위큐

 

programmers.co.kr

 

입출력 예시

 

문자열로 들어오는 명령어로 값을 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개의 힙으로 풀었다..

 

반응형

문제

 

코딩테스트 연습 - 더 맵게

매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같

programmers.co.kr

 

프로그래머스 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

 

[Python] 리스트 slice, pop, del 성능 비교 및 사용방법

slice, pop, del 사용방법 remove() remove()는 지우고자 하는 인덱스가 아닌, 값을 입력하는 방식입니다. 만약 지우고자 하는 값이 리스트 내에 2개 이상이 있다면 순서상 가장 앞에 있는 값을 지우게 됩

brownbears.tistory.com

 

 

[Python] 힙 자료구조 / 힙큐(heapq) / 파이썬에서 heapq 모듈 사용하기

힙은 특정한 규칙을 가지는 트리로, 최댓값과 최솟값을 찾는 연산을 빠르게 하기 위해 고안된 완전이진트리를 기본으로 한다. 힙 property : A가 B의 부모노드이면 A의 키값과 B의 키값 사이에는 대

littlefoxdiary.tistory.com

 

 

[파이썬] 덱 vs 리스트 속도 차이? (deque vs list speed 차이)

덱과 리스트? 여러분은 어떤 차이를 두고 두 자료구조를 적절하게 사용하시나요? 둘 다 사용상에는 큰 차이가 없어 보입니다. 그렇지만, 이 자료구조를 어떤 상황에서 어떻게 사용하느냐에 따라

wellsw.tistory.com

 

05-4 예외 처리

프로그램을 만들다 보면 수없이 많은 오류를 만나게 된다. 물론 오류가 발생하는 이유는 프로그램이 잘못 동작하는 것을 막기 위한 파이썬의 배려이다. 하지만 때때로 이러한 오류 ...

wikidocs.net

 

반응형

문제

 

코딩테스트 연습 - 동명 동물 수 찾기

ANIMAL_INS 테이블은 동물 보호소에 들어온 동물의 정보를 담은 테이블입니다. ANIMAL_INS 테이블 구조는 다음과 같으며, ANIMAL_ID, ANIMAL_TYPE, DATETIME, INTAKE_CONDITION, NAME, SEX_UPON_INTAKE는 각각 동물의 아이디

programmers.co.kr

 

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

동물 이름을 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)

ANIMAL_INS 테이블은 동물 보호소에 들어온 동물의 정보를 담은 테이블입니다. ANIMAL_INS 테이블 구조는 다음과 같으며, ANIMAL_ID, ANIMAL_TYPE, DATETIME, INTAKE_CONDITION, NAME, SEX_UPON_INTAKE는 각각 동물의 아이디

programmers.co.kr

입출력 예제

 

입양간 동물이 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
반응형

 문제

 

코딩테스트 연습 - 우유와 요거트가 담긴 장바구니

CART_PRODUCTS 테이블은 장바구니에 담긴 상품 정보를 담은 테이블입니다. CART_PRODUCTS 테이블의 구조는 다음과 같으며, ID, CART_ID, NAME, PRICE는 각각 테이블의 아이디, 장바구니의 아이디, 상품 종류, 가

programmers.co.kr

 

입력예제

 

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_INS 테이블 구조는 다음과 같으며, ANIMAL_ID, ANIMAL_TYPE, DATETIME, INTAKE_CONDITION, NAME, SEX_UPON_INTAKE는 각각 동물의 아이디

programmers.co.kr

입출력 예제

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)

 

코딩테스트 연습 - 오픈채팅방

오픈채팅방 카카오톡 오픈채팅방에서는 친구가 아닌 사람들과 대화를 할 수 있는데, 본래 닉네임이 아닌 가상의 닉네임을 사용하여 채팅방에 들어갈 수 있다. 신입사원인 김크루는 카카오톡 오

programmers.co.kr

입출력 예시

 

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() 부분을,,, 좀더 좋은 방법으로 쓸 수 있을 것 같긴한데..

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

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

반응형

+ Recent posts