본문 바로가기
반응형

프로그래머스14

[프로그래머스] 쌍둥이 빌딩 숲 https://school.programmers.co.kr/learn/courses/30/lessons/140105?language=python3# 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 해설 나머지 연산이 있는걸 보니 전형적인 dp 문제이다. (n,c) 를 (n-1,c-1) 과 (n-1,c)로 나누어 생각한다. 새로들어온 n이 두개가 다 가장 뒤로 배치된다고 하자. n은 어차피 가장 크므로 나머지 경우의수는 solution(n-1, c-1)이 될 것이다. 만약 n의 건물 사이에 아래처럼 다른건물이 들어오거나 앞서있다면? (n, n-1)의 이 한쌍.. 2022. 12. 10.
[프로그래머스][완전탐색] 카펫 https://school.programmers.co.kr/learn/courses/30/lessons/42842 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 해설 brown+yellow = w*h yellow = (w-2)*(h-2) 위 방정식을 풀면 w, h를 구할 수 있다. 허나 이렇게 풀면 완전 수학문제다 나는 완전탐색 느낌이 나도록 문제룰 풀어보았다. total 셀의 개수는 brown + yellow 이다. yellow = (w-2)*(h-2) 이다. h를 3부터 시작해서 차례로 오름차순으로 증가해 나간다 total이 h로 나눠지는지 확인한다... 2021. 4. 15.
[프로그래머스][완전탐색] 소수 찾기 programmers.co.kr/learn/courses/30/lessons/42839 코딩테스트 연습 - 소수 찾기 한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다. 각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 programmers.co.kr 해설 내가 본래 c++이 주 언어여서 그런지 완전 c++ 스타일로 풀었다. 문제 해결은 간단하다 permutation로직으로 모든 케이스를 생성하고 해당 케이스가 소수인지 아닌지 판별한다 여기서 permutation은 파이썬 내장 함수를 사용해도 되지만 기본적으로 어떻게 하는지 적어보면 for i in range(len(numbers)): if visit[i]:.. 2021. 4. 15.
[프로그래머스][동적계획법] 등굣길 programmers.co.kr/learn/courses/30/lessons/42898?language=python3 코딩테스트 연습 - 등굣길 계속되는 폭우로 일부 지역이 물에 잠겼습니다. 물에 잠기지 않은 지역을 통해 학교를 가려고 합니다. 집에서 학교까지 가는 길은 m x n 크기의 격자모양으로 나타낼 수 있습니다. 아래 그림은 m = programmers.co.kr 문재해결 방법 dp[0][0] = 1로 둔다 한 지점에서 위쪽과 왼쪽의 dp값을 더한다. set을 이용해서 웅덩이는 무시한다. 문제에서 1,000,000,007 로 나눠주라는거 주의하자 def solution(m, n, puddles): answer = 0 dp = [[0 for _ in range(m)] for _ in range(n.. 2021. 4. 13.
[프로그래머스][동적계획법] 정수 삼각형 programmers.co.kr/learn/courses/30/lessons/43105 코딩테스트 연습 - 정수 삼각형 [[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]] 30 programmers.co.kr 간단한 dp문제. 숫자 하나 기준으로 윗줄의 left right 숫자를 더하며 가장 큰것을 선택해 나가면 된다. 다른사람 풀이보니 한줄에 풀었던데 그런건 어케하는건지.. def solution(triangle): answer = 0 length = len(triangle) dp = [ [0] * i for i in range(1, length + 1)] dp[0][0] = triangle[0][0] for i in range(1, length): fo.. 2021. 4. 13.
[프로그래머스][탐욕법] 큰 수 만들기 programmers.co.kr/learn/courses/30/lessons/42883 코딩테스트 연습 - 큰 수 만들기 programmers.co.kr 그리디 + 스택문제이다. 문제해결 아이디어 : 앞자리에서부터 세어나가며 내림차순이 되도록 만든다 숫자를 스택에 하나씩 쌓아 올려가되 내림차순으로 만든다. 즉 스택을 쌓다가 스택 가장 윗자리 숫자보다 큰 숫자가 나오면 스택을 내림차순이 될 때 까지 pop 해준다. k개를 pop해주었으면 나머지 숫자는 그대로 내비둔다. pop한 갯수가 k보다 부족하면 부족한 수 만큼 뒤에서 덜어준다.(내림차순이므로 뒤에 숫자를 빼는게 유리) def solution(number, k): answer = '' q = [] popcnt = 0 for num in number: .. 2021. 4. 2.
[프로그래머스][탐욕법(그리디)] 체육복 programmers.co.kr/learn/courses/30/lessons/42862 코딩테스트 연습 - 체육복 점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번 programmers.co.kr 해설 각 학생이 가지고 있는 체육복의 수를 dictionary를 이용하여 만든다 각 요소를 오른쪽 방향으로 순회한다. 체육복을 한개 이상 들고 있을시 왼쪽 학생먼저 체육복이 없을경우 빌려주고 그다음으로 오른쪽 학생을 체크 한다. def solution(n, lost, reserve): answer = n mydict = {} for i in range(1,n+1): mydict.. 2021. 4. 1.
[프로그래머스][힙] 디스크 컨트롤러 programmers.co.kr/learn/courses/30/lessons/42627 코딩테스트 연습 - 디스크 컨트롤러 하드디스크는 한 번에 하나의 작업만 수행할 수 있습니다. 디스크 컨트롤러를 구현하는 방법은 여러 가지가 있습니다. 가장 일반적인 방법은 요청이 들어온 순서대로 처리하는 것입니다. 예를 programmers.co.kr 해설 대기하는 작업들중 수행시간이 가장 작은작업을 먼저 처리해야 한다. 현재 작업중인 작업이 [0, 3] 라고 하자 대기 작업 [1, 9], [2, 6] 이 있다고 하자 저기서 대기작업들의 걸리는 시간을 생각해보면 간단하다. 만약 대기작업이 2개가 있다고 치자. 각각 걸리는 작업의 시간은 앞에오는놈 : (현재 작업중인 작업의 종료시간 - 앞에오는놈의 시작시간) + 앞에오.. 2021. 3. 31.
[프로그래머스][힙(heap)] 더 맵게 programmers.co.kr/learn/courses/30/lessons/42626 코딩테스트 연습 - 더 맵게 매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같 programmers.co.kr 해설 시키는대로 heap을 이용해 풀면 된다. 한번 스코빌 지수를 계산할때마다 전체 원소의 수가 하나씩 줄어드는데 이때 heap의 사이즈가 0이 되면 바로 return -1을 해주면 된다. import heapq def solution(scoville, K): answer = 0 q = [] for i in scoville: heapq.heappush(q,i) w.. 2021. 3. 25.
[프로그래머스][정렬] H-Index 해설 문제를 보면 x번 -> 세로축 x편 -> 가로축 이라고 생각 할 수 있다. 풀이방법 내림차순으로 정렬한다 가로세로가 h인 정사각형을 떠올리고 정사각형의 한 변의 길이가 가장 최대일때를 계산한다. def solution(citations): citations.sort(reverse=True) length = len(citations) answer = 0 for i in range(length): if citations[i] < i+1: break else: answer = i+1 return answer 다른사람 풀이를 보니 아래와 같이 개쩌는 풀이를 발견했다. 아이디어는 똑같은데 enumerate를 이용한게 참으로 멋있구만. def solution(citations): citations.sort(r.. 2021. 3. 25.
[프로그래머스][정렬] 가장 큰 수 programmers.co.kr/learn/courses/30/lessons/42746 코딩테스트 연습 - 가장 큰 수 0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요. 예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 programmers.co.kr 아이디어 문자열 A+B, 로 만든 숫자와 B+A로 만든 숫자를 비교하여 어느게 더 큰수인지 확인하고 정렬한다 파이썬 문자열 비교를 이용하면 사전순으로 정렬해주는데 이걸 수 비교수단으로 이용할 수 있다 답이 0일 경우에는 0만 리턴해준다.(마지막 테스트 케이스) from functools import cmp_to_.. 2021. 3. 24.
[프로그래머스][해시] 위장 programmers.co.kr/learn/courses/30/lessons/42578 코딩테스트 연습 - 위장 programmers.co.kr 이걸 해시라고 해야하는게 맞는건지... 그냥 순열 문제이다. 모자가 3개, 옷이 5개, 신발이 4개 있다 치자 모자를 고르는 경우의수는 3+1 = 4 (+1은 선택하지 않음을 의미) 옷을 고르는 경우의수는 5+1 = 6 신발을 고르는 경우의수는 4+1 = 5 문제에서 아예 안고르는 경우의 수는 빼라 했으므로 마지막에 -1 해주면 된다. 4 * 6 * 5 - 1 이런식으로 풀면된다. def solution(clothes): answer = 0 mydict = {} for i in clothes: if i[1] in mydict: mydict[i[1]] = mydi.. 2021. 3. 17.
[프로그래머스][해시] 전화번호 목록 programmers.co.kr/learn/courses/30/lessons/42577 코딩테스트 연습 - 전화번호 목록 전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다. 전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다. 구조 programmers.co.kr 문제는 풀었는데 다른사람이 파이썬 내장함수로 한줄로 푸는거 보고 충격... 정리 따로 해야겠다. 아이디어는 이렇다. 전화번호부로 set을 이용해 hash테이블을 만든다. 각번호를 순회하면서 이중포문을 통하여 번호의 부분문자열을 얻은뒤 hash 테이블에 있는지 확인한다. hashtable에 있다면 누군가의 접두어가 된다는 뜻이므로 False를 리턴한다 이렇게 하면 시간복잡도.. 2021. 3. 12.
[프로그래머스][해시] 완주하지 못한 선수 programmers.co.kr/learn/courses/30/lessons/42576 코딩테스트 연습 - 완주하지 못한 선수 수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다. 마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수 programmers.co.kr c++스타일로 풀어봤다. completion 배열을 dictionary로 만들어준다. value값을 기본적으로 1로 주고 동명이인이 있는경우 value에 1을 더해주어 몇명이 있는지 세어준다. 이후 participant를 확인하면서 이름이 존재 할 때 마다 value값을 -1씩 해준다. value가 0이거나 dictionary에 없는경우가 답이므로 해당값 .. 2021. 3. 12.
반응형

티스토리툴바