코딩하는 eroke

문제

로또 번호로 가능한 최고 등수와 최저 등수를 리턴하는 문제이다.

로또 숫자는 1~45인데, 0인 경우는 알아볼 수 없는 숫자이다.

그래서 0의 개수에 따라 가능한 최고 등수가 바뀐다.

14번 케이스만 계속 틀려서 시간이 좀 걸렸는데 0의 개수도 없고 6개 다 틀린경우를

생각하지 못했다ㅠ 어떤 문제든 제약사항을 잘 고려해야 하는 것 같다.

풀이 (Python)

def solution(lottos, win_nums):
    #0 없앰
    notzero = set(lottos) 
    if 0 in notzero: notzero.remove(0) #0이 한개일 경우 
    
    if len(notzero)==0: return [1,6]

    zero_cnt = len(lottos) - len(notzero) #0 개수
    lotto_len = len(set(win_nums)-set(notzero)) #1등과 차이 개수 
    
    if lotto_len==0: return [1,1]
    elif zero_cnt==0 and lotto_len==6: return [6,6]
    else:
        if zero_cnt==0: return [lotto_len+1,lotto_len+1]
        else: return [lotto_len-zero_cnt+1,lotto_len+1]

문제

입력 : n=수빈시작위치, k=동생위치(도착지점)

출력 : 수빈이가 걷거나 순간이동한 횟수 

예를들어 n=5, k=17 일떼, 수빈이가 5-10-9-18-17 순으로 가면 4번 만에 동생을 찾을 수 있다.

풀이

from collections import deque

MAX=10**5
dp=[0]*(MAX+1)
dq = deque()

n,k = map(int,input().split())
dq.append(n)
while dq:
    c=dq.popleft() #current
    if c==k:
        print(dp[k])
        break

    for nc in (c-1,c+1,c*2):
        if 0<=nc<=MAX and dp[nc]==0:
            dp[nc]=dp[c]+1
            dq.append(nc)

큐에 현재 위치 c와 다음 위치 c-1, c+1, c*2를 넣으며 횟수를 추가했다.

문제

입력 : n = 동전의 가치, k = 만들어야 할 가치

출력 : 사용한 동전의 개수

동전 종류는 k가치보다 큰 경우가 있을 수 있다.

입력받은 동전 종류는 오름차순 정렬이 된채로 입력이 되기 때문에

동전배열 맨 뒤에서부터 가치 계산을 하도록 접근했다.

풀이

n,k = map(int,input().split())
coin=[0]*n

for i in range(n):
    coin[i]=int(input())

cnt=tmp=0
for i in range(n-1,-1,-1):
    if k>=coin[i] :
        tmp=k//coin[i]
        k-=(tmp*coin[i])
        if tmp==0: cnt+=1
        else: cnt+=tmp

print(cnt)

처음엔 그냥 for문 안에 while을 넣었다가 시간초과가 났고

그 다음은 세부조건을 고려하지 않아 오류가 났다... 따흑

문제

nums 배열에 n개의 폰켓몬 수가 주어지고 최대 n/2마리 폰켓몬을 선택해야하는데 

중복없이 선택해야하는 문제이다.

풀이

def solution(nums):
    
    po=len(nums)//2
    snums = set(nums)

    if len(snums)<po:
        return len(snums)
    else:
        return po

파이썬의 set으로 nums에서 중복제거 후 n/2와 비교하여 선택할 수 있는 수를 return했다.

문제

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