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

BFS로 풀어야 하는 문제라고 한다.. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152import java.util.*; class Solution { private static int[] dr = {0, 1, 0, -1}; private static int[] dc = {1, 0, -1, 0}; private static boolean[][] visited; private static int n, m; public int solution(int[][] maps) { n= maps.length; m= maps[0].length; visited = new boolean[n][m]; r..

알파벳을 바꾸는 부분은 어렵지 않다.. 중요한 부분은 좌우키를 어떤 식으로 움직여서 최소한으로 움직이느냐인데.. 실패했다 Line:19가 너무나 중요함 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 import java.util.*; class Solution { private static int answer; // private static List noAindexList; public int solution(String name) { answer = 0; int len = name.length(); int min = name.length()-1; for(i..

220607 12345678910111213141516171819202122232425262728293031323334353637383940import java.util.*; class Solution { public int solution(String numbers) { int answer = 0; Set set = new HashSet(); permutation("", numbers, set); while(set.iterator().hasNext()){ int a = set.iterator().next(); set.remove(a); if(isPrime(a)){ answer++; } } return answer; } private boolean isPrime(int n){ if(n==2) return..

테케 11번 반례 [0, 0, 0] => "000" (x) [0, 0, 0] => "0" (o) clearZero메서드를 하나 만들어줌 만들어줬는데 clearZero 필요 없는 더좋은 코드 있어서 그거씀 Line:20의 의미는 [0] , [0, 0] , [0, ... , 0] 등의 오직 원소가 0뿐이고 n개로 이루어진 String의 charAt(0)은 반드시 0인 특징을 활용하여 짜준거 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 import java.util.*; c..

220607 효율성 3,4 실패 (수정전)으로 돌릴 시 시간복잡도 n^2 (수정후)으로 돌릴 시 시간복잡도 nlogn 효율성 3,4번 실패함 O(n^2)으로 풀어서 그런듯 O(n)으로 해결이 되는데 정렬 후에(사전 순으로) 앞뒤 문자만 체크해줘도 해결이 되는 방식이 뭔가 신기했다.. (수정 전) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 import java.util.*; class Solution { public boolean solution(String[] phone_book) { boolean answer = true; for(int i=0; i

220606 실수 1. 오름차순을 내림차순으로 착각 2. Line:48~50 nr = makeRow(nr, nDir); nc = makeCol(nc, nDir); nDir = makeDir(nr, nc, nDir); 이 부분을 nr = makeRow(nr, dir); nc = makeCol(nc, dir); nDir = makeDir(nr, nc, dir); 이렇게 실수함.. 하 ㅠ 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64..

처음에는 Map으로 했는데 (Line:24의 중복된 원소를 Map.getOrDefault(..)로 했음) Set.add( )의 리턴값이 boolean형이라는 것을 다른 분 코드보고 알게 됐다 Map -> Set으로 바꾸니까 깔끔하기는한데 Map의 속도는 O(1)인데 Set.add()하면서 중복인지 아닌지 판별하는 속도가 O(1)보다는 클 것이라고 생각한다 둘다 HashFuncion을 사용하는 자료구조였음.. Set의 탐색은 O(1)/저장 O(1) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 import java.util.*; class Solution { public int[] solution(..

220605 시간복잡도가 초과했었는데 기본으로 주어지는 연산자 3개 +,*,- 만으로 조합을 구성해야하는데 문제의 예시의 ex)100-234+234243-345*... 등의 연산자 n개의 배열을 활용하여 조합을 구성했음(실수한 부분) 1. 주어진 String인 expression을 parsing하여 numList와 signList를 구하기 2. numList.size()값은 signList.size()보다 1크다 3. + - *의 순열을 구한 후에 answer의 후보값을 구하는 식을 짠다. 4. 원본 numList와 signList가 훼손되지 않게 (remove를 사용할 것이므로) 다른 list객체에 값을 복사한다. import java.util.*; class Solution { private stat..

DFS인데 재귀로 안풀고 그냥 체크하는 방식으로 했음 조건절중 if문 가장 마지막 1칸 아래, 1칸 왼쪽을 체크 안해줘서 테케 3개인가 틀림 어떠한 자리 P를 기준으로 맨해튼 거리가 2이하인 점은 아래 그림과 같은데 DFS로 처리하면 아래 점들을 모두 체크하지만 점 P를 기준으로 대칭되어 있는 점은 체크할 필요가 없기 때문에 수행시간을 반으로 줄일 수 있음 근데 파란 부분 점들만 체크하고 빨간점 중 둘 중 1개를 체크해줘야 맨해튼 거리가 2이하인 점들을 모두 체크할 수 있는 건데 저 빨간 부분을 체크안해줘서 틀림.. class Solution { public int[] solution(String[][] places) { int[] answer = new int[5]; for(int i=0; i

하.. map에 부분집합 저장할 때 누적이 안되고 자꾸 1로 갱신된다.. getOrDefault 썼는데도 이러네 이유 찾았다 또 스펠링임 이거 프로그래머스 ide가 이상한게 컴파일 에러를 제대로 못찾는 것 같음 Line:60~61번 subsetMap.put(subset, subsetMap.getOrDefault(subsetMap, 0)+1); -> subsetMap.put(subset, subsetMap.getOrDefault(subset, 0)+1); 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 5..