본문 바로가기

All Post269

[프로그래머스] 피로도 (Python) https://programmers.co.kr/learn/courses/30/lessons/87946 코딩테스트 연습 - 피로도 XX게임에는 피로도 시스템(0 이상의 정수로 표현합니다)이 있으며, 일정 피로도를 사용해서 던전을 탐험할 수 있습니다. 이때, 각 던전마다 탐험을 시작하기 위해 필요한 "최소 필요 피로도"와 던 programmers.co.kr 그리디 + 완전 탐색으로 풀었다. 던전 총개수를 세고, 최대 던전 개수부터 내려오면서 순열을 만든 다음 모두 탐색하며 조건에 만족하면 바로 return 하도록 코드를 작성했다. 나의 풀이 from itertools import permutations def solution(k, dungeons): dungeons_count = len(dungeons) d.. 2021. 11. 1.
[프로그래머스] 배달 (Python) https://programmers.co.kr/learn/courses/30/lessons/12978 코딩테스트 연습 - 배달 5 [[1,2,1],[2,3,3],[5,2,2],[1,4,2],[5,3,1],[5,4,2]] 3 4 6 [[1,2,1],[1,3,2],[2,3,2],[3,4,3],[3,5,2],[3,5,3],[5,6,1]] 4 4 programmers.co.kr 다익스트라 알고리즘으로 풀이했다. 주의할 점은 방향성이 없는 간선이므로 도로 정보를 받았을 때 양쪽 마을에 다 추가를 시켜줘야 하고, 간선의 최대 길이는 10,000이지만 배달 시간은 500,000 이하인 것을 주의해서 문제를 풀어야 한다. 나의 풀이 import heapq def solution(N, road, K): answer = .. 2021. 11. 1.
[프로그래머스] 괄호 회전하기 (Python) https://programmers.co.kr/learn/courses/30/lessons/76502 코딩테스트 연습 - 괄호 회전하기 programmers.co.kr 올바른 괄호인지 체크하는 코드와, 왼쪽으로 회전하는 것을 어떻게 짜는지만 고민하면 되는 간단한 구현 문제다. 올바른 괄호 여부에서 dict를 활용하니 훨씬 깔끔하게 풀 수 있었다. 나의 풀이 def check_correct(s): bracket_dict = {']':'[',')':'(','}':'{'} stack = [] for v in s: if len(stack) ==0: stack.append(v) elif v in bracket_dict: if bracket_dict[v] == stack[-1]: stack.pop() else: r.. 2021. 11. 1.
[프로그래머스] 후보키 (Python) https://programmers.co.kr/learn/courses/30/lessons/42890 코딩테스트 연습 - 후보키 [["100","ryan","music","2"],["200","apeach","math","2"],["300","tube","computer","3"],["400","con","computer","4"],["500","muzi","music","3"],["600","apeach","music","2"]] 2 programmers.co.kr 꽤나 애를 먹었던 문제였다. 내가 풀었던 알고리즘은 1. 속성의 개수를 카운트하고 속성을 조합 2. 각 속성으로 유일성을 만족하는지 확인 3. 현재 조합한 속성이 기존에 조합했던 속성과 겹치는 것이 있는지 다시 조합 후 확인(최소성 만족하는.. 2021. 11. 1.
[프로그래머스] 순위 검색(Python) https://programmers.co.kr/learn/courses/30/lessons/72412 = int(want[4]): suc_candidate+=1 answer.append(suc_candidate) return answer 처음에 막 손가는대로 풀었을 때 정확성은 모두 맞았지만 효율성에서 모두 시간 초과가 났다. 리스트를 사용하면서 조회할 때 많은 시간이 걸린다고 판단해서 set이나 dict를 사용해서 풀 생각이 들었다. 수정된 풀이 from itertools import combinations from collections import defaultdict from bisect import bisect_left def combination_cases(data): cases = [] for.. 2021. 11. 1.
[프로그래머스] 예상 대진표(Python) https://programmers.co.kr/learn/courses/30/lessons/12985 코딩테스트 연습 - 예상 대진표 △△ 게임대회가 개최되었습니다. 이 대회는 N명이 참가하고, 토너먼트 형식으로 진행됩니다. N명의 참가자는 각각 1부터 N번을 차례대로 배정받습니다. 그리고, 1번↔2번, 3번↔4번, ... , N-1번↔N programmers.co.kr 대진표 조건에 따라 구현하면 된다. 두 명이 같은 라운드에 있는 경우는 a-b의 절댓값이 1이고 둘을 더한 값에 4를 나눴을 때 나머지가 3이면 성립한다. Ex: (1,2) , (3,4) , (5,6) -> 모두 3+4n의 규칙을 가진다. 다음 라운드의 번호를 구하려면 홀수일 경우 +1 후 2로 나누고 짝수일 경우 그냥 2로 나눠준다 나.. 2021. 10. 31.
[프로그래머스] 게임 맵 최단거리(Python) https://programmers.co.kr/learn/courses/30/lessons/1844 코딩테스트 연습 - 게임 맵 최단거리 [[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,1],[0,0,0,0,1]] 11 [[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,0],[0,0,0,0,1]] -1 programmers.co.kr 전형적인 BFS 문제다 나의 풀이 from collections import deque def solution(maps): n,m = len(maps), len(maps[0]) visited = [[0]*m for _ in range(n)] visited[0][0]=True move = [(1,0),(-1,0.. 2021. 10. 31.
[프로그래머스] 거리두기 확인하기(Python) https://programmers.co.kr/learn/courses/30/lessons/81302 코딩테스트 연습 - 거리두기 확인하기 [["POOOP", "OXXOX", "OPXPX", "OOXOX", "POXXP"], ["POOPX", "OXPXP", "PXXXO", "OXXXO", "OOOPP"], ["PXOPX", "OXOXP", "OXPOX", "OXXOP", "PXPOX"], ["OOOXX", "XOOOX", "OOOXX", "OXOOX", "OOOOO"], ["PXPXP", "XPXPX", "PXPXP", "XPXPX", "PXPXP"]] [1, 0, 1, 1, 1] programmers.co.kr 맨해튼 거리 1일 때, 2일 때를 나눠서 생각해보면 쉽게 풀 수 있는 문제였다. 확실히 2.. 2021. 10. 31.
[프로그래머스] 뉴스 클러스터링(Python) https://programmers.co.kr/learn/courses/30/lessons/17677 코딩테스트 연습 - [1차] 뉴스 클러스터링 뉴스 클러스터링 여러 언론사에서 쏟아지는 뉴스, 특히 속보성 뉴스를 보면 비슷비슷한 제목의 기사가 많아 정작 필요한 기사를 찾기가 어렵다. Daum 뉴스의 개발 업무를 맡게 된 신입사원 튜브 programmers.co.kr Counter를 활용해서 주어진 조건대로 구현해서 풀었다. 나의 풀이 from collections import Counter def solution(str1, str2): str1 = str1.upper() str2 = str2.upper() intersection, union = 0 , 0 word_list1, word_list2 = [.. 2021. 10. 30.
[프로그래머스] 셔틀버스 (Python) https://programmers.co.kr/learn/courses/30/lessons/17678 코딩테스트 연습 - [1차] 셔틀버스 10 60 45 ["23:59","23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59"] "18:00" programmers.co.kr 나의 풀이 그다지 잘 푼 느낌이 아니다. 그냥 알고리즘 짜고 그대로 구현하긴 했다. 더 깔끔하게 풀 수 있을 것 같은데 아직 많이 부족하다ㅠ 알고리즘 순서는 1. 셔틀버스 도착 시간 순서로 dict 초기화하고 2. 정렬된 timetable을 바탕으로 도.. 2021. 10. 30.
[프로그래머스] 베스트앨범 (Python) https://programmers.co.kr/learn/courses/30/lessons/42579 코딩테스트 연습 - 베스트앨범 스트리밍 사이트에서 장르 별로 가장 많이 재생된 노래를 두 개씩 모아 베스트 앨범을 출시하려 합니다. 노래는 고유 번호로 구분하며, 노래를 수록하는 기준은 다음과 같습니다. 속한 노래가 programmers.co.kr 충분히 풀 수는 있지만 뭔가 코드가 효율적이지 않은 것 같은 느낌이 드는 풀이였다. 시간 복잡도는 O(N)이라 나쁘지 않을 수도? 1. 장르별로 값을 dict에 초기화해주고, 판매수는 큰 순으로, 같을 때 고유 번호는 작은 순으로 정렬한다. 2. 각 장르별로 총판매수를 구하고, 총판매수가 큰 순으로 장르를 정렬한다. 3. 판매수가 큰 장르부터 두 개씩 뽑아서 .. 2021. 10. 29.
[프로그래머스] 위장 (Python) https://programmers.co.kr/learn/courses/30/lessons/42578 코딩테스트 연습 - 위장 programmers.co.kr 각 옷의 종류에 따라 dict를 초기화하고, 그 옷의 조합인 (N+1)*(M+1) -1 하면 된다. (-1은 모든 옷 종류 꺼내지 않았을 경우는 인정되지 않으므로 하나 빼 주는 것) 나의 풀이 from collections import defaultdict def solution(clothes): answer = 1 cloth_dict = defaultdict(list) for cloth in clothes: cloth_dict[cloth[1]].append(cloth[0]) for cloth in cloth_dict.values(): answer.. 2021. 10. 29.
[프로그래머스] 소수 찾기 (Python) https://programmers.co.kr/learn/courses/30/lessons/42839 코딩테스트 연습 - 소수 찾기 한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다. 각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 programmers.co.kr itertools의 permutations와 에라토스테네스의 체를 활용해서 문제를 풀었다. 나의 코드 from itertools import permutations def solution(numbers): def prime_list(n): # 에라토스테네스의 체 초기화: n개 요소에 True 설정(소수로 간주) sieve = [True] * n m.. 2021. 10. 29.
[프로그래머스] H-Index (Python) https://programmers.co.kr/learn/courses/30/lessons/42747 코딩테스트 연습 - H-Index H-Index는 과학자의 생산성과 영향력을 나타내는 지표입니다. 어느 과학자의 H-Index를 나타내는 값인 h를 구하려고 합니다. 위키백과1에 따르면, H-Index는 다음과 같이 구합니다. 어떤 과학자가 발표 programmers.co.kr 주어진 조건대로 구현하면 된다. 나의 코드 def solution(citations): citations.sort(reverse=True) answer = len(citations) -1 if citations[-1] >= answer+1: return answer+1 while answer > 0: if citations[ans.. 2021. 10. 29.
[프로그래머스] 단속카메라 (Python) https://programmers.co.kr/learn/courses/30/lessons/42884 코딩테스트 연습 - 단속카메라 [[-20,-15], [-14,-5], [-18,-13], [-5,-3]] 2 programmers.co.kr 그렇게 어렵지 않았던 문제였다. 자동차를 정렬하고 카메라 범위를 좁혀가면 풀렸다. 나의 풀이 def solution(routes): answer = 1 check = [-30001,30001] routes.sort() for route in routes: print(check,route) if check[0] 2021. 10. 28.

티스토리툴바