본문 바로가기

알고리즘146

[Java] DFS [Java] DFS 전위 순회 class Solution { public void DFS(int v) { if (v > 7) return; else { System.out.print(v + " "); DFS(v * 2); DFS(v * 2 + 1); } } public static void main(String[] args) { Solution T = new Solution(); T.DFS(1); } } // return : 1 2 4 5 3 6 7 중위 순회 class Solution { public void DFS(int v) { if (v > 7) return; else { DFS(v * 2); System.out.print(v + " "); DFS(v * 2 + 1); } } public stat.. 2023. 10. 12.
꼭 보기! 20231003 [Java] 문제풀이 (다익스트라 + dfs) 꼭 보기! 20231003 [Java] 문제풀이 (다익스트라 + dfs) [프로그래머스] 배달 - 다익스트라 다익스트라 알고리즘을 활용 1부터 시작하여, 모든 마을들에 갈 수 있는 최적의 거리를 계산 그 후, 1부터 시작하여 모든 마을들에 갈 수 있는 거리들을 순회하며, 답을 찾는다 import java.util.*; class Solution { static class Node { int to; int distance; Node(int to, int distance) { this.to = to; this.distance = distance; } } public int solution(int N, int[][] road, int K) { int answer = 0; int[] allDistances = .. 2023. 10. 3.
20230925 [Java] 문제풀이 20230925 [Java] 문제풀이 [프로그래머스] 주식가격 그냥 2중 for문을 사용하여, prices에 있는 원소들을 서로 비교하면 되는 문제다 크거나 같으면 다음 prices 원소를 순회한다 작으면 바로 break class Solution { public int[] solution(int[] prices) { int[] answer = new int[prices.length]; for (int i = 0; i prices[j]) break; } answer[i] = count; } return ans.. 2023. 9. 26.
20230918 [Java] 문제풀이 20230918 [Java] 문제풀이 [프로그래머스] 프로세스 우선순위 큐를 사용해서 프로세스의 우선순위를 찾는다 여기서 우선순위 큐는 내림차순으로 만들어야 한다 그리고 큐에 priorities를 프로세스의 인덱스와 프로세스의 우선순위를 배열로 넣어준다 큐를 돌면서 우선순위가 같은 프로세스를 result 리스트에 넣어주고 우선순위 큐에서 해당 우선순위는 빼주고, 큐에서도 빼준다 큐를 돈다는 것은, 우선순위가 같지 않으면 큐의 맨 뒤로 돌아가게 된다 import java.util.*; class Solution { public int solution(int[] priorities, int location) { ArrayList result = new ArrayList(); PriorityQueue pq =.. 2023. 9. 18.
20230917 [Java] 문제풀이 20230917 [Java] 문제풀이 [프로그래머스] 소수 찾기 isNotSuso 배열에 0부터 9999999까지 수소의 여부를 true 또는 false로 설정한다 수소이면 false / 아니면 true 이다 permutation, 순열을 통해서 주어진 숫자에서, 만들 수 있는 모든 숫자들을 만든다 숫자들을 만들 때에 중복이 될 수 있기 때문에, set에 넣어준다 set에서 숫자들을 빼면서 수소인지 아닌지 인덱스를 통해서 개수를 센다 import java.util.*; class Solution { HashSet set = new HashSet(); boolean[] isNotSuso = new boolean[10000000]; int count = 0; public void permutation(Str.. 2023. 9. 18.
20230913 [Java] 문제풀이 20230913 [Java] 문제풀이 [프로그래머스] 문자열 압축 입력되는 문자열을 압축하는 것이다 단 문자 단위는 같아야 하고, 연속되는 문자가 같으면 압축을 한다 class Solution { public int solution(String s) { int answer = s.length(); if (s.length() == 1) return 1; for (int i = 1; i = 2) { comString += String.format("%d", cnt); } comString += tempS; tempS = tempCompare; cnt = 1; } } if (cnt > 1) comString += String.format("%d", cnt) + tempS; else comString += te.. 2023. 9. 13.
20230912 [Java] 문제풀이 20230912 [Java] 문제풀이 [프로그래머스] 스킬 트리 기술을 배우기 위해, 앞에 미리 배워야 하는 기술이 있다 A -> B -> C : C를 배우려면 B를 배워야 하고, B를 배우려면 A를 배워야 한다 즉 A를 배우고 바로 C를 배울 수 없다 그 외에 주어진 것들은 언제든 배울 수 있다 Queue에다가 순서대로 배워야 하는 기술들을 넣는다 (skill들) skill_trees를 순회하면서, Queue 대로 즉 선입선출 로직으로 기술들을 배우는지 확인을 한다 skill = {A, B, C} skill_trees = {B, C} B는 skill에 있지만, 먼저 배워야 하는 A가 있기 때문에 기술을 배울 수 없다 import java.util.*; class Solution { public int .. 2023. 9. 12.
20230906 [Java] 문제풀이 20230906 [Java] 문제풀이 [프로그래머스] 메뉴 리뉴얼 문자열을 리스트로 잘 만들고, 2중 리스트에서, 리스트 크기에 따라서 정렬을 한다 {2}, {2, 1}, {2, 1, 3}, {2, 1, 3, 4}} 2 를 answer에 제일 앞 부분에 넣는다 (2) {2} 와 {2, 1} 을 비교하여, 없는 숫자를 answer에 넣는다 (1) {2, 1}와 {2, 1, 3} 을 비교하여, 없는 숫자를 answer에 넣는다 (3) {2, 1, 3}와 {2, 1, 3, 4} 을 비교하여, 없는 숫자를 answer에 넣는다 (4) import java.util.*; class Solution { public ArrayList solution(String s) { ArrayList answer = new Ar.. 2023. 9. 8.
20230905 [Java] 문제풀이 20230905 [Java] 문제풀이 [프로그래머스] 괄호 회전하기 .substring 을 이용해서, 문자열을 슬라이싱 하면서 문자열을 한바퀴 돌린다 한바퀴 돌리면서 stack을 사용하여 괄호 문자열이 유효한지 확인해준다 import java.util.*; class Solution { public static boolean isCorrect(String str) { Stack stack = new Stack(); for (int i = 0; i < str.length(); i++) { if (str.charAt(i) == '(' || str.charAt(i) == '[' || str.charAt(i) == '{') { stack.push(str.charAt(i)); } else { if (stack.i.. 2023. 9. 8.

티스토리툴바