문제 확인 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 나의 풀이 모든 경우의 수를 완전 탐색할 경우, 대략 $4^{100,000}$ 정도의 연산이 필요해 시간 초과가 발생한다. 따라서 다른 방법을 활용해야하고, 나는 DP를 활용했다. 매번 새로운 열만 밟을 수 있기 때문에, 현재 K 번째 열을 밟았다면, 이전엔 [K - 1, K - 2, K - 3]의 열만 밟을 수 있다. 결국 N 행의 K 번째 열을 밟았을 때의, 최대 값을 DP 테이블에 저장하면 문제를 풀 수 있다. DP[n][k] = land[n][k] + max(DP[n - 1][k - 1] +..

문제 확인 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 나의 풀이 스킬 트리만 만족하면 되기 때문에, 관련 없는 다른 스킬들은 확인하지 않아도 된다. 스킬 트리에 포함되는 스킬만 추출해서, 스킬을 찍은 순서를 확인하고 이것이 스킬 트리와 동일한 지 확인하면 된다. # 선행 스킬? 어떤 스킬을 배우기 전에 먼저 배워야 하는 스킬 # 중복이 없으니까, 필요없는 문자열 제거하면 될듯! import re def solution(skill, skill_trees): # 가능한 스킬 트리 개수 cnt = 0 # 확인할 스킬 정보 : 스킬 트리만 만족하면 되기 때문..

문제 확인 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 나의 풀이 10일 동안의 할인 품목이, 원하는 품목과 동일할 경우에만 멤버십에 가입한다. 할인 품목의 개수 정보를 얻기 위해서 Counter를 사용했다. # 10일 동안 회원 자격 # 회원 : 하루 1 개만 # 10일 연속 일치할 경우에 가입 ! from collections import Counter def solution(want, number, discount): best_day = 0 want_number = dict(zip(want, number)) # 언제 가입하면 좋을 지 확인 for ..

문제 확인 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 나의 풀이 마지막에 설정한 이름에 따라 기존 메시지는 전부 바뀌게 된다. 반복문을 통해 uid와 마지막 이름 사이 Hash를 구성하고, 이후 f-string을 통해서 출력했다. $2 * O(N)$ 정도의 시간 복잡도를 가지기 때문에, 시간 초과 없이 처리할 수 있다. # 입장 : 닉네임이 들어옴 -> 퇴장 : 닉네임님이 나감 # 닉네임 변경 방법 : 채팅방 나간 후, 새로운 닉네임으로 다시 들어감 / 채팅방에서 닉네임 변경 # 변경 -> 기존 출력 메시지 닉넴도 변경 # 유저 구분 -> uid 활용..

문제 확인 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 나의 풀이 들어온 차는 나가지 않으면 23 : 59에 나간 것으로 가정한다. 이 경우 들어오고, 나간 시간의 차이를 구하는 것은 23:59 분과 현재 시각 사이 차를 구하는 것과 동일해진다. OUT과 IN을 서로 다른 기호를 가지도록 더해주면 결국 주차장에 머무른 총 시간을 구할 수 있다. # 차량별 주차 요금 계산 # 00:00 ~ 23:59 까지 누적으로 처리 -> 요금 일괄 정산 # 다음날 출차는 고려 X # 요금 계산 시 '올림' 처리 # 차량 번호가 작은 자동차부터, 차례대로 return!..

문제 확인 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 나의 풀이 숫자들을 미리 N 진법으로 변환한 뒤, 대답 여부는 1 글자 씩 읽어서 확인했다. 튜브가 대답할 순서는 나머지를 통해서 확인했다. # 10 이상 부터는, 한 자리씩 말하기! # 자신이 말해야할 번호만 출력하면 됨 # n 진법으로 변환하기 def get_nbase(n: int, i: int) -> str: nbase = "" over_10 = {10 : "A", 11 : "B", 12 : "C", 13 : "D", 14 : "E", 15 : "F"} while i: q, r = divmod..

문제 확인 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 나의 풀이 가장 덜 매운 두 음식을 고르기 위한 방법으로 우선, 정렬을 생각해볼 수 있다. 하지만 K는 10억이라 정렬의 횟수가 많아지기 때문에 시간 초과가 발생할 것이다. 따라서 항상 최소값을 보장할 수 있는, 최소 힙 자료구조를 활용한다. 최소 힙을 이용할 경우, 각 push와 pop은 $\log N$의 시간 복잡도를 가지게 된다. # K가 10억 -> 반복 횟수가 매우 큼 # 100 만의 길이를 계속 정렬한다면 시간 초과가 발생! from heapq import heappush, heappop..

문제 확인 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 나의 풀이 던전의 최대 개수는 8개로, 각 던전 방문의 경우의 수는 8! = 40320이기 때문에 완전 탐색만으로도 풀 수 있다. 가능한 던전 방문의 순서를 얻기 위해서, 순열을 활용했다. # 던전 입장 조건 : 피로도 >= 최소 피로도, 던전 입장 후 : 피로도 -= 소모 피로도 # 최소 피로도 >= 소모 피로도 # 최대한 많이 탐험 -> 각 던전은 한번만 가능 # 가능한 경우의 수 : 8! : 40320 -> 완전 탐색으로도 풀 수 있음 from itertools import permutatio..

문제 확인 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 나의 풀이 알파벳을 하나씩 더해서 새로운 단어를 만들고, 만약 그 단어가 사전에 없는 경우 저장한다. 이 경우 저장된 단어의 바로 이전 단어가 현재 사전에 중 가장 긴 단어이다. 마지막 단어가 사전에 있는 경우 체크가 되지 않기 때문에, 이를 방지하기 위해서 조건문을 추가했다. # 길이가 1인 모든 단어를 포함 하도록 사전 초기화 -> 알파벳 입력 # 현재 입력과 일치하는 가장 긴 문자열 w 찾기 -> 한 글자씩 더해가면서 있는지 확인 -> 만약 없다면, 새로 등록해야함! # w에 해당하는 색인 번..

문제 확인 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 나의 풀이 정규 표현식을 활용한 풀이 1 : 에라토스테네스의 체 활용 → 시간 초과 작은 진법으로 변환 시, 에라토스테네스의 체로 저장 가능한 범위를 넘기 때문에 테스트 케이스 1을 통과할 수 없다. 100만을 2진수로 표현하면, 21개의 숫자가 필요한데, 그 이전에 분명 11111111111111...과 같은 숫자가 여러 번 나올 것 다양한 패턴을 한번에 확인하기 위해서, 정규 표현식의 Group을 활용했다. # 소수 판별 def get_prime(c): is_prime = [True] * (c ..

문제 확인 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 나의 풀이 성분의 개수($n$)을 늘려가며 부분 수열을 구성하면 되는 문제다. 끝점의 index가 범위를 초과할 경우를 처리해주는 것이 중요하다. 범위 초과 시 위 그림과 같이 표현할 수 있기 때문에 각 수열을 나눠서 합했다. def solution(elements): sum_unique = set() # 성분 개수 for n in range(len(elements)): # 시작점 for i in range(len(elements)): # 배열의 길이 초과할 경우 if n + i > len(elem..

문제 확인 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 나의 풀이 처음 풀이 : 시간 초과 발생 접두어의 길이는 '최대 단어 길이 -1' 까지만 가능하다. 길이에 따라서 접두어 후보를 나누고, 이후 비교하는 방식으로 접근하려고 했다. 후보를 나누고, 비교하는 과정이 대략 $O(20 * (50000)^2)$이 되기 때문에 시간 초과가 발생했다. # 접두어 여부 확인 # 접두어? (최대 단어 길이 -1) 까지만 접두어가 될 수 있음 # 접두어 탐색 범위 : 나보다 길이가 더 긴 단어들만 확인 가능 # 길이에 따라서, 접두어 후보를 나누고, 이후 비교하면? ..