chuseok

정수 n과 k가 있는데, 1부터 n까지 숫자로 만드는 모든 순열을 나열해서 k번째 순열 구하는 문제풀이 순서조합을 찾는 방법은 backtracking 활용, 1부터 시작, 방문 추적함 모든 조합을 구하는 문제이기 때문에순열을 구하는 공식은 1의 자리, 10의 자리, 100의 자리 이렇게 하나씩 cur에 담아서 구할 수 있도록cur * 10 씩 곱하고 여기에 현재 들어오는 값 i를 더함 그러면 들어오는 순서대로 한자리씩 커져서 왼쪽에서 오른쪽으로 숫자가 쌓임 풀이 시작 1:40풀이 종료 2:20다시 풀이내 풀이class Solution { List answer; boolean[] visited; public String getPermutation(int n, int k) { a..

릴레이션이 주어질 때 유일성과 최소성을 만족하는 후보키 갯수 구하기풀이 순서속성의 조합을 구하는 방법으로 backtracking 을 활용1. 조합을 구하기 위해 속성의 길이를 설정해 backtracking 시도(길이 1부터 시작)2. 컬럼이 중복되지 않도록 방문 추적, 이 때 조합을 만들지 않는 이유는 3번에서 설명3. 현재까지 backtrack을 수행한 값 => cur == 속성의 길이 => end와 같을 때 조합의 길이가 충족돼서 검사 시작4. 유일성 판별을 위한 List 타입과 최소성 길이 판별을 위한 String 타입 데이터에 방문한 값을 릴레이션을 돌며 추가5. 유일성 판별, 맞으면 Set에 추가 아니면 backtracking 종료6. 최소성 판별, 최초 조합 최종 list에 담고 들어오는 순서..

unique한 값이 하나씩 담겨있는 배열이 주어지는데 값이 중복되지 않는 부분 집합을 순서에 상관없이 구하는 문제풀이 순서조합을 찾는 방법은 backtracking 활용소수 찾기는 에라토스테네스의 체 활용 풀이 시작 1:40풀이 종료 2:20 다시 풀이List를 활용했는데 중복을 찾으려면 계속해서 for을 돌며 찾아야 돼서 HashSet으로 변경함backtrack에서 거꾸로 조합을 담기 위해 i+1을 하지 않았고, 모든 경우의 수를 찾기 위해 used 배열을 사용함한 값이 하나씩 담겨있는 배열이 주어지는데 값이 중복되지 않는 부분 집합을 순서에 상관없이 구하는 문제 풀이 순서조합을 찾는 방법은 backtracking 활용 소수 찾기는 에라토스테네스의 체 활용 풀이 시작 1:40 풀이 종료 2:20 ..

unique한 값이 하나씩 담겨있는 배열이 주어지는데 값이 중복되지 않는 부분 집합을 순서에 상관없이 구하는 문제풀이 순서backtracking 문제카운팅이 필요없고 하나씩 결과 그려보고 이해하면서 진행 풀이 시작풀이 종료 다시 풀이 내 풀이다른 사람의 풀이 참고class Solution { List> answer; public List> subsets(int[] nums) { answer = new ArrayList(); backtrack(0, new ArrayList(), nums); return answer; } private void backtrack(int start, List list, int[] nums) { answe..

1~n개의 연속된 숫자 중에서 k개의 조합으로 순서를 고려하지 않고 값에 대한 중복이 없는 조합들을 담은 배열을 구하는 문제풀이 순서backtracking 문제1부터 시작하고 4개의 숫자 중 2개를 카운팅하기 때문에 카운팅 변수가 필요하다 풀이 시작 23:08풀이 종료 23:11 다시 풀이 내 풀이class Solution { List> answer; public List> combine(int n, int k) { answer = new ArrayList(); backtrack(1, 0, new ArrayList(), n, k); return answer; } private void backtrack(int start, int cnt, Lis..

int[] nums가 주어질 때 중복이 없는 순열 조합 구하기원소의 합이 같게 만들 수 없으면 -1 반환long 타입 고려할 것풀이 순서backtracking 문제수열의 조합을 담을 List가 필요한데 수열 List를 담을 때 같은 list를 공유하지 않도록 다른 객체를 넣어야 함그리고 인덱스 방문을 체크하는 배열이 필요함하나씩 방문하며 백트래킹 수행 풀이 시작풀이 종료 다시 풀이 내 풀이다른 사람의 풀이 참고import java.util.*;class Solution { List> ans = new ArrayList(); boolean[] visited; public List> permute(int[] nums) { visited = new boolean[nums.leng..

먼저 배포되어야 하는 순서대로 작업의 진도가 적힌 정수 배열 progresses와 각 작업의 개발 속도가 적힌 정수 배열 speeds가 주어질 때 각 배포마다 몇 개의 기능이 배포되는지 찾는 문제원소의 합이 같게 만들 수 없으면 -1 반환long 타입 고려할 것풀이 순서Math.ceil((100.0 - progresses[i]) / 개발 속도[i]) = 올림 처리한 작업 일수순차적으로 꺼내기 위해 queue올림 처리를 위해 실수로 계산, 마지막 타입 고려할 것while(!isEmpty)cnt = 1;cur = poll()while(!isEmpty() && 현재 작업이 ≥ 다음 작업) {cnt++;제거}list.add(cnt); 풀이 시작 20:40풀이 종료 20:57 다시 풀이 내 풀이import ja..

컬렉션 프레임워크 종류 컬렉션 프레임워크는 크게 Collection 인터페이스와 Map 인터페이스로 나뉜다.Map 인터페이스 컬렉션들은 두개의 데이터를 묶어 한쌍으로 다루기 때문에 Collection 인터페이스와 따로 분리되어 있다. 💡 Tip대부분의 컬렉션 클래스들은 List, Set , Map 중의 하나를 구현하고 있으며, 구현한 인터페이스의 이름이 클래스 이름에 포함되는 특징이 있다. (ArrayList, HashSet, HashMap ... 등)그러나 Vector, Stack, Hashtable, Properties 와 같은 클래스들은 컬렉션 프레임워크가 만들어지기 이전부터 존재하던 것이기 때문에 컬렉션 프레임워크의 명명법을 따르지 않는다. 또한 Vector 나 Hashtable 과 같은 기존의..

초 단위로 주식가격이 담긴 prices에서 가격이 떨어지지 않은 기간은 몇초인지 구하는 문제원소의 합이 같게 만들 수 없으면 -1 반환long 타입 고려할 것풀이 순서현재 가격이 stack에 떨어진 가격을 만나지 않은 시간의 가격보다 작으면 주식가격이 떨어진 것이다 풀이 시작 17:00풀이 종료 17:05 다시 풀이 내 풀이import java.util.*;class Solution { public int[] solution(int[] prices) { Deque stack = new ArrayDeque(); for(int i=0; i다른 사람의 풀이 참고class Solution { public int[] solution(int[] prices) { i..

(), [], {} 올바른 괄호 문자열이 s를 왼쪽으로 s의 길이 = x만큼 회전시켰을 때, 올바른 괄호 문자열이 되게 하는 x의 개수원소의 합이 같게 만들 수 없으면 -1 반환long 타입 고려할 것풀이 순서s의 길이만큼 반복해서 유효한 괄호인지 확인 풀이 시작 01:06풀이 종료 01::36 다시 풀이 내 풀이import java.util.*;class Solution { public int solution(String s) { int cnt = 0; s = s + s; for(int i=0; i stack = new ArrayDeque(); for(char c: s.toCharArray()) { if(isO..