코딩테스트

문제 소요 시간 : 30분난이도 : LV 2나의 풀이1차접근 방법1. 무게당 가격이 높은 순서대로 정렬한다.2. 가방 무게에서 가격이 높은 순서대로 차례차례 그리디하게 금속을 가져간다. 시간복잡도O(N)코드import java.io.*;import java.util.*;public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int w = sc.nextInt(); int n = sc.nextInt(); int [][] list = new int[n][2]; for(int i=0; i o2[1]-o1[1]); ..

문제https://school.programmers.co.kr/learn/courses/30/lessons/154539?language=java 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 소요 시간 : 40분난이도 : LV 2나의 풀이 접근 방법https://ggungdi-dev.tistory.com/entry/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EB%92%A4%EC%97%90-%EC%9E%88%EB%8A%94-%ED%81%B0-%EC%88%98-%EC%B0%BE%EA%B8%B0-Python [프로그래머스] 뒤에 있는 큰 수 찾기 - ..

문제https://school.programmers.co.kr/learn/courses/30/lessons/132265# 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr소요 시간 : 30분난이도 : LV 2나의 풀이1차 시도접근 방법1. 완전탐색으로 모든 인덱스일 때 2개로 슬라이싱한다.2. set으로 토핑의 종류 개수를 세서 비교한다.  시간복잡도O(N^2)Python list slicing : O(N)https://school.programmers.co.kr/questions/42508 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그..

문제https://school.programmers.co.kr/learn/courses/30/lessons/161988# 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr소요 시간 : 30분난이도 : LV 3나의 풀이 접근 방법1. [기존 배열 * 1로 시작하는 펄스배열] , [기존 배열 * -1로 시작하는 펄스배열] 2가지 배열을 만든다.2. 각 2가지 배열의 누적합 배열을 만든다.3. 누적합 배열에서 가장 큰 값 - (가장 큰 값 이전에 나온 가장 작은값) 이 정답이다. 시간복잡도O(N)코드def find_max_sum(arr): max_value = ..

문제https://school.programmers.co.kr/learn/courses/30/lessons/154538# 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 소요 시간 : 1시간난이도 : LV 2나의 풀이1차 시도접근 방법재귀를 이용하여 모든 경우의 수를 탐색한다. y에서 x를 만들기 위해 n을 빼고, 3으로 나누고, 2로 나눈다. 시간복잡도매번 3가지 연산이 가능하므로, 최악의 경우에는 모든 경로를 탐색하게 될 수 있다. 최악의 경우 시간 복잡도는 O(3^d)가 될 수 있다. 여기서 d는 y에서 x로 도달하기 위한 최대 깊이이다.코드def sol..

문제https://school.programmers.co.kr/learn/courses/30/lessons/92343 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr소요 시간 : 1시간난이도 : LV 2 나의 풀이접근 방법1. 노드별로 루트까지 가면서 들러야 하는 늑대의 개수를 체크한다.2. 개수가 적은대로 방문한다. 시간복잡도for : O(N)  *  go_to_root : O(N) = O(N^2)코드 def solution(info, edges): answer = 0 childs = [[] for i in range(len(info)..

문제https://school.programmers.co.kr/learn/courses/30/lessons/154540 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr소요 시간 : 30분난이도 : LV 2나의 풀이 접근 방법BFS의 정석과도 같은 문제맵을 전체적으로 돌면서 숫자이고 방문하지 않았다면 BFS를 사용해 이어진 영역의 합을 구한다.  시간복잡도 이중 for 루프에서 모든 셀을 탐색하고, BFS로 연결된 모든 셀을 한 번씩만 방문하므로,전체 시간 복잡도는 O(n * m)이다. (n  코드from collections import dequedef sol..

문제https://school.programmers.co.kr/learn/courses/30/lessons/150365 소요 시간 : 2시간난이도 : LV 3나의 풀이 접근 방법1. S에서 E까지의 최단 경로를 사전순으로 제일 빨리 탐색한다.d > l > r > u 가 사전순이기 때문에 아래, 왼쪽, 오른쪽, 위 순으로 BFS를 돌려 최단거리를 찾는다.2. S에서 E까지의 최단 거리와 k의 차이를 이용해 추가적인 처리를 한다.k == S에서 E까지의 최단 거리 : 별도로 추가하지 않고 경로를 반환한다.k > S에서 E까지의 최단 거리차이가 홀수일 경우 : 경로에 영향을 주지 않고 추가로 움직이려면 [아래위, 왼오, 오왼, 위아래] 이렇게 2번씩 움직여야하는데, 홀수일 경우 불가능하므로 impossible..

문제https://school.programmers.co.kr/learn/courses/30/lessons/154539 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 소요 시간 : 30분난이도 : LV 2나의 풀이접근 방법현재 위치보다 뒤에 있는 리스트를 돌면서 큰 수가 나오면 멈춘다. 시간복잡도O(N^2)인데, 100만 * 100만이라 무조건 시간초과가 나온다..코드def solution(numbers): answer = [] # 100만 for idx, n in enumerate(numbers): backs = numb..

문제https://school.programmers.co.kr/learn/courses/30/lessons/138476 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 소요 시간 : 15분난이도 : LV 2접근 방법1. 종류별 개수를 센 뒤 많은 순으로 정렬한다.ex. 1, 3, 2, 5, 4, 2, 31: 1개4: 1개2: 2개3: 2개5: 2개=> [2, 2, 2, 1, 1] 2. 종류별 개수 리스트를 돌면서 k만큼 가져간다. ex. k = 62+2+2 => 3번째 원소까지 가져갈 수 있다.ex. k=42+2 => 2번째 원소까지 가져갈 수 있다.풀이나의 ..