🧩 문제 🌱 풀이과정 1️⃣ 이중 for문 사용하기 - O(N^2) def solution(prices): answer = [] for i in range(len(prices)): time = 0 for j in range(i+1, len(prices)): if prices[i] right_price: time += 1 break else: time += 1 answer.append(time) return answer 둘다 시간복잡도가 O(N^2)이기는 하지만, 효율성 테스트에서의 시간이 전체적으로 줄어들었다 ..! 이유는 전자의 경우 최악의 경우 n*n번 탐색하지만, 후자는 while문에서 n번, for문에서 n-1 번으로 총 n*(n-1)번 탐색하기 때문인 것 같다. 내 머리로는 이것이 최선일 것 같..
🔫 문제 : 공원 산책 https://school.programmers.co.kr/learn/courses/30/lessons/172928 📍 정리 산책 경로가 주어졌을 때, 공원의 범위와 장애물을 고려해 강아지의 최종 위치를 구하면 된다! - 공원의 범위를 벗어나거나 장애물을 마주치면 해당 명령을 수행하기 전 위치로 돌아가 다음 명령을 수행하면 된다. 🌱 풀이과정 1️⃣ 산책을 시작할 위치 찾기 아래와 같이 문자열 "S"가 있는 x좌표와 y좌표의 위치를 answer에 넣어주었다. for x in range(H): for y in range(W)): if "S" in park[x][y]: answer.append(x) answer.append(y) 2️⃣ 강아지 산책시키기 먼저, 동서남북의 이동을 다음과..
🔫 문제 : 단어 변환 📍 정리 현재 단어와 words에 있는 단어가 알파벳 하나만 다르다면 words에 있는 단어로 변경해주면 된다. - words에 target이 없다면 최종 목표인 target으로 바꿀 수 없으므로 0을 반환한다. 🌱 풀이 방법 어느 경우를 탐색해도 깊이가 같다 -> BFS를 사용하자! 1️⃣ 현재 단어와 변환 횟수를 담을 queue와 방문 여부를 확인할 list를 만들어준다. q = deque() q.append([begin, 0]) visit = [0] * len(words) 2️⃣ words에 target이 존재하는지 확인 if target not in words: return 0 3️⃣ queue에서 현재 단어와 변환 횟수를 꺼낸 후, target과 현재 단어가 같은지 확..
🔫 문제 : 베스트 앨범 📍 정리 장르 리스트와 노래의 재생횟수가 담긴 리스트가 주어질 때, 많이 재생된 장르에서 많이 재생된 노래의 고유번호를 2개씩 반환하면 된다. (노래가 같은 횟수로 많이 재생되었다면 고유번호가 낮은 순으로, 많이 재생된 노래가 하나라면 하나만 수록) 🌱 풀이 방법 1️⃣ 딕셔너리 두개를 만들어준다. total_genres : 장르별 총 재생횟수를 담을 딕셔너리이다. song_plays : 장르별로 각 노래의 [재생횟수, 고유번호] 리스트를 담을 딕셔너리이다. 2️⃣ 정렬하기 total_genres : 장르별 총 재생횟수를 기준으로 정렬 total_genres = dict(sorted(total_genres.items(), key=lambda x: x[1], reverse=True..
🧩 문제 : 타겟넘버 💡 정리 numbers에 주어진 수를 더하고 빼서 target을 만든다. target을 만드는 방법의 수를 return 한다. 💪🏻 풀이 과정 🌱 아이디어 재귀함수로 구현한 dfs로 numbers의 수를 모두 더하고 뺀다. 재귀함수가 무한루프에 빠지지 않기 위해서 종료 조건이 필요하다. 종료 조건은 numbers의 크기가 index와 같을 때 이다. 즉 모든 원소를 탐색한 경우이다. 모든 원소를 탐색하였는데, sum이 target과 같다면 1을 return 해 target 넘버를 만드는 방법의 수를 구한다. 재귀함수안에서는 numbers의 다음원소를 더하는 경우와, 빼는 경우를 나누어 재귀적으로 호출한다. 더하고 빼가며 합을 저장할 sum변수와 numbers의 인덱스를 나타내는 in..
🧩 문제 : 듣보잡 💡 정리 N개의 듣도 못한 사람의 이름, M개의 보도 못한 사람의 이름이 주어질 때, 듣도 보도 못한 사람들을 구하면 된다. 이 때 듣도 못한 사람과 보도 못한 사람의 명단에는 중복되는 이름이 없다 ! 💪🏻 풀이 과정 🌱 아이디어 1️⃣ map을 이용해 중복을 찾고, 중복된 이름은 vector에 넣어서 오름차순 정렬했다. 💻 코드 #include #include #include #include #include using namespace std; int main(){ int n, m; map list; vector answer; cin >> n >> m; for(int i = 0; i > name; list[name]++; if(..
