본문 바로가기

Programming/Programmers149

[프로그래머스] 무지의 먹방 라이브 (Python) https://programmers.co.kr/learn/courses/30/lessons/42891 코딩테스트 연습 - 무지의 먹방 라이브 programmers.co.kr 딕셔너리 + 정렬을 활용해서 문제를 풀었다. 효율성에서 아슬아슬하게 통과해서 더 좋은 풀이가 있을 것 같다. 알고리즘 : 1. 먹는 것이 종료되는 시간이 같은 음식을 dict를 통해 세어 준다. (defaultdict 활용) 2. 짧은 시간 순서대로 dict.items를 정렬한다. - food_times의 입력이 [6, 6, 1, 1, 2, 2, 3, 5] 일 경우 아래와 같이 정렬됨. - Tsort => [(1, 2), (2, 2), (3, 1), (5, 1), (6, 2)] (음식 다 먹는 시간, 그 음식의 개수) 3. 정렬된 T.. 2021. 12. 28.
[프로그래머스] 가사 검색 (Python) https://programmers.co.kr/learn/courses/30/lessons/60060 코딩테스트 연습 - 가사 검색 programmers.co.kr 문자열 검색 알고리즘인 Trie를 활용해서 푸는 문제다 계속 효율성 4번에서 시간 초과가 나서 풀이를 참고하고 그대로 구현했다. class Trie(): def __init__(self): self.child = dict() self.count = 0 def insert(self,str): curr = self for ch in str: curr.count += 1 if ch not in curr.child: curr.child[ch] = Trie() curr = curr.child[ch] curr.count += 1 def search(se.. 2021. 12. 27.
[프로그래머스] 단어 퍼즐(Python) https://programmers.co.kr/learn/courses/30/lessons/12983 코딩테스트 연습 - 단어 퍼즐 단어 퍼즐은 주어진 단어 조각들을 이용해서 주어진 문장을 완성하는 퍼즐입니다. 이때, 주어진 각 단어 조각들은 각각 무한개씩 있다고 가정합니다. 예를 들어 주어진 단어 조각이 [“ba”, “na programmers.co.kr dp 활용 문제다. 처음에 그리디 + dfs로 풀었는데 시간 초과가 났다. dp를 생각하긴 했는데 dp에 익숙하지 않아서 다른 사람 풀이를 참고했다. dp를 설계할 때 일반적으로 원하는 답을 설정하면 구하기 쉽다. 이 문제는 각 위치에서 단어조각 개수의 최솟값을 return 하는 문제이므로 dp를 각 위치에서의 최소 단어조각 개수로 설정해주고 문제를 .. 2021. 12. 22.
[프로그래머스] 실패율 (Python) https://programmers.co.kr/learn/courses/30/lessons/42889 코딩테스트 연습 - 실패율 실패율 슈퍼 게임 개발자 오렐리는 큰 고민에 빠졌다. 그녀가 만든 프랜즈 오천성이 대성공을 거뒀지만, 요즘 신규 사용자의 수가 급감한 것이다. 원인은 신규 사용자와 기존 사용자 사이에 스 programmers.co.kr dict 활용 문제다 defaultdict 활용하면 좀 더 편하긴 함. - dict 정렬 참고 나의 풀이 def solution(N,stages): member = len(stages) counting = {} result = {} for stage in stages: if counting.get(stage): counting[stage] += 1 else: c.. 2021. 12. 21.
[프로그래머스] 지형 이동 (Python) https://programmers.co.kr/learn/courses/30/lessons/62050 코딩테스트 연습 - 지형 이동 [[1, 4, 8, 10], [5, 5, 5, 5], [10, 10, 10, 10], [10, 10, 10, 20]] 3 15 [[10, 11, 10, 11], [2, 21, 20, 10], [1, 20, 21, 11], [2, 1, 2, 1]] 1 18 programmers.co.kr 이동하는 것은 dfs와 최소 비용 사다리는 heapq를 활용해서 풀었다 dfs + heapq 알고리즘 1. 0, 0 에서 방문 가능한 곳 방문(height) 2. height 차 때문에 방문 못하면 height차이와 x , y 를 heapq에 저장 3. 이동 할 수 있는 곳 모두 이동 했을 .. 2021. 12. 20.
[프로그래머스] 지형 이동 (Python) https://programmers.co.kr/learn/courses/30/lessons/62050 코딩테스트 연습 - 지형 이동 [[1, 4, 8, 10], [5, 5, 5, 5], [10, 10, 10, 10], [10, 10, 10, 20]] 3 15 [[10, 11, 10, 11], [2, 21, 20, 10], [1, 20, 21, 11], [2, 1, 2, 1]] 1 18 programmers.co.kr 이동하는 것은 dfs와 최소 비용 사다리는 heapq를 활용해서 풀었다 dfs + heapq 알고리즘 1. 0, 0 에서 방문 가능한 곳 방문(height) 2. height 차 때문에 방문 못하면 height차이와 x , y 를 heapq에 저장 3. 이동 할 수 있는 곳 모두 이동 했을 .. 2021. 12. 20.
[프로그래머스] 동굴 탐험 (Python) https://programmers.co.kr/learn/courses/30/lessons/67260 코딩테스트 연습 - 동굴 탐험 9 [[0,1],[0,3],[0,7],[8,1],[3,6],[1,2],[4,7],[7,5]] [[8,5],[6,7],[4,1]] true 9 [[8,1],[0,1],[1,2],[0,7],[4,7],[0,3],[7,5],[3,6]] [[4,1],[5,2]] true 9 [[0,1],[0,3],[0,7],[8,1],[3,6],[1,2],[4,7],[7,5]] [[4,1],[8,7],[6,5]] false programmers.co.kr DFS에 조건을 잘 걸어야 하는 문제다 from collections import defaultdict import sys sys.setrecu.. 2021. 12. 9.
[프로그래머스] 퍼즐 조각 채우기 (Python) https://programmers.co.kr/learn/courses/30/lessons/84021 코딩테스트 연습 - 퍼즐 조각 채우기 [[1,1,0,0,1,0],[0,0,1,0,1,0],[0,1,1,0,0,1],[1,1,0,1,1,1],[1,0,0,0,1,0],[0,1,1,1,0,0]] [[1,0,0,1,1,0],[1,0,1,0,1,0],[0,1,1,0,1,1],[0,0,1,0,0,0],[1,1,0,1,1,0],[0,1,0,0,0,0]] 14 [[0,0,0],[1,1,0],[1,1,1]] [[1,1,1],[1,0,0],[0,0,0]] 0 programmers.co.kr dfs로 풀이했다. 알고리즘은 다음과 같다. 1. 게임보드의 모양을 구한다. 모양은 2차원 배열의 좌표 순서대로 찾으며, 방문하지 .. 2021. 11. 29.
[프로그래머스] 표 편집 (Python) https://programmers.co.kr/learn/courses/30/lessons/81303 코딩테스트 연습 - 표 편집 8 2 ["D 2","C","U 3","C","D 4","C","U 2","Z","Z"] "OOOOXOOO" 8 2 ["D 2","C","U 3","C","D 4","C","U 2","Z","Z","U 1","C"] "OOXOXOOO" programmers.co.kr 연결리스트를 활용해서 풀어야 하는 문제다 트리나 연결리스트를 활용하는 방법을 정리해놔야겠다. class Node: def __init__(self): self.prev = None self.next = None self.removed = False def solution(n, k, cmd): linkedList .. 2021. 11. 24.
[프로그래머스] N-Queen (Python) https://programmers.co.kr/learn/courses/30/lessons/12952 코딩테스트 연습 - N-Queen 가로, 세로 길이가 n인 정사각형으로된 체스판이 있습니다. 체스판 위의 n개의 퀸이 서로를 공격할 수 없도록 배치하고 싶습니다. 예를 들어서 n이 4인경우 다음과 같이 퀸을 배치하면 n개의 퀸은 programmers.co.kr 다른 풀이를 참고했다. 아직 dfs를 짜는데 좀 익숙하지 않은 것 같다. 나중에 다시 살펴봐야겠다. import sys sys.setrecursionlimit(10**6) def dfs(queen,n,row): answer = 0 if n == row: return 1 for i in range(n): queen[row] = i for j in r.. 2021. 11. 23.
[프로그래머스] 하노이의 탑 (Python) https://programmers.co.kr/learn/courses/30/lessons/12946 코딩테스트 연습 - 하노이의 탑 하노이 탑(Tower of Hanoi)은 퍼즐의 일종입니다. 세 개의 기둥과 이 기동에 꽂을 수 있는 크기가 다양한 원판들이 있고, 퍼즐을 시작하기 전에는 한 기둥에 원판들이 작은 것이 위에 있도록 순서대 programmers.co.kr 대표적인 재귀 문제다. 나의 풀이 import sys sys.setrecursionlimit(10**6) answer = [] def hanoi(n, from_col, to_col, assi_col): global answer if n == 1: answer.append([from_col, to_col]) return hanoi(n-1, .. 2021. 11. 23.
[프로그래머스] 스티커 모으기(2) (Python) https://programmers.co.kr/learn/courses/30/lessons/12971 코딩테스트 연습 - 스티커 모으기(2) N개의 스티커가 원형으로 연결되어 있습니다. 다음 그림은 N = 8인 경우의 예시입니다. 원형으로 연결된 스티커에서 몇 장의 스티커를 뜯어내어 뜯어낸 스티커에 적힌 숫자의 합이 최대가 되도록 programmers.co.kr DP 유형의 문제다. 첫 번째 스티커를 찢는 경우, 찢지 않는 경우를 따져서 문제를 풀면 된다. 나의 풀이 def solution(sticker): if len(sticker) 2021. 11. 23.
[프로그래머스] 숫자 게임 (Python) https://programmers.co.kr/learn/courses/30/lessons/12987 코딩테스트 연습 - 숫자 게임 xx 회사의 2xN명의 사원들은 N명씩 두 팀으로 나눠 숫자 게임을 하려고 합니다. 두 개의 팀을 각각 A팀과 B팀이라고 하겠습니다. 숫자 게임의 규칙은 다음과 같습니다. 먼저 모든 사원이 무작위로 programmers.co.kr 정렬을 활용하면 되는 문제다 나의 풀이 def solution(A, B): answer = 0 A.sort() B.sort() A_now, B_now = 0,0 while B_now < len(B): if A[A_now] < B[B_now]: answer+=1 A_now +=1 B_now +=1 else: B_now +=1 return answer 2021. 11. 23.
[프로그래머스] 기지국 설치 (Python) https://programmers.co.kr/learn/courses/30/lessons/12979 코딩테스트 연습 - 기지국 설치 N개의 아파트가 일렬로 쭉 늘어서 있습니다. 이 중에서 일부 아파트 옥상에는 4g 기지국이 설치되어 있습니다. 기술이 발전해 5g 수요가 높아져 4g 기지국을 5g 기지국으로 바꾸려 합니다. 그런데 5 programmers.co.kr N의 범위를 보면 N: 200,000,000 이하의 자연수라 되어있기 때문에 N을 기준으로 풀면 시간 초과가 난다. 따라서 stations을 바탕으로 알고리즘을 생각했다. 해당 기지국의 커버 범위에 따라 추가해야 하는 기지국 값을 answer에 추가해준다. 나의 풀이 def solution(n, stations, w): start = 1 an.. 2021. 11. 23.
[프로그래머스] 블록 이동하기 (Python) https://programmers.co.kr/learn/courses/30/lessons/60063 코딩테스트 연습 - 블록 이동하기 [[0, 0, 0, 1, 1],[0, 0, 0, 1, 0],[0, 1, 0, 1, 1],[1, 1, 0, 0, 1],[0, 0, 0, 0, 0]] 7 programmers.co.kr 힘든 구현 문제다. 이게 맞나 싶으면서 그냥 구현했다. bfs로 풀었다. 나의 풀이 from collections import deque,defaultdict def solution(board): length = len(board) visited = defaultdict(int) visited[(0,0,0,1)] = 1 q = deque([(0,0,0,1,0)]) while q: x, y, .. 2021. 11. 18.

티스토리툴바