솧로그

https://school.programmers.co.kr/learn/courses/30/lessons/84021 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 예전에 풀다가 빡구현에 지쳐서 포기한 문제인데 이번엔 풀었다..! 아이디어 자체는 간단하다.bfs를 통해 퍼즐과 빈칸들을 찾는다. 그리고 나중에 빈칸에 퍼즐을 넣을 수 있는지 비교해야 하므로 퍼즐과 빈칸의 위치를 0, 0을 시작으로 하며, 딱 맞는 크기의 배열로 만들어야 한다.그리고 각 빈칸에 각 퍼즐들이 들어갈 수 있는지 확인한다. 빈칸과 퍼즐의 사이즈는 딱 맞아야 한다. 즉, 두 배열의 가로, 세..

https://school.programmers.co.kr/learn/courses/30/lessons/86971# 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 전선들 중 하나를 골라 끊어야 한다. 따라서 wires를 하나씩 고르며 완전탐색을 진행했다.그리고 끊은 전선을 기준으로 dfs를 진행한다. 예를 들어, 3과 4를 이은 전선을 끊을 경우 3을 기준으로 이어진 송전탑들이 몇 개인지 dfs를 진행하고, 4를 기준으로 이어진 송전탑들이 몇 개인지 dfs를 진행한다. 그리고 두 값의 차이를 구한다.내가 유독 헷갈렸던 부분은 dfs에서 sum에 값을 더하고 ..

https://school.programmers.co.kr/learn/courses/30/lessons/84512?language=java 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 조금 헤맸는데 dfs로 쉽게 해결할 수 있는 문제였다. dfs로 "A", "E", "I", "O", "U"를 차례대로 이어서 만들어진 각 문자열들을 리스트에 담고, word가 몇 번째 문자열인지 확인하면 된다.이렇게 하면 시간 복잡도는 dfs(O(5^5)) + 완전탐색(O(5^5))이다.import java.util.*;class Solution { String[..

https://leetcode.com/problems/orderly-queue/description/ 어렵게 구현하다가 틀렸는데 답을 보니 굉장히 간단한 문제였다. k가 2이상인 경우, 문자들을 사전순으로 정렬한 것이 답이 된다.반면 k가 1이면, 문자열의 길이만큼 맨 앞 글자를 맨 뒤로 옮기는 작업을 진행한 후에, 가장 사전순으로 빠른 문자열을 반환하면 된다.알고리즘을 떠올리기 전에 문제를 읽고 무작정 예를 들어가며 이해해보자. 그러면 문제 이해를 통한 해결책이 떠오를 거다..!class Solution { public String orderlyQueue(String s, int k) { if (k >= 2) { char[] charArr = s.toCharArray(); Ar..

https://leetcode.com/problems/put-marbles-in-bags/description/ 혼자 고민하다가 백트래킹으로 풀었는데 시간 초과 + 오답이 났다. 그래서 다른 사람들 풀이를 봤는데 이해하지 못하다가 겨우 이해하고 다시 풀었다.  특별한 알고리즘은 아닌 거 같고 문제를 이해하고 답이 나오는 과정을 이해하면 해결방법을 떠올릴 수 있다.score는 각 가방의 cost를 모두 더한 값이다.score를 구할 때 weights 배열의 첫 번째와 마지막 값은 무조건 포함된다. 따라서 두 개의 값은 고려할 필요가 없다. 첫 번째와 마지막 값을 제외하면 score에 들어가는 값은 경계선에 있는 값들이다. 만약 0, 1, 2, 3, 4번 인덱스를 가진 weights를 2개의 가방에 나눠 담..

https://school.programmers.co.kr/learn/courses/30/lessons/42628# 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr풀이 1처음에 푼 풀이는 다음과 같다.최댓값과 최솟값을 구해야 하므로 큰 수를 우선으로 하는 우선순위 큐, 작은 수를 우선으로 하는 우선순위 큐 총 2개를 사용하면 된다.그런데 하나의 큐에서 제거된 값이 여전히 다른 큐에는 남아있으므로, 두 큐에 공통되게 담긴 수를 의미하는 set을 두었다. 그러고 하나의 큐에서 값을 제거할 때 정말 실제로 큐에 남아있는 값인지(두 큐에 공통되게 있는지) set.co..

https://school.programmers.co.kr/learn/courses/30/lessons/42627 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr현재 시간까지 들어온 job들을 찾는 과정에서는 job들 중에 요청 시간이 적은 순으로 빼내야 한다.이어서 현재 시간까지 들어온 job들 중 소요 시간이 가장 적은 job을 찾아야 하므로 이때는 job들 중에 소요 시간이 적은 순으로 빼내야 한다.따라서 요청 시간이 기준인 우선순위 큐와 소요 시간이 기준은 우선순위 큐로 총 2개의 큐를 사용하면 된다.주의할 점으로는, 큐를 사용할 때 항상 큐가 비어있는..

스택을 이용해서 푸는 문제이다. 쉬웠는데 딱 한가지 실수는 while 문에서 !stack.isEmpty() 를 넣어주지 않아서 런타임 에러가 발생했다. while문을 돌면서 스택에 값이 모두 빠져 비어있는 경우에도 while문을 돌 수 있기 때문에 !stack.isEmpty() 를 잊지말고 꼭 넣어주자!import java.util.*;class Solution { public int[] solution(int[] prices) { Stack stack = new Stack(); int[] answer = new int[prices.length]; for (int i = 0; i prices[i]) { i..

https://www.acmicpc.net/problem/12865 이차원 배열을 사용한 dp로 풀 수 있는 문제이다. dp[i][j]는 i번째 아이템까지 고려했을 때, 무게 j를 채우는 최대 가치를 의미한다.  만약 3번 아이템을 고려할 차례라고 할 때, dp[3][7]은 3번 아이템을 포함하지 않았을 때 무게 7을 채우는 최대 가치(= dp[2][7])와 3번 아이템을 포함했을 때 무게 7을 채우는 최대 가치(= 3번 아이템의 가치 + dp[2][7 - 3번 아이템의 무게]) 중 더 큰 값이 된다.  즉, 다음과 같은 점화식이 나온다.dp[i][j] = max(dp[i - 1][j], value[i] + dp[i - 1][j - weight[i]])import java.io.BufferedReader..

https://school.programmers.co.kr/learn/courses/30/lessons/42583 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr문제를 딱 보고 큐를 떠올리긴 했지만 효율적인 구현을 떠올리지 못했다. 다리에 올라간 트럭은 다리 길이만큼 다리에 머무르게 되는데, 이를 어떻게 구현하는게 효율적일지 고민하다가 혼자 힘으로 풀지 못했다. 주요 포인트는 다음과 같다.처음에 다리 길이만큼 0을 넣는다.그리고 다리에 트럭을 올릴 수 있으면(무게가 가능하면) 올린다. 반면 올릴 수 없으면 트럭대신 0을 올린다.즉, 큐에는 0이든 트럭이든 다리..