문제 확인 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 나의 풀이 귤 k개를 종류를 최소화하면서 구하려면, 많은 개수를 가진 종류부터 차례로 선택하면 된다. 개수를 세기 위해서 Counter를 활용했다. # 귤 k 개 -> 서로 다른 종류 최소화! # Counter 사용 후, 개수 기준 내림차순 정렬 from collections import Counter def solution(k, tangerine): # 귤 종류 수 tan_uniq = 0 # 종류 별 개수 세기 type_cnt = Counter(tangerine) type_cnt = sorted(..

문제 확인 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 나의 풀이 처음 풀 때는 문제 조건을 제대로 확인하지 않아, 특수 문자 / 공백을 제거해서 풀었다. 이 경우 aa1+aa2와 AAAA12가 동일해지는 문제가 생긴다. 특수 문자 / 공백을 미리 제거 하면 문제가 생기기 때문에, 알파벳 여부를 원소를 만들 때 확인했다. # 자카드 유사도 : (두 집합의 교집합 크기 / 두 집합의 합집합 크기 # 중복 문자에 대해서도 처리 가능 # 둘다 공집합인 경우 -> 1로 정의 from collections import Counter def solution(str..

문제 확인 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 나의 풀이 $N = 10^7$이기 때문에 2 차원 배열을 선언하고, 각 성분에 값을 할당할 경우 시간 초과가 발생한다. 따라서 별도의 규칙을 찾아서 문제를 풀려고 했는데, 고민해도 생각이 안나서 다른 사람의 풀이를 참고해서 풀었다. 2 차원 행렬을 1 차원으로 펼칠 경우, 각 성분은 n으로 나눈 몫과 나머지로 표현할 수 있다. # n이 크기 때문에, n**2만 해도 시간 초과 발생! # 규칙을 찾아야 함 # 1 2 3 2 2 3 3 3 3 # (0,0) (0,1) (0,2) (1, 0) (1, 1)..

문제 확인 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 나의 풀이 튜플은 원소의 순서를 고려해야 하기 때문에, 낮은 길이의 튜플부터 확인하면, 입력 순서를 확인할 수 있다. 각 성분으로 구성된 튜플을 얻기 위해서, 정규 표현식을 활용 했다. 숫자가 1번 이상 나오고, 이후 "," 와 숫자가 올 수도, 안 올수도 있도록 정규 표현식을 구성 했다. # 원소의 개수가 n, 중복되는 원소가 없는 튜플 # 튜플은 원소의 순서를 고려해야 함 -> 집합의 개수가 늘어날 수록 1 개 씩 추가 됨 # 이를 통해 튜플 원소의 순서를 알 수 있다! import re def..

문제 확인 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 나의 풀이 한 부위의 옷은 입거나, 안 입은 경우 2 가지만 존재한다. 입을 경우, 현재 부위에 속하는 옷 개수 만큼의 경우가 가능하고, 입지 않는 경우는 1 가지만 있다. 따라서 (현재 부위 옷의 개수 + 1)을 통해서, 모든 위장 경우의 수를 표현할 수 있다. 최소 1 개의 의상은 입어야 하기 때문에, 마지막에 1을 빼주면 전체 경우의 수를 얻을 수 있다. # n, m, k, l # nC1, mC1, kC1, lC1 -> n, m, k에 대한 선택 # 종류가 많은 경우 -> 시간 초과가 발생할 ..

문제 확인 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 나의 풀이 행렬의 곱을 얻기 위해선 arr1의 행과 arr2 열 사이의 연산이 필요하다. arr2의 열 성분을 얻기 위해서 zip(*arr2)를 활용했다. *arr2를 통해 unpacking을 하면 각 행 별 리스트([] [] [])를 얻을 수 있고, zip을 사용하면 리스트의 n 번째 항 끼리 묶을 수 있다. 각 행의 n 번째 항 끼리 묶은 것은 결국 행렬의 열과 동일하다. # (a x b) * (b x a) = (a x a) # 행 - 열 성분 사이 곱 def solution(arr1, arr2..

문제 확인 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 나의 풀이 괄호 회전을 쉽게 하기 위해서 deque.rotate를 활용했다. 올바른 괄호 쌍인지 확인하기 위해서 stack을 활용했다. # 괄호 회전 -> deque.rotate로 구현 # 올바른 괄호 여부 확인 : stack으로! from collections import deque def solution(s): # 올바른 괄호 문자열의 수 answer = 0 # 올바른 괄호 쌍 match = {"[" : "]", "(" : ")", "{" : "}"} # i 만큼 회전 for i in range..

문제 확인 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 나의 풀이 LRU : 가장 오랫 동안 참고되지 않은 캐시부터 제거하는 알고리즘 LRU를 사용하려면 사용 순 → 입력 순으로 정렬하는 캐시가 필요하다. # LRU : 최근에 사용되지 않은 캐시부터 교체 # 사용 순 -> 입력 순으로 정렬 필요 from collections import deque def solution(cacheSize, cities): # 실행 시간 answer = 0 cache = deque() for city in cities: # 대소문자 구분 X city = city.lowe..

문제 확인 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 나의 풀이 항상 1칸 또는 2칸만 뛸 수 있기 때문에, 가능한 모든 방법의 수는 $a[n] = a[n - 1] + a[n - 2]$로 표현할 수 있다. 현재 칸에 도달 = 1 칸 전에서 뛴 경우 + 2 칸 전에서 뛴 경우 # 가능한 모든 방법의 수 # a1 = 1 # an = a(n - 1) + a(n - 2) def solution(n): answer = [i for i in range(n + 1)] for i in range(3, n + 1): answer[i] = answer[i - 1] + ..

문제 확인 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 나의 풀이 나머지를 활용한 풀이 비용을 줄이려면 가능하면 항상 순간 이동을 해야 한다. $n$ 번째 위치는 $n // 2$에서 순간 이동해서 바로 가거나, 순간 이동 후 1 만큼 점프하여 갈 수 있다. 따라서 매번 2 로 나눴을 때, 나머지가 1인 경우에만 비용을 추가하면 된다. def solution(n): answer = 0 while n: q,r = divmod(n, 2) # 점프가 필요할 때 비용 추가 if r == 1: answer += 1 n = q return answer DP를 활용한..

문제 확인 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 나의 풀이 전체 대진표는 대결하는 두 쌍($0, 1$)과 순서로 표현할 수 있다. 순서는 숫자를 2 로 나눴을 때 몫으로 표현할 수 있기 때문에, $a$와 $b$가 몫이 같을 때 까지 라운드를 반복하면 된다. # 0 1 2 3 4 5 6 7 # 0 1 2 3 # 0 1 def solution(n,a,b): # 1 라운드부터 시작하기 때문에 answer = 1 # 몫 정보로 대결 여부 파악할 수 있도록 변경 # 몫이 같다면 둘이 매칭된 것 a, b = a - 1, b - 1 while a // 2 !..

문제 확인 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 나의 풀이 N개 수의 최소 공배수를 구하기 위해선, 두 정수 사이 최소 공배수를 구한 다음, 그 최소 공배수와 다음 정수 사이 최소 공배수를 구하면 된다. 기존 최소 공배수가 다른 정수에도 적용 되기 위해선, (최소 공배수 * 상수 배) 형식이어야 하기 때문에 각각 최소 공배수를 구하는 과정에서 최악의 경우, 대략 $(100^2)**14$ 정도의 시간 복잡도가 발생하기 때문에, 유클리드 호제법을 활용해 최소 공배수를 찾았다. 유클리드 호제법을 활용한 최소 공배수, 최대 공약수 구하는 방법은 포스팅에..