알고리즘/프로그래머스
-
공원 산책알고리즘/프로그래머스 2023. 5. 11. 10:38
문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/172928 해설 이차원 배열로 공원 맵을 만들면 편하게 작업할 수 있다. 공원의 길이가 가로, 세로 각각 50이기 때문에 O(N^2)의 시간복잡도를 가져도 괜찮다. 코드 class Solution { public int[] solution(String[] park, String[] routes) { int[] startPoint = new int[2]; int height = park.length; int width = park[0].length(); char[][] parkMap = new char[park.length][park[0].length()]; for (int i = 0; i ..
-
추억 점수알고리즘/프로그래머스 2023. 5. 11. 10:32
문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/176963 해설 길이가 많이 길지 않으므로 O(N^2)로 편하게 풀면 된다 코드 import java.util.*; class Solution { public int[] solution(String[] name, int[] yearning, String[][] photo) { Map nameYearingMap = new HashMap(); int size = name.length; for (int i = 0; i < size; ++i) { nameYearingMap.put(name[i], yearning[i]); } List answer = new ArrayList(); for (int i..
-
[Java] 달리기 경주알고리즘/프로그래머스 2023. 5. 3. 12:04
문제 링크 callings의 길이가 최대 1,000,000개이므로 이중 반복문을 사용해서 시간 복잡도가 O(N^2)이 나오도록 작업하면 시간 초과가 뜹니다. class Solution { public String[] solution(String[] players, String[] callings) { for (int i = 0; i < callings.length; ++i) { for (int j = 0; j < players.length; ++j) { if (callings[i].equals(players[j])) { String temp = players[j - 1]; players[j - 1] = players[j]; players[j] = temp; break; } } } return player..
-
[프로그래머스] 순위알고리즘/프로그래머스 2021. 9. 16. 12:46
문제 링크 풀이 이 문제는 모든 정점에 대해 최단 경로를 찾는 플로이드-워셜 알고리즘을 이용해 풀 수 있습니다. 주어진 예제를 통해 이 알고리즘을 어떻게 적용하는지 알아보겠습니다. 주어진 예제는 {4, 3}, {4, 2}, {3, 2}, {1, 2}, {2, 5} 입니다. {A, B}에서 A는 B를 항상 이깁니다 - 2는 네 번의 경기를 하므로 순위가 확정적으로 정해집니다 - 5번이 2번에게 확실하게 지는 거라면, 5번은 2번을 이기는 모든 선수에게도 집니다 - {4,2} {2,5}에서 {4,5}가 도출됩니다 - 그러므로 {4, 5}, {3, 5}, {1, 5}, {2, 5}가 성립합니다 코드 #include #include using namespace std; int solution(int n, vec..
-
[프로그래머스] 정수 삼각형알고리즘/프로그래머스 2021. 9. 15. 19:53
문제 링크 풀이 점화식 d[i][j]는 왼쪽 대각선 위인 d[i-1][j-1]와 오른쪽 대각선 위인 d[i-1][j] 중에서 큰 값을 triangle[i][j]와 더해준 값입니다. d[i][j] = max(d[i-1][j-1], d[i-1][j]) + t[i][j] 코드 #include #include using namespace std; int wrap(int a) { return a < 0 ? 0 : a; } int solution(vector triangle) { int answer = 0; int size = triangle.size(); vector d(size, vector(size, 0)); for (int i = 0; i < triangle.size(); ++i) for (int j = 0..
-
[프로그래머스] 디스크 컨트롤러알고리즘/프로그래머스 2021. 9. 15. 18:29
문제 링크 풀이 1) 지금 처리되고 있는 작업이 끝나는 시간(현재 시간)을 초과하지 않으면 2) 요청된 작업들은 우선 순위 큐에 담아 작업 시간이 빠른 순서대로 처리합니다. 3) 그렇지 않은 작업은 요청 시간이 도래할 때까지 기다렸다가 1번, 2번을 반복합니다. 우선 순위 큐에 비교 함수를 넣을 때 함수 객체를 넣어도 되고 람다 표현식을 넣어도 됩니다. 내부적으로 생성자를 호출하는데 람다식은 생성자가 없기 때문에 직접 초기화해줘야 합니다. 템플릿으로 넣어주는 것은 타입이기 때문입니다. 코드 #include #include #include #include using namespace std; int solution(vector jobs) { int answer = 0, current_time = 0; in..
-
[프로그래머스] N으로 표현알고리즘/프로그래머스 2021. 8. 17. 21:18
문제 링크 풀이 많은 DP 문제가 그렇듯 점화식만 제대로 세울 수 있으면 어렵지 않은 문제이지만, 꽤 까다로운 문제에 속하는 것 같습니다. 여기에서 d[i]는 solution 함수의 매개변수로 주어지는 N을 i번 사용해서 얻을 수 있는 숫자의 집합으로 정의해 문제를 풀면 수월합니다. 즉 N이 5라면 다음과 같은 점화식을 만들 수 있습니다. d[1] = {5} d[2] = {55, 5+5, 5-5, 5*5, 5/5} d[3] = {555, (5+5) + 5, (5+5) - 5, (5+5) * 5, ... , 55 / 5} 3번째 항부터는 집합의 크기가 커지기 시작합니다. 우리는 규칙을 찾아야 하고요. 일단 N이 i만큼 붙어 있는 숫자 하나는 만들기 쉽습니다. d[4]에는 5555가 있겠지요. d[2]를 보..
-
[프로그래머스] 가장 먼 노드알고리즘/프로그래머스 2021. 8. 16. 15:20
문제 링크 풀이 bfs를 이용하면 방문하는 노드가 최단거리가 됩니다. 거리를 기록하는 배열인 dist를 이용해 지금 노드에서 다음 노드를 방문할 때 +1을 해서 값을 갱신합니다. 코드 #include #include #include using namespace std; int solution(int n, vector edge) { int answer = 0; vector vec(n + 1, vector(n + 1)); size_t size = edge.size(); for (int i = 0; i < size; ++i) { auto n1 = edge[i][0]; auto n2 = edge[i][1]; vec[n1][n2] = 1; vec[n2][n1] = 1; } vector visited(n + 1, ..