반응형 프로그래머스13 [프로그래머스] 게임 맵 최단거리(level2) (자바) package com.programmers; import java.util.LinkedList; import java.util.Queue; /** * https://programmers.co.kr/learn/courses/30/lessons/1844?language=java * 방문 처리를 해버리면 다른 루트에서 접근할 때 도착하지를 못한다. bfs일 경우 최단 거리로 갈 수 있기 때문에 방문처리를 false로 바꿀 일이 필요 없다. */ public class 게임맵_최단거리 { public static void main(String[] args) { int[][] maps = { {1, 0, 1, 1, 1}, {1, 0, 1, 0, 1}, {1, 0, 1, 1, 1}, {1, 1, 1, 0, 1}, .. 2021. 11. 14. [프로그래머스] N개의 최소공배수 (자바) 문제 풀이 유클리드호제(최대공약수) 알고리즘을 활용하여 풀 수 있다. package com.programmers; /* 문제 설명 두 수의 최소공배수(Least Commontem Multiple)란 입력된 두 수의 배수 중 공통이 되는 가장 작은 숫자를 의미합니다. 예를 들어 2와 7의 최소공배수는 14가 됩니다. 정의를 확장해서, n개의 수의 최소공배수는 n 개의 수들의 배수 중 공통이 되는 가장 작은 숫자가 됩니다. n개의 숫자를 담은 배열 arr이 입력되었을 때 이 수들의 최소공배수를 반환하는 함수, solution을 완성해 주세요. 제한 사항 arr은 길이 1이상, 15이하인 배열입니다. arr의 원소는 100 이하인 자연수입니다. 입출력 예 arr result [2,6,8,14] 168 [1,2.. 2021. 10. 17. [프로그래머스] 큰 수 만들기 (level2) (자바) 문제 풀이 문제를 잘 파악하는 것이 중요하다. 힙소트(오답) -> 조합(시간초과) -> 풀이(그리디)를 보고 문제를 풀 수 있었다. package com.programmers; import java.util.PriorityQueue; import java.util.Queue; /** * 문제 설명 * 어떤 숫자에서 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 숫자를 구하려 합니다. * * 예를 들어, 숫자 1924에서 수 두 개를 제거하면 [19, 12, 14, 92, 94, 24] 를 만들 수 있습니다. 이 중 가장 큰 숫자는 94 입니다. * * 문자열 형식으로 숫자 number와 제거할 수의 개수 k가 solution 함수의 매개변수로 주어집니다. number에서 k 개의 수를 제거했을 때 만들.. 2021. 10. 17. [프로그래머스] 야근 지수 (level3) (파이썬) 문제 접근 정렬 된 최대 값이 필요하므로 우선순위큐로 표현해야 된다고 생각하였다 가장 빠른 삽입 삭제 시간복잡도 N(데이터) logN을 가진 힙(heap)을 이용하여 문제를 접근 풀이 코드 # 19:10 ~ 19:30 # https://programmers.co.kr/learn/courses/30/lessons/12927?language=python3# import heapq def solution(n, works): answer = 0 h = [] # 우선순위 큐 최대힙으로 저장 for value in works: heapq.heappush(h, -value) while n > 0: # 힙에서 하나 꺼내어 다시 넣음 work = -heapq.heappop(h) if work != 0: heapq.hea.. 2021. 6. 28. [프로그래머스] 더 맵게 (level2) (파이썬) 문제 접근 힙의 특징을 이용하여 문제를 푼다. 문제 해결 # 09:30 ~ 09:55 # https://programmers.co.kr/learn/courses/30/lessons/42626?language=python3 # 정렬 시간 복잡도 NlogN, 삽입 삭제 logN # heapq.heappush() 삽입 # heapq.heappop() 꺼냄 import heapq def solution(scoville, K): # 모든 음식의 스코빌 지수를 K이상으로 만들 수 없는 경우 -1 return answer = -1 count = 0 flag = True h = [] for value in scoville: heapq.heappush(h, value) # pop 하면서 스코빌 지수와 체크 하며 섞을지 .. 2021. 6. 28. [프로그래머스 ] 짝지어 제거하기 (level2) (파이썬) 문제 접근 스택에 쌓으면서 짝이 지어지면 바로바로 제거하는 방식을 선택하였다 풀이 코드 # https://programmers.co.kr/learn/courses/30/lessons/12973?language=python3 # 9:40 ~ 09:52 def solution(s): answer = -1 stack = [] for i in s: if len(stack) != 0: if stack[-1] == i: stack.pop() else: stack.append(i) else: stack.append(i) if len(stack) == 0: answer = 1 else: answer = 0 return answer 2021. 6. 21. [프로그래머스] Summer/Winter Coding(~2018) 소수 만들기 (파이썬) 문제 접근 소수의 판별을 할 줄 알면 풀 수 있던 문제 에라토스테네스의 체를 기억하자 2021.03.08 - [Problem-solved (코딩테스트 문제풀이)/python] - [백준] 소수 구하기 1929 (파이썬) # Summer/Winter Coding(~2018) 소수 만들기 import math from itertools import combinations def solution(nums): # 에라토스테네스의 체를 이용하여 해당 범위의 소수를 판별한다. # 1~1000 사이의 자연수를 3개 고르므로 단순히 합의 최대값을 3000이라고 설정하였다 n = 3000 array = [True for i in range(n+1)] for i in range(2, int(math.sqrt(n) + 1).. 2021. 6. 18. [프로그래머스] 예상 대진표(level 2) (파이썬) 문제 접근 수학 문제 a,b 중 b가 큰것이 보장된다면 둘이 만나는 경우는 b가 2의 지수이면서 b - 1이 a일 때 뿐이다. 코드 # 13:45 ~ 14:10 import math def solution(n,a,b): if a > b: a, b = b, a cnt = 1 while True: if b % 2 == 0 and b - a == 1: break a = math.ceil(a/2) b = math.ceil(b/2) cnt += 1 return cnt 노트 2021. 5. 19. [프로그래머스] 위장(level 2) (파이썬) 접근 경우의 수를 잘 생각해야 하는 문제 최소한 1개의 옷을 입어야 하므로 모두 안입은 경우를 -1 해야 한다. 각각의 경우의 수에서 옷의 종류는 독립변수로 작용한다. # 위장 level2 # 3시 57분 ~ 4시 43분 # 경우의 수 문제 종류가 2인 경우 00, 10, 01, 11 2*2 -1(00) def solution(clothes): answer = 1 hmap = dict() for i in range(len(clothes)): if clothes[i][1] in hmap.keys(): hmap[clothes[i][1]] = hmap[clothes[i][1]] + 1 else: hmap[clothes[i][1]] = 1 value_list = hmap.values() for value in .. 2021. 5. 18. [프로그래머스] 다음 큰 숫자(level 2) (파이썬) 접근 2진수로 변환 하는 함수를 알아야했다 (bin이나 format 방식을 이용한다) 숫자를 하나 씩 늘려가며 일치할 시에 반복문을 빠져나오면 된다. # 다음 큰 숫자 # https://programmers.co.kr/learn/courses/30/lessons/12911 # 3시 8분 - 3시 25분 (17분) def solution(n): b_origin = str(format(n, 'b')) b_count = b_origin.count('1') num = n while True: num += 1 v = str(format(num, 'b')) if v.count('1') == b_count: return num def solution2(n): cnt = format(n, 'b').count('1') .. 2021. 5. 18. [프로그래머스] 기능 개발(level 2) (파이썬) 문제 접근 간단한 문제로 생각했으나 문제를 잘 못 파악한 것이 코드를 잘못작성하는 것으로 이어졌다. 문제파악을 잘하는 것이 중요할 것 같다 # https://programmers.co.kr/learn/courses/30/lessons/42586?language=python3 # 내가 푼 것 (1차) from collections import deque import math from collections import deque import math def solution(progresses, speeds): answer = [] q = deque() time = 0 # 누적된 시간을 나타냄 for i in range(len(speeds)): day = math.ceil((100 - progresses[i].. 2021. 5. 10. [프로그래머스] 주식가격(level 2) (파이썬) 문제접근 스택 큐 유형이며 level2 문제였으나 이중 반복문으로 충분히 풀 수 있을 것 같아 이중반복문으로 구현하였다. 스택 큐 쪽으로는 문제접근 방식이 생각나지 않는다. https://programmers.co.kr/learn/courses/30/lessons/42584 코딩테스트 연습 - 주식가격 초 단위로 기록된 주식가격이 담긴 배열 prices가 매개변수로 주어질 때, 가격이 떨어지지 않은 기간은 몇 초인지를 return 하도록 solution 함수를 완성하세요. 제한사항 prices의 각 가격은 1 이상 10,00 programmers.co.kr def solution(prices): answer = [0] * len(prices) for i in range(len(prices)): for j.. 2021. 5. 7. [프로그래머스] [oracle] [sql] 입양시각 구하기 /* 문제 설명 ANIMAL_OUTS 테이블은 동물 보호소에서 입양 보낸 동물의 정보를 담은 테이블입니다. ANIMAL_OUTS 테이블 구조는 다음과 같으며, ANIMAL_ID, ANIMAL_TYPE, DATETIME, NAME, SEX_UPON_OUTCOME는 각각 동물의 아이디, 생물 종, 입양일, 이름, 성별 및 중성화 여부를 나타냅니다. NAME TYPE NULLABLE ANIMAL_ID VARCHAR(N) FALSE ANIMAL_TYPE VARCHAR(N) FALSE DATETIME DATETIME FALSE NAME VARCHAR(N) TRUE SEX_UPON_OUTCOME VARCHAR(N) FALSE 보호소에서는 몇 시에 입양이 가장 활발하게 일어나는지 알아보려 합니다. 0시부터 23시까지.. 2020. 11. 8. 이전 1 다음 반응형
