hansjour 개발일지

코드 구현import java.util.*;class Solution { public int solution(String begin, String target, String[] words) { Queue queue = new ArrayDeque(); boolean[] visited = new boolean[words.length]; queue.offer(new WordState(begin,0)); //방문 체크는 안해도 됨 while (!queue.isEmpty()){ //방문 (가까운 곳부터) WordState curr = queue.poll(); //방문한 곳이 내가 찾던 t..

문제 파악-주어진 배열을 끝까지 돌며 +,- 두 가지를 모두 구해 target값에 다다르는 경우의 수를 카운트주어지는 숫자의 개수는 2개 이상 20개 이하입니다.각 숫자는 1 이상 50 이하인 자연수입니다.타겟 넘버는 1 이상 1000 이하인 자연수입니다.접근 방법-완전 탐색이라서 dfs도 가능하지만, 큐가 조금 더 익숙해 큐로 풀이했다.-기준 뽑아 연결 된 노드(경우의 수)를 모두 큐에 넣고 같은 조건에서 값을 누적해나갔을 때 결과값을 비교-결과값이 맞기만 하면 카운트하면 되므로, 그냥 카운트한다.코드 구현import java.util.*;class Solution { public int solution(int[] numbers, int target) { Queue que=new Ar..

N-Queen  코드 구현import java.util.*;class Solution { int cnt=0; public int solution(int n) { //가로 세로 같은 줄에 있음 안되고, //대각선에 겹침 안됨.. //퀸 놓을 때마다 카운트, 말==n이면 카운트 //조건 뚫고 n개 다 놓을 수 있는 경우의 수를 구하기 //부모row != 자식row //부모col != 자식col //[row+1][col-1] || [row+1][col+1] => 대각선 //혹은 Math.abs(line[i]-col)==Math.abs(i-row) 여기서 i는 변하는 row값 int[] l..

https://leetcode.com/problems/word-search/  >접근 방법-dfs(backtrack)을 이용한 풀이dfs함수의 리턴값을 boolean으로 주어 방향마다 전진 가능한지 여부 체크-해당 노드가 유효하려면, 전진이 가능한지 여부도 체크해야함.-isValid() 조건 1) 범위 벗어나면X 2) 방문했으면X 3) charAt(idx)와 같아야함-재귀적으로 dfs 메서드 호출하고 하나라도 true를 반환하면 전체 탐색을 멈추고 true를 반환한다. 리턴되지 못하고 빠져나오면 false라는 의미이므로 방문 취소하고 다른 경우의 수 탐색-최종 리턴값이 boolean타입이기 때문에 dfs도 boolean타입인 게 헷갈리지 않음코드 구현class Solution { public boo..

https://leetcode.com/problems/permutation-sequence/  문제 파악1~n 까지의 수의 순열을 구하고, 그 중 k번째 순열을 문자열 형태로 리턴1 1 접근 방법-순열 문제코드 구현import java.util.*;class Solution { public String getPermutation(int n, int k) { String answer=""; List> permutations = new ArrayList(); boolean[] visited = new boolean[n]; String[] arr = new String[n]; for(int i=1;i(),visited,n,arr); ..

https://leetcode.com/problems/permutations/   문제 파악주어진 배열로 만들 수 있는 모든 순열 구하기1 10 All the integers of nums are unique. (요소 중복 허용)접근 방법💡 -재귀 함수가 리턴되면 마지막에 호출한 함수가 가장 먼저 리턴-리턴 되면 리스트에서 해당 원소 삭제, 방문 배열 초기화 - : 중복 허용, 순서 존재-방문 배열은 하나의 순열 안에서 이루어지는 것을 유의하자.해당 원소에 해당하는 경우의 수를 모두 순회하면서 겹치지 않게 표시 코드 구현import java.util.*;class Solution { //순열 문제 : 중복 허용, 순서 존재 public List> permute(int[] nums) { ..

https://leetcode.com/problems/combinations/ 문제 파악주어진 1~n까지의 범위 중에서, k개의 원소를 갖는 숫자 ‘조합’ 구하기1 1 접근 방법💡 backtrack() 함수 정의하여, 가장 작은 단위의 연산을 정의하고, 재귀적으로 해당 함수를 호출한다. 코드 구현class combinations { public List> combine(int n, int k) { //1~n까지 숫자 중에 k개를 짝지은 조합을 찾아내기 List> result = new ArrayList(); int start = 1; //시작점을 값으로 전달해주기. // 함수에 유동적으로 인자를 주고 싶을 때 사용, 함수에 인자가 증가하며 삽입될..

https://leetcode.com/problems/subsets/description/문제 파악주어진 배열에서 나올 수 있는 subset 모두 구하기(조합)1 10 All the numbers of nums are unique.접근 방법💡 -combination으로 순서가 없는 리스트를 담아 최종 result에 적재-”combinations” 문제와 흡사-조건 걸지 않고 조합 만들어지는대로(길이n) 결과로 반환하는 것이 포인트 코드 구현import java.util.*;class Solution { public List> subsets(int[] nums) { List> result = new ArrayList(); List curr = new ArrayList(); ..

피로도https://campus.programmers.co.kr/tryouts/140902/challenges  문제 파악💡 -dfs, bfs, dp로도 풀 수 있는 문제-가진 체력으로 각 던전을 돌며 최대 던전 돌 수 있는 횟수 구하기-똑같은 게 계속 반복된다. ⇒ 작은 문제로 줄여서 풀기 (재귀)-순차적으로 돌 필요 없고 어떤 조합이든 많이 돌 수 있는 방법 찾기.k는 1 이상 5,000 이하인 자연수입니다.dungeons의 세로(행) 길이(즉, 던전의 개수)는 1 이상 8 이하입니다.dungeons의 가로(열) 길이는 2 입니다.dungeons의 각 행은 각 던전의 ["최소 필요 피로도", "소모 피로도"] 입니다."최소 필요 피로도"는 항상 "소모 피로도"보다 크거나 같습니다."최소 필요 피로도..

소수 찾기https://campus.programmers.co.kr/tryouts/140903/challenges 문제 파악순열 문제. 가장 효율적인 방법을 찾아보자.numbers는 길이 1 이상 7 이하인 문자열입니다.numbers는 0~9까지 숫자만으로 이루어져 있습니다."013"은 0, 1, 3 숫자가 적힌 종이 조각이 흩어져있다는 의미입니다. 접근 방법💡 permutations 문제와 비슷하지만, curr가 특정 길이 충족되면 result에 추가했던 것과 달리, 가는 도중에 보일 때마다 result에 curr값 추가한다.즉, 길이는 정해지지 않았고 길이가 어떻든 조건 만족하면 리스트에 추가.base case는 카운트되는 것으로 변경소수 구하는 함수는 isPrime() 으로 별도로 선언한다. (리..