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

문제 확인 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 나의 풀이 한 번에 최대 2명을 태울 수 있기 때문에, 최적의 구성은 무거운 사람 + 가벼운 사람을 태울 경우다. 무거운 사람, 가벼운 사람의 무게 합이 제한 무게를 넘는지 확인하기 위해서, 무게 순으로 people을 정렬 했다. 정렬 뒤엔 시작 점과 끝 점을 비교하기 위해서 투 포인터를 활용했다. # 한 번에 최대 2명 # 최적 -> 무거운 사람 + 가벼운 사람 def solution(people, limit): people.sort() answer = 0 # 투포인터 시작 - 끝 점 start,..

모든 사진과 내용은 강의를 참고 했습니다. 투포인터 2 가지 점(시작, 끝점)의 위치를 기록해서, 순차 접근을 빠르게 할 수 있도록 도와주는 알고리즘이다. 투포인터를 사용하면 기존 $O(N^2)$에서 $O(N)$로 시간 복잡도를 줄일 수 있다는 장점이 있다. 매 시행 마다 투 포인터의 시작, 끝 점은 1개 씩 움직이고, 각 점이 마지막 성분에 도달하면 끝나게 되기 때문에 $O(N)$ 임 활용 1 : 부분 합 구하기 투포인터는 수열의 부분 합을 구하는데 활용될 수 있고, 수열의 모든 수가 양수인 경우에만 가능하다. 모든 수가 양수여야 시작점을 오른쪽으로 옮길 때, 합을 구성하는 성분 수가 줄어 합이 줄어 들고, 끝점을 오른쪽으로 옮겨 부분 합을 구성하는 성분 수가 늘어 합이 늘기 때문이다. 투포인터를 활용..

문제 확인 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 나의 풀이 노란 박스의 가로, 세로 정보에 따라서 갈색 박스의 정보가 결정 된다. 노란 박스의 가로, 세로는 박스 수의 약수이고, 가로는 그 중에서 큰 값이다. 따라서 노란 박스의 약수를 큰 수 부터 역으로 완전 탐색하면 문제를 풀 수 있다. 탐색 범위에 대해선, 가로의 길이가 세로 길이 보다 크거나 같기 때문에 제곱근 범위 까지만 찾으면 된다. # 노란 박스 정보 : 가로 x 세로 # brown = ((가로 + 2) * 2 + 세로 * 2) def solution(brown, yellow): an..

문제 확인 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 나의 풀이 중복 여부를 확인하기 위해서 set()을 사용했고, 그에 따라 마지막 단어를 확인하는 변수도 활용했다. words의 길이가 50 정도로 작은 편이기 때문에, 리스트를 사용해서 마지막 단어, 중복 여부 확인을 동시에 하는 것이 더 좋았을 거 같다. # 정답 : (먼저 탈락하는 사람의 번호, 몇 번째 차례에 탈락) def solution(n, words): answer = [0, 0] # 중복 단어 체크 word_set = set() last_word = "" # 끝말잇기 시작 for idx..

문제 확인 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 나의 풀이 완전 탐색을 활용해서 풀었다. 이 경우 시간 복잡도는 $N$ * $((\log C + C)) \times C$이다. $C$가 대략 $\log_{2}{10^6} = 20$ 정도라서 시간 초과가 발생하진 않는다. # 다음 큰 숫자 : 'n보다 크고, 2 진수 표현에서 1의 갯수가 같은 수' 중에서 가장 작은 숫자 # 시간 복잡도 : n * ((logc + c) * c) def solution(n): n_cnt = bin(n)[2:].count("1") check = n + 1 while Tr..

문제 확인 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 나의 풀이 i, j를 각각 연속된 수의 시작과 끝으로 생각하면, 각 i 마다의 j를 찾으면 문제를 풀 수 있다. 합을 구하는 과정에서 동일한 연산이 계속 반복되기 때문에, 누적합을 미리 계산했다. def solution(n): answer = 0 # 누적합 cum_sum = [] for i in range(10001): cum_sum.append((i * (i + 1) // 2)) # 확인 for i in range(10001): for j in range(i + 1, 10001): if cum_s..

문제 확인 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 나의 풀이 문제 조건에 띄어쓰기가 여러 개 있을 수 있다고 나와서, 그냥 문자 단위로 확인했다. upper, lower 함수는 숫자가 섞여 있더라도, 문자에만 영향을 준다 def solution(s): answer = "" word = "" for char in s: if char == " ": answer += (word + " ") word = "" else: if not word: word += char.upper() else: word += char.lower() # 마지막 부분 answer..

문제 확인 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 나의 풀이 날짜 정보를 간단하게 처리하기 위해서 '일' 단위로 변경하여 문제를 풀었다. 2 중 리스트를 zip하기 위해서 *를 사용했다. def cnt_day(day: str) -> int: # 날짜 정보를 '일' 단위로 변경하는 함수 day = day.split(".") day = int(day[0]) * 12 * 28 + int(day[1]) * 28 + int(day[2]) return day def solution(today, terms, privacies): answer = [] # 비교하..

문제 확인 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 나의 풀이 처음엔 str.replace(, , 1)를 활용해서 풀려고 했다. 이 경우 $O(N^2)$의 시간 복잡도를 가지기 때문에 시간 초과가 발생한다. def solution(ingredient): answer = 0 food = list(map(str, ingredient)) food = "".join(food) while food: # 한번에 1개의 문자열만 교체할 수 있도록 1을 설정 했다. temp = food.replace("1231", "", 1) if food == temp: bre..

문제 확인 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 나의 풀이 분리 전 문자열을 word 변수를 활용해서 관리했다. def solution(s): answer = 0 word = "" # 개수 세기 x_cnt, y_cnt = 0, 0 for char in s: # 새로운 단어 생성 if not word: word += char x_cnt += 1 continue # 글자 확인 if char == word[0]: x_cnt += 1 elif char != word[0]: y_cnt += 1 # 문자열 분리 if x_cnt == y_cnt: answer..

문제 확인 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 나의 풀이 문자열을 완전 탐색해 정해진 패턴을 찾는 방식으로 문제를 풀었다. 이전 패턴과 겹치는지 여부를 확인하기 위해서 idx를 활용했다. def solution(babbling): answer = 0 for bab in babbling: # 비교할 문자열 temp_c = "" # 이전에 나온 단어 확인 prev_idx = -1 for c in bab: temp_c +=c # 못 찾은 경우 중단 if len(temp_c) > 4: break # 체크 시작 for idx, word in enumer..