문제

 

코딩테스트 연습 - 로또의 최고 순위와 최저 순위

로또 6/45(이하 '로또'로 표기)는 1부터 45까지의 숫자 중 6개를 찍어서 맞히는 대표적인 복권입니다. 아래는 로또의 순위를 정하는 방식입니다. 1 순위 당첨 내용 1 6개 번호가 모두 일치 2 5개 번호

programmers.co.kr

 

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

로또 숫자는 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]

 

파이썬 쏠!

 

반응형

문제

 

1697번: 숨바꼭질

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일

www.acmicpc.net

 

입력 : 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를 넣으며 횟수를 추가했다.

 

 

 

반응형

문제

 

11047번: 동전 0

첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수)

www.acmicpc.net

 

 

입력 : 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을 넣었다가 시간초과가 났고

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

 

 

반응형

문제

 

코딩테스트 연습 - 폰켓몬

당신은 폰켓몬을 잡기 위한 오랜 여행 끝에, 홍 박사님의 연구실에 도착했습니다. 홍 박사님은 당신에게 자신의 연구실에 있는 총 N 마리의 폰켓몬 중에서 N/2마리를 가져가도 좋다고 했습니다.

programmers.co.kr

 

 

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했다.

반응형

문제

 

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

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

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
반응형

+ Recent posts