코딩 정복 가즈아~

(っ◔◡◔)っ ♥ 2021 취뽀하자!! ♥

알고리즘 풀이/프로그래머스

- "ICN"에서 출발하여, 모든 티켓을 다 사용하여, 갈 수 있는 모든 경로를 ArrayList에 넣는다. - 구한 경로를 알파벳순으로 정렬한 다음 맨 처음 것을 배열로 바꾸어 리턴한다. import java.util.*; class Solution { static boolean isVisited[]; static ArrayList answer; public static String[] solution(String[][] tickets) { answer = new ArrayList(); isVisited = new boolean[tickets.length]; dfs(tickets, "ICN", "ICN", 1); Collections.sort(answer); return answer.get(0).spl..

2021. 9. 14.

알고리즘 풀이/프로그래머스

전체 코드는 맨 밑에 있어요. [ 문제 풀이 ] - 바꿀 수 있는 단어로 모두 바꿔보며 완전탐색한다. [ 풀이 방법 ] - begin에서 바꿀 수 있는 경우에 대해서 모두 탐색을 해본다. => begin과 words[i]의 알파벳 차이가 1개인 경우 - 알파벳 차이가 1인 단어("hot")가 또 다시 바꿀 수 있는 경우를 찾아 바꾸면서 target인 cog까지 바꿀 수 있는지 확인한다. 이때, 이미 바꾼 단어로 또 바뀌는 것을 막기 위해 isVisited를 사용한다. 또, 바꿔진 횟수를 알기 위해 단어를 변경할 때 마다 cnt를 하나씩 증가시킨다. - hot이 바꿀 수있는 단어인 "dot", "lot"으로 차례대로 바꿔본다. 먼저, dot으로 바꿔보면 다음과 같다. - 이런식으로 방문처리를 하며, 바꿔서..

2021. 9. 14.

알고리즘 풀이/프로그래머스

- 1~n개의 네트워크에 대해 탐색한다. => dfs - 만약 연결된 네트워크중에 탐색하지 않은게 있다면, 계속해서 타고 들어가 탐색을 계속한다. class Solution { static boolean[] isVisited; public int solution(int n, int[][] computers) { int answer = 0; isVisited = new boolean[n]; // 방문 처리 for(int i = 0; i < n; i++) { if(!isVisited[i]) { dfs(i, computers); answer++; } } return answer; } static void dfs(int cur, int[][] computers) { isVisited[cur] = true; fo..

2021. 9. 14.

알고리즘 풀이/프로그래머스

- dfs를 응용하여 각 숫자를 더했다가 빼보면 된다. 그러면 numbers의 숫자를 빼고 더하는 모든 경우의 수에 대해 탐색 가능! class Solution { static int answer = 0; public int solution(int[] numbers, int target) { makeTargetNum(numbers, target, 0, 0); return answer; } static void makeTargetNum(int[] numbers, int target, int cnt, int sum) { if(cnt == numbers.length) { if(sum == target) answer++; return; } makeTargetNum(numbers, target, cnt + 1, ..

2021. 9. 14.

알고리즘 풀이/프로그래머스

[ 문제 풀이 ] - [ 1, 2, 4 ]로만 숫자를 구성해야 한다. => 숫자 3가지만 사용하는 것이, 3진수를 사용하는 것과 같다. - 숫자 3가지만 사용하는 것이, 3진수를 사용하는 것과 같다. => num[ "4", "1", "2"] 에서 해당 index로 접근하여 문자열에 더해준다. N 3으로 나눈 나머지 3으로 나눈 몫 1 1 0 2 2 0 3 0 1 => 3으로 나누어 떨어지는 경우, 몫이 1개 더 생기기 때문에 빼준다!!! 0 4 1 1 5 2 1 6 0 2 => 3으로 나누어 떨어지는 경우, 몫이 1개 더 생기기 때문에 빼준다!!! 1 [ 전체 코드 ] class Solution { public String solution(int n) { String answer = ""; String ..

2021. 9. 12.

알고리즘 풀이/프로그래머스

레벨2에.. 효율성이라니요!!!! 개인적으로는 지금까지 차례대로 푼 1~2단계 문제중엔 제일 어려웠다.. 방법을 몰라서..ㅎ [ 문제 해석 ] - 이 문제는 시간초과가 있으므로, info와 query를 하나씩 비교하면 시간초과가 난다ㅠㅠ - info가 포함될 수 있는 모든 경우의 수를 map에 key로 넣고 점수를 value로 넣어준다. - query를 key로하는 value들을 가져와서 이분탐색한다!! => 그래야 시간초과가 안 난다.ㅠㅠ [ 풀이 방법 ] 1. info에 있는 값을 다음과 같이 바꿔준다. { "언어", "직군", "경력", "소울푸드", "점수" } ex) "java backend junior pizza 150" 2. "언어", "직군", "경력", "소울푸드" 가 속할 수 있는 모든..

2021. 9. 12.

알고리즘 풀이/프로그래머스

[ 풀이 방법 ] - 직선을 그리는 일차 방정식(y = ax)를 이용하여 수식을 만든다. y = x * h / w - 기울기인 h / w를 먼저 계산하게 되면, 소수점을 정확히 구할 수는 없기 때문에 값이 불완전해져 6번 테스트 케이스가 틀린다.ㅠㅠ => x를 먼저 h와 곱한 후, w로 나누자 - 1부터 w전까지의 정수를 방정식에 대입하여, 온전한 정사각형 개수를 센다. 위에서 구한 y = i * h / w 에 1 ~ (w-1)의 값을 대입해준다. y의 값을 내림했을때의 값 = 온전한 사각형의 크기 - 위에서 구한 값들의 합이 '1*1 정사각형의 크기'이다. [ 전체 코드 ] class Solution { public long solution(int w, int h) { long answer = 0; /..

2021. 9. 11.

알고리즘 풀이/프로그래머스

[ 풀이 방법 ] 1. 각 숫자가 나온 횟수를 HashMap에 저장 2. 횟수(value)를 기준으로 키를 내림차순 정렬 3. List(keySet)를 int배열(answer)로 바꿔서 리턴! [ 전체 코드 ] import java.util.ArrayList; import java.util.Collections; import java.util.HashMap; import java.util.List; import java.util.StringTokenizer; class Solution { public static int[] solution(String s) { // 숫자만 자르기 StringTokenizer st = new StringTokenizer(s, "},{"); // 숫자가 나온 횟수 세기 Ha..

2021. 9. 10.