알고리즘/프로그래머스 문제풀이 (18) 썸네일형 리스트형 프로그래머스 주식가격 https://school.programmers.co.kr/learn/courses/30/lessons/42584 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제분석 주어진 배열 prices의 길이 제한사항이 >10^5이므로 사용할 수 있는 시간복잡도는 O(n)이나 최소 O(nlogn)에 끝내야한다. 따라서 완전탐색은 불가능(n^2)하고 다른 아이디어를 사용해야한다. 이떄 메모리를 사용해서 시간복잡도를 낮추기위해서 주어진 배열을 스택에 넣고 이를 기본의 배열과 비교하는 방법 선택 def solution(prices): answer = [0] * len.. 프로그래머스 위장(lv2, python) https://school.programmers.co.kr/learn/courses/30/lessons/42578?language=python3 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 접근 스파이가 입을 수 있는 옷의 경우의 수를 모두 구하는 문제 스파이는 한 종류의 옷을 꼭 입어야함 아이디어 각 종류의 옷의 개수 해시를 이용해 저장하고 이를 곱하여 모든 경우의 수를 구함 입지 않는 경우도 생각하기위해 모든 옷의 종류에 +1 아무 옷도 안 입는 경우를 빼주기 위해 -1 정답 코드 def solution(clothes): # 1. 옷을 종류별로.. 프로그래머스 짝지어 제거하기(lv2, python) https://school.programmers.co.kr/learn/courses/30/lessons/12973 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 접근 해당 조건에 의거하여 문자열을 모두 제거할 수 있으면 1 아니면 0을 리턴하는 함수를 구현하는 문제 아이디어 문자열의 길이가 10^6이므로 O(n+@)정도의 시간복잡도로 해결하면 될듯 이중 for문으로 하나하나 완전탐색해줄까 했지만 구현도 복잡하고 시간복잡도상 불가능함 이전의 문자와 다음 문자를 비교한다는 점에서 올바른 괄호 문제와 비슷하다고 판단-> 스택을 활용 문자열을 스택에 넣어서.. 프로그래머스 숫자의 표현(lv2, python) https://school.programmers.co.kr/learn/courses/30/lessons/12924 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 접근 주어진 수 이하의 연속된 자연수의 합으로 주어진 수를 표현할 수 있는 경우의 수를 모두 구하는 문제 아이디어 n이 10,000(10^4)이하 이므로 대충 O(n^2) 이하의 시간복잡도면 풀 수 있겠다 판단함 이중 for문으로 완전탐색해주면 시간복잡도상 애매한데, 정답이 구해지는 경우랑 정답이 나올 수 없는경우 break를 걸어주면 충분히 가능하겠다 싶어서 구현시작 정답 코드 def so.. 프로그래머스 최솟값 만들기(lv2, Python) https://school.programmers.co.kr/learn/courses/30/lessons/12941 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 분석 길이가 같은 두 배열의 원소를 하나씩 뽑아 곱하는 걸 배열 길이만큼 반복해 각각의 결과를 더함 더한 결과값이 최소가 되는 경우를 구하는 문제 아이디어 처음엔 탐색문제라 생각해서 모든 경우를 다 구해서 최솟값을 구하려했음...-> 구현 복잡하고 비효율적 다른 사람 풀이보니 두 배열을 오름차, 내림차순 정렬해서 각 인덱스끼리 곱했음-> 문제 원리 파악해서 구현 정답코드 def solutio.. 프로그래머스 올바른 괄호(lv2, Python) https://school.programmers.co.kr/learn/courses/30/lessons/12909?language=python3 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 접근 괄호가 문자열로 주어졌을 때 해당 괄호가 올바르게 되어있는지 판별하는 함수를 만드는 문제 아이디어 문자열을 하나씩 탐색하는데 여는괄호가 나오면 큐에 저장하고 닫는괄호가 나오면 하나씩 큐에서 제거하는 방식 -> 시간초과 문자열을 하나씩 탐색하는데 여는괄호가 나오면 스택에 저장하고 닫는괄호가 나오면 하나씩 스택에서 제거하는 방식 -> 성공? 큐를 활용한 풀이 .. 프로그래머스 - 소수찾기 (Python) https://school.programmers.co.kr/learn/courses/30/lessons/42839?language=python3 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 접근 한자리 숫자가 적힌 카드들을 조합해서 만들 수 있는 소수의 개수를 구하는 문제 아이디어 주어진 카드로 수를 만들어 set에 저장하기(중복을 피하기 위함) set에 넣기전에 에라토스테네스(소수 판별 알고리즘)의 체를 활용해서 소수만 넣기 완성된 set의 개수 리턴하기 코드 myset = set() def solution(numbers): dfs('',numb.. 프로그래머스 최소 직사각형(lv1, python) https://school.programmers.co.kr/learn/courses/30/lessons/86491 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 분석 주어진 크기의 명함들을 모두 수납할 수 있는 명함지갑의 최소 크기를 구하는 문제 일반적으로 생각하면 명함들의 가로세로 길이의 최대값을 곱해주면 되지만 명함은 회전이 가능하다. 아이디어 어차피 카드를 돌린다면 더 큰 쪽을 가로, 짧은 쪽을 세로라고 생각하였다. 두 리스트( maxW, maxH)를 만들어 주어진 명함들의 가로, 세로 중 큰 값을 maxW에 넣고, 작은 값을 maxH에 넣었다.. 이전 1 2 3 다음
