본문 바로가기
반응형

프로그래머스16

[프로그래머스] 전화번호목록 (자바) 프로그래머스 고득점 Kit: 해시 - 전화번호 목록문제 설명"전화번호 목록" 문제는 전화번호 목록이 주어졌을 때, 어떤 번호가 다른 번호의 접두어인 경우가 있는지 확인하는 문제입니다. 예를 들어, 전화번호 "119"는 "1195524421"의 접두어입니다. 전화번호 목록에 접두어 관계가 하나라도 있으면 false를 반환하고, 그렇지 않으면 true를 반환해야 합니다.문제 접근 방법HashMap 사용: 모든 전화번호를 HashMap에 저장합니다.접두어 확인: 각 전화번호의 모든 접두어를 확인하면서, 해당 접두어가 HashMap에 존재하는지 검사합니다.시간 복잡도 분석전화번호의 수를 N, 각 전화번호의 길이를 L이라고 할 때, 시간 복잡도는 O(N * L^2)입니다.전화번호 목록을 HashMap에 저장하는 .. 2024. 7. 11.
[프로그래머스] 완주하지 못한 선수 (자바) 프로그래머스 고득점 Kit: 해시 - 완주하지 못한 선수문제 설명"완주하지 못한 선수" 문제는 주어진 참가자 명단과 완주자 명단을 비교하여 완주하지 못한 선수를 찾는 문제입니다. 모든 선수들은 한 번만 참가하거나 완주합니다. 단, 완주하지 못한 선수는 단 한 명만 존재합니다.문제 접근 방법HashMap 사용: 각 선수의 이름을 키(key)로 하고, 해당 선수의 참가 횟수를 값(value)으로 하는 HashMap을 사용합니다.참가자 처리: 참가자 명단에서 각 선수의 이름을 키로 하여 참가 횟수를 카운트합니다.완주자 처리: 완주자 명단에서 각 선수의 이름을 키로 하여 참가 횟수를 감소시킵니다.완주하지 못한 선수 찾기: HashMap에서 값이 0이 아닌 선수를 찾습니다.시간 복잡도 분석참가자와 완주자 명단의 .. 2024. 7. 9.
[프로그래머스] 베스트앨범 해시 (자바) 프로그래머스 고득점 Kit: 해시 - 베스트 앨범문제 설명"베스트 앨범" 문제는 주어진 노래의 장르와 각 노래의 재생 횟수를 바탕으로 베스트 앨범을 만드는 문제입니다. 베스트 앨범은 다음과 같은 규칙에 따라 구성됩니다:속한 노래가 많이 재생된 장르를 먼저 수록합니다.장르 내에서 많이 재생된 노래를 먼저 수록합니다.장르 내에서 재생 횟수가 같은 노래 중에서는 고유 번호가 낮은 노래를 먼저 수록합니다.문제 접근 방법장르별 총 재생 횟수 계산: 각 장르의 총 재생 횟수를 계산하여 장르별 순위를 결정합니다.장르 내 노래 정렬: 각 장르 내의 노래들을 재생 횟수와 고유 번호를 기준으로 정렬합니다.베스트 앨범 구성: 위의 정렬된 리스트를 바탕으로 장르별로 두 곡씩 베스트 앨범에 수록합니다.시간 복잡도 분석O(N l.. 2024. 7. 8.
[프로그래머스] 게임 맵 최단거리(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.
반응형