안정적인 문자열 - 백준 4889 (Java) https://www.acmicpc.net/problem/4889 풀이 1. { 는 stack에 넣는다. 2. } 일 때는, stack이 비어있을 때는 count+1을 하고 { 로 바꿔서 stack에 넣어준다. stack이 비어있지 않을 때에는 stack에 저장된 { 을 pop하여 짝을 짓는다. 3. 모든 과정을 마친 후, stack에 남은 { 의 갯수의 절반을 count에 더해준다. 4개가 남았다면 2개를 } 로 바꿔주면 안정적인 문자열이 되기 때문이다. 즉, stack이 empty하게 만드는 것이다. count() private static int count(Stack stk, String str) { int answer = 0; int length = str.length(); for (int i =.. 2022. 8. 11. 문자열 압축 - 프로그래머스 (Java , Level 3) 처음 풀이 1. 단위를 1 ~ 전체길이의 절반까지 1씩 증가하면서 압축한다. 2. 압축된 최소 길이만 구하면 되기 때문에, 단위 크기로 자른 후 앞과 같은지 다른지 비교 후, 같으면 갯수를 1 증가, 다르면 현재까지 같았던 갯수의 자릿수와 단위 크기를 더해준다. solution() public int solution(String s) { int length = s.length(); //길이가 1일 땐 1 리턴 if (length==1) return 1; int min = Integer.MAX_VALUE; //절반 길이까지 단위 크기를 늘려가면서 압축 길이 갱신 for (int i = 1; i 2022. 8. 10. 스킬트리 - 프로그래머스 (Java, Level 2) https://school.programmers.co.kr/learn/courses/30/lessons/49993 처음 풀이 public int solution(String skill, String[] skillTrees) { char[] charArr = skill.toCharArray(); //skill 탐색 위한 index (index+1부터) int index = -1; int cnt = 0; //선행 스킬에 포함되지만 순서 맞지 않는 경우, //연산을 빠져나오기 위한 flag boolean check = true; for (String skillTree : skillTrees) { //새 skillTree마다 check, index 변수 초기화 check = true; index = -1; in.. 2022. 8. 5. 땅따먹기 - 프로그래머스 (Java, Level 2) https://www.acmicpc.net/blog/view/109 각 행에서 이전 행의 최댓값인 열을 제외한 나머지 3열 중 최댓값을 선택하면 될 줄 알았다. 하지만, 이전 행의 최댓값인 열과 현재 행의 최댓값인 열이 같을 경우, 이전 행의 선택을 바꾸는 것과 현재 행의 선택을 바꾸는 것은 총합의 차이를 가져온다. 즉, 현재의 선택이 매번 계속 다음 선택에 영향을 미친다. 그래서 다음 생각은 모든 경우를 고려하는 dfs를 생각했다. 하지만 행의 수가 100,000까지 가능했기 때문에 아니나 다를까 런타임 에러가 났다. PriorityQueue pq= new PriorityQueue(Collections.reverseOrder()); boolean[] isUsed = new boolean[4]; publ.. 2022. 8. 5. 디스크 컨트롤러 - 프로그래머스 (Java, Level 3) https://school.programmers.co.kr/learn/courses/30/lessons/42627 풀이 package programmers; import java.util.Comparator; import java.util.PriorityQueue; public class 디스크컨트롤러 { public class Job { int startTime; int requiredTime; Job(int startTime, int requiredTime) { this.startTime = startTime; this.requiredTime = requiredTime; } } public int solution(int[][] jobs) { int currentTime = 0; int sum = 0;.. 2022. 8. 5. 프린터 - 프로그래머스 (Java, Level 2) https://school.programmers.co.kr/learn/courses/30/lessons/42587?language=java 처음 풀이 import java.util.ArrayList; import java.util.Arrays; import java.util.LinkedList; import java.util.List; import java.util.Queue; public class 프린터 { Integer[] dump = {0, -1}; public int solution(int[] priorities, int location) { //요청리스트 Queue reqList = new LinkedList(); //실제 인쇄리스트 List printList = new ArrayList();.. 2022. 8. 4. 트리 순회 - 백준 1991 (Java) https://www.acmicpc.net/problem/1991 입력한 값에 따라 트리에 노드를 추가하는 메소드 (insertNode()) 해당 트리를 순회(전위, 중위, 후위)하는 메소드 필요 (~Order()) C E F를 입력하면 C노드(데이터 C를 가진 노드)의 좌측 자식노드에는 E노드, 우측 자식노드에는 F노드를 추가해야 한다. 그러기 위해선 특정 데이터 값을 가지는 노드를 찾는 메소드가 필요 (searchNode()) 여기서는 searchNode()를 호출하면, 찾는 노드가 있으면 pointer 변수가 해당 노드의 주소를 참조하고, 없으면 null값이다. 개념 searchNode()와 ~Order()에서 사용한 재귀호출 (중단조건, stack구조로 메소드 호출) 순회(전위, 중위, 후위) 순.. 2022. 8. 3. 길 찾기 게임 - 2019 Kakao Blind Recruitment (Java, Level 3) https://school.programmers.co.kr/learn/courses/30/lessons/42892 풀이 노드들을 그래프에 나타내보면 BST의 전체 모습을 알 수 있다. 해당 모습의 BST가 되기 위해서는 루트 노드부터 리프 노드까지 차례대로 해당 노드를 트리에 add해야 한다.(BST의 문제점으로 자료 삽입 순서에 따라 트리의 구조가 바뀌는 점이 있다.) 따라서 nodeInfo에 담긴 노드 정보를 순서에 맞게 정렬해야 한다. 정렬 기준은 첫 번째는 y값이 큰 순서대로, 두 번째는 같은 y값이라면 x값이 작은 순서대로! Node 클래스 static class Node { int num; int x; int y; Node parent; Node leftChild; Node rightChild.. 2022. 7. 30. 키 순서 - 백준 2458 (Java) https://www.acmicpc.net/problem/2458 풀이 문제에 주어진 대로 관계가 주어진 학생을 2차원 그래프로 나타낸다. 순위가 정해진다는 의미는 자신보다 크거나 작은 것이 결정된 학생 수가 (전체 학생 수 - 1)이 된다는 뜻이다. 자신을 기준으로 키가 크거나 작은 학생을 bfs로 탐색하여(greaterBfs(), lessBfs()) 각각 몇 명인지 알아내고 합을 구하면 된다. main() //학생들 간의 관계 저장할 2차원 배열 static int[][] graph; static int N; static boolean[] isVisited; public static void main(String[] args) throws IOException { BufferedReader bf = .. 2022. 7. 26. 멀쩡한 사각형 - Summer/Winter Coding 2019 (Java, Level 2) https://school.programmers.co.kr/learn/courses/30/lessons/62048 처음 풀이 public long solution(int w, int h) { //가로로 한칸씩 움직이면서 대각선이 지나는 위치(y좌표)를 보고 //지나가는 사각형의 개수를 계속 더해준다. //각 구간의 처음 지나가는 사각형의 위치 //현재 대각선의 y좌표가 2.5라면 2 이후의 사각형부터 지나간다. int prevFlr = 0; int sumOfUnUsedSqr = 0; double division = h/(double)w; for(int i=1; i 2022. 7. 25. 이전 1 2 3 4 ··· 8 다음
