월 15,400원
5개월 할부 시다른 수강생들이 자주 물어보는 질문이 궁금하신가요?
- 미해결자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비
탐색문제
- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요! - 먼저 유사한 질문이 있었는지 검색해보세요. - 서로 예의를 지키며 존중하는 문화를 만들어가요. - 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요. 안녕하세요 탐색문제를 공부하고싶은데탐색문제라고 하면 몇 몇 섹션이 해당하는지 알 수 있을까요?
- 미해결자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비
comparable관련 질문입니다.
안녕하세요.씨름선수 문제를 풀다가 궁금한 점이 생겨 글남깁니다. comparable 을 구현하여 compareTo를 정의할 때 선행원소 - 후행 원소 가 음수이면 자리를 바꾸지 않고, 양수이면 자리를 바꾸는 것으로 알고 있습니다.문제 코드를 예시로 들어서 return this.h - o.h 라면 선행원소가 this.h 이고 후행원소가 o.h 라는 것은 어떻게 알 수 있나요? 물론 외우면 되긴 하지만 원리가 궁금합니다. 두서 없는 글 읽어주셔서 감사합니다.
- 미해결자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비
코드 확인 부탁드립니다 ㅠ
import java.util.*; public class Main { public static void main(String[] args){ Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int[][] arr = new int[n][n]; for(int i = 0; i < n; i++) { for(int j = 0; j < n; j++) { arr[i][j] = sc.nextInt(); } } int m = sc.nextInt(); int[] moves = new int[m]; for(int i = 0; i < m; i++){ moves[i] = sc.nextInt(); } ArrayList<Stack<Integer>> board = new ArrayList<>(); for(int i = 0; i < n; i++) { Stack<Integer> temp = new Stack<>(); for(int j = 0; j < n; j++) { if(arr[n-1-j][i] == 0) break; temp.push(arr[n-1-j][i]); } board.add(temp); } Stack<Integer> basket = new Stack<>(); int result = 0; for(int i = 0; i < m; i++) { int num = moves[i]-1; Stack<Integer> stack = board.get(num); if(stack.empty()) continue; int popNum = stack.pop(); if(!basket.isEmpty() && basket.peek() == popNum) { basket.pop(); result += 2; } else { basket.push(popNum); } } System.out.print(result); } }어느 부분에서 틀린지 모르겠습니다. 확인 해주시면 감사하겠습니다.ㅠㅠ
- 미해결자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비
아나그램 문제 런타임에러
안녕하세요 강사님. 해쉬맵 아나그램문제 런타임에러가 나서 채점이 되지않은데 왜 그런지 모르겠습니다.. import java.util.HashMap; import java.util.Scanner; public class Main { public String solution( String str1, String str2){ String answer = "YES"; HashMap<Character,Integer> str1map = new HashMap<>(); //문자열을 순회하며 알파벳을 개수를 세기 for(char key: str1.toCharArray()){ str1map.put(key,str1map.getOrDefault(key,0)+1); } //문자열을 순회하며 map에서 count 하나씩 제거 for(char key: str2.toCharArray()){ //str1에 있는 문자열이 str2에는 없거나 갯수가 0인경우 아나그램이 아님 if(!str1map.containsKey(key) || str1map.get(key) == 0) answer = "NO"; str1map.put(key,str1map.get(key)-1); } return answer; } public static void main (String[]args){ Main main = new Main(); Scanner sc = new Scanner(System.in); String str1 = sc.next(); String str2 = sc.next(); System.out.print(main.solution(str1, str2)); } }
- 미해결자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비
왜 시간초과가 나는지 모르겠습니다.
import java.util.HashMap; import java.util.Map; import java.util.Scanner; public class 매출액의_종류 { public static void main(String[] args) { Scanner scan = new Scanner(System.in); int n = scan.nextInt(); int k = scan.nextInt(); int[] arr = new int[n]; for(int i=0;i<n;i++){ arr[i] = scan.nextInt(); } System.out.println(mySol(n,k,arr)); } private static String mySol(int n, int k, int[] arr) { String result = ""; Map<Integer,Integer> map = new HashMap<>(); for(int i=0;i<k-1;i++){ map.put(arr[i],map.getOrDefault(arr[i],0) + 1); } int lt = 0; for(int rt=k-1;rt<n;rt++){ map.put(arr[rt],map.getOrDefault(arr[rt],0) + 1); result += map.size() + " "; map.put(arr[lt], map.get(arr[lt]) - 1); if(map.get(arr[lt]) == 0) map.remove(arr[lt]); lt++; } return result; } }
- 미해결자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비
똑같이 작성하고 실행하는데 런타임에러가 발생해요
import java.util.*; class Main { static String answer = "NO"; static int n, total = 0; boolean flag = false; public void dfs(int L, int sum, int[] arr) { if(flag) return; if(sum > total/2) return; if(L == n){ if(total/2 == sum){ answer = "YES"; flag = true; } }else{ dfs(L + 1, sum + arr[L], arr); dfs(L + 1, sum, arr); } } public void main(String[] args) { Main T = new Main(); Scanner sc = new Scanner(System.in); n = sc.nextInt(); int[] arr = new int[n]; for(int i = 0; i < n; i++){ arr[i] = sc.nextInt(); total += arr[i]; } T.dfs(0, 0, arr); System.out.println(answer); } }복습 차원에서 똑같이 코드를 실행하는데 런타임에러가 자꾸 발생하는 이유를 모르겠습니다.
- 미해결자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비
시간복잡도가O(N^2)이라고 생각 되서 시간이 초과될거같은데 오류가 안나서 궁금합니다.
- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요! - 먼저 유사한 질문이 있었는지 검색해보세요. - 서로 예의를 지키며 존중하는 문화를 만들어가요. - 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요.import java.util.Arrays; import java.util.Scanner; public class lecture27 { public static void main(String[] args) { Scanner scanner=new Scanner(System.in); int n=scanner.nextInt(); int m=scanner.nextInt(); int []arr=new int[n]; for (int i = 0; i <n ; i++) { arr[i]=scanner.nextInt(); } int count=0; for (int i = 0; i <n ; i++) { int sum=arr[i]; for (int j = i+1; j <n ; j++) { sum=sum+arr[j]; if(sum==m) { count++; } else if(sum>=m) { break; } } } System.out.println(count); } }이 코드로 정답입니다는 받았는데 , 제 생각에는 O(n^2)이라 시간 초과가 나야할것 같은데 이중 for문이니까 시간 초과가 나지 않아서 어떤 부분에서 잘못 생각한건지 궁금합니다.
- 미해결자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비
11. 임시반장 정하기
59 8 7 6 55 6 7 8 91 2 3 7 84 5 3 4 26 2 8 4 2 이예제의 답이 왜 3번학생인가요 4번학생이이 제일 많이 겹치는거 아닌가요?
- 미해결자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비
HashMap에서 map.KeySet() 정렬관련 질문있습니다.
입력 순서가 BACDE 이면 HashMap을 배열로 생각하였을 때, 순서대로 저장된다면 KeySet()의 배열은 [B, A, C, D, E]가 되는게 맞지 않나요? for(char x : keySet())의 출력 값이 ABCDE로 나오는 것을 보면 별다른 sort과정 없이 HashMap에서 Key 값을 정렬해서 출력해주는 것으로 보입니다. HashMap에 존재하는 Key값들이 자동적으로 정렬이 되고 있다고 봐도 될까요?
- 미해결자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비
TimeLimit 문의 드립니다
로직은 다르지만 의미는 강의와 비슷하게 구현한듯 한데 타임리밋이 발생하여 문의 드립니다. 어떤 부분이 잘못된 걸까요?public class 송아지찾기 { int count = 0; boolean visited[] = new boolean[10001]; public int BFS(int s ,int e) { Queue<Integer> queue = new LinkedList<>(); queue.add(s); while (!queue.isEmpty()) { int size = queue.size(); for (int i = 0; i < size; i++) { Integer poll = queue.poll(); visited[poll] = true; if (poll + 1 < 1000 && !visited[poll + 1]) { if (poll + 1 == e) { return count + 1; } queue.add(poll + 1); } if (poll + 5 < 10000 && !visited[poll + 5]) { if (poll + 5 == e) { return count + 1; } queue.add(poll + 5); } if (poll - 1 > -1 && !visited[poll - 1]) { if (poll -1 == e) { return count + 1; } queue.add(poll - 1); } } count++; } return count; }
- 미해결자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비
트리 레벨 체크로는 안되는건가요??
예전 BFS 영상에서 최단 경로 길이를 구하기 위해서는 트리 레벨 체크를 활용하는 것을 보고 이번에도 큐 사이즈 만큼 반복을 돌아서 트리 레벨을 체크 하는 방식으로 구현하였는데프로그램에선 12로 잘 나오지만, 채점에선 오류가 떠서 이 방식으론 안되는지 궁금합니다.. 또, 강의를 들으면서 배열에 +1씩 추가하는 아이디어를 보고 기존의 배열에서 +1씩 해주어 수정한 결과는 통과하였는데, DIS배열을 하나 더 만든 이유도 궁금합니다! 추가로 젤 윗 이야기인 큐 사이즈 만큼 반복하여 레벨을 체크하는 상황과 배열에 +1씩 하여 넓혀가는 상황의 구별을 어떻게 할 수 있을지도 궁금해졌습니다... 감사합니다 import java.awt.*; import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; public class In_8_11 { static int[][] matrix = new int[8][8]; static int[] dx = {-1, 0, 1, 0}; static int[] dy = {0, 1, 0, -1}; static int level; public static int BFS(int x, int y) { Queue<Point> Q = new LinkedList<>(); // 가장 처음 큐에 넣기 Q.offer(new Point(x,y)); matrix[1][1] = 1; // 출발지점 꼭 걸어줘야함. // 시작 while( !Q.isEmpty()){ for (int j = 0; j < Q.size(); j++) { Point P = Q.poll(); System.out.println("( "+P.x + " , " + P.y+" )"); if (P.x == 7 && P.y == 7){ //return matrix[7][7] -1; return level; } for (int i = 0; i < 4; i++) { int nx = P.x + dx[i]; int ny = P.y + dy[i]; if (1 <= nx && nx <= 7 && 1 <= ny && ny <= 7) { if (matrix[nx][ny] == 0) { matrix[nx][ny] = 1; //matrix[nx][ny] = matrix[P.x][P.y] +1; // 뺄 필요 없을 거 같은데? Q.offer(new Point(nx, ny)); } } } }level++; } return -1; } public static void main(String args[]) { Scanner sc = new Scanner(System.in); for(int i = 1; i <= 7; i++){ for(int j = 1; j <= 7; j++) { matrix[i][j] = sc.nextInt(); } } System.out.println( BFS(1, 1) ); } }
- 미해결자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비
아나그램 사이즈 관련 질문입니다.
만약 아나그램 b 가 bbb 라면?해쉬맵의 사이즈가 0이 되서 아나그램 비교자체가 안되지 않을까라는.. 의문이 들어서 질문드립니다 ~
- 미해결자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비
ch 배열의 값을 확인해서 더 이상 반복문이 돌지 않도록 하는 것도 유효한가요?
private static int solution(int v, int cost) { int answer = 0; Queue<Edge> pq = new PriorityQueue<>(); pq.offer(new Edge(v, cost)); while (!pq.isEmpty()) { if (successTree()) { // 모든 노드가 트리에 추가되었을 때는 반복문을 더이상 돌지않는다. break; } Edge cur = pq.poll(); if (ch[cur.v]) { continue; } ch[cur.v] = true; answer += cur.cost; for (Edge edge : graph.get(cur.v)) { if (!ch[edge.v]) { pq.offer(edge); } } } return answer; } private static boolean successTree() { for (boolean check : ch) { if (!check) { return false; // 아직 연결 안 된 노드가 있다면 false를 return } } return true; // 이미 트리가 다 완성되었다면 true를 return } 이렇게 pq를 도는 반복문에 successTree라는 메소드를 추가하여 모든 노드가(=도시) 트리에 포함되었다면 바로 true를 return 시켜 pq에 대한 반복문이 돌지 않도록 수정했습니다.이게 코드 수행 시간에 더 효율적인 방법인지 강사님의 의견이 궁금하여 질문해봅니다!저는 마지막 노드까지 트에 추가되었어도 pq에 남아있는 값들이 있어 의미없는 로직을 돌 것이라고 생각해 추가하게 되었습니다만 ch 배열을 탐색하는 데에 걸리는 시간이 더 걸려 해당 로직을 수행하는 것이 더 비효율적인지 궁금합니다.또한, 이미 노드가 다 들어가있다면 그 뒤에 pq가 반복할 일이 없어 해당 메소드가 의미가 있는지 없는지 궁금합니다. 이전에 pq에 남아있는 노드들이 poll()될 수 있다고 생각했거든요..// 항상 강의 잘 보고있습니다. 감사합니다.
- 미해결자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비
소수 뒤집기 문제 다른 방식으로 풀기
복잡하게 푼 것 같기는 한데, 혹시 어떻게 수정하면 정답이 될까요?인풋, 아웃풋은 잘 나오는데 채점 사이트에서는 오답이라고 뜹니다. import java.lang.reflect.Array; import java.util.ArrayList; import java.util.Arrays; import java.util.Scanner; class Main { public String solution(int n, int[] intArr){ String answer = " "; int[] intPrimeArray= new int[n]; for(int i=0; i<n; i++){ int indexInt= intArr[i]; int remain; int reverse=0; while(indexInt > 0){ remain= indexInt%10; reverse= reverse*10 + remain; indexInt = indexInt/10; } intPrimeArray[i] = reverse; int flag= 0; if(intPrimeArray[i]==1) flag=1; for(int j=2; j<intPrimeArray[i]; j++){ if(intPrimeArray[i] % j ==0 ) flag=1; } if(flag==0) answer += intPrimeArray[i] + " "; } return answer; } public static void main(String[] args) { Main T = new Main(); Scanner sc= new Scanner(System.in); int n = sc.nextInt(); int[] intArr = new int[n]; for(int i=0; i<n; i++){ intArr[i]= sc.nextInt(); } System.out.println(T.solution(n, intArr)); } }
- 미해결자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비
Array 12) 멘토링 문제 짝 클래스 객체와 Map을 활용하는 풀이방식
public class Main{ public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int m = sc.nextInt(); int[][] arr = new int[m][n]; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { arr[i][j] = sc.nextInt(); } } System.out.println(answer(n, m, arr)); } static class Pair { int mento; int menti; @Override public boolean equals(Object o) { if (this == o) return true; if (!(o instanceof Pair)) return false; Pair pair = (Pair) o; return mento == pair.mento && menti == pair.menti; } @Override public int hashCode() { return Objects.hash(mento, menti); } } private static int refactor(int n, int m, int[][] arr) { Map<Pair, Integer> map = new HashMap<>(); for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { for (int k = j+1; k < n; k++) { Pair pair = new Pair(); pair.mento = arr[i][j]; pair.menti = arr[i][k]; map.put(pair, map.getOrDefault(pair, 1) + 1); } } } return (int) map.entrySet().stream().filter(entry -> entry.getValue() == m).count();; } }저는 위와 같이 짝에 부합하는 값들을 클래스를 통해 객체에 짝을 저장하고, 각 시험별 동일한 짝(객체)에 대한 중복을 제거함과 동시에 count값을 증가시키며 Map에 저장하는 방식으로 문제를 풀었습니다.
- 미해결자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비
격자판 최대합 테스트케이스 문제 있습니다.
반대 누적합에 대한 테스트케이스 예외가 없는거 같아요.public static void main(String[] args) { Scanner sc = new Scanner(System.in); int length = sc.nextInt(); int[][] intArr = new int[length][length]; for (int i = 0; i < length; i++) { for (int j = 0; j < length; j++) { intArr[i][j] = sc.nextInt(); } } System.out.println(answer(length, intArr)); } private static int answer(int length, int[][] intArr) { /* 대각선 누적합, 최대값 */ int xXSum = 0, xYSum = 0, max = 0; for (int i = 0; i < length; i++) { /* 행, 열 누적합 */ int rowSum = 0, colSum = 0; for (int j = 0; j < length; j++) { /* 각 행의 누적합 저장*/ rowSum += intArr[i][j]; /* 각 열의 누적합 저장*/ colSum += intArr[j][i]; } if (rowSum > max) max = rowSum; if (colSum > max) max = colSum; /* 대각선의 누적 합 저장*/ xXSum += intArr[i][i]; xYSum += intArr[length-1-i][length-1-i]; } /* 대각선 의 합 추가*/ if (xXSum > max) max = xXSum; if (xYSum > max) max = xYSum; return max; } }반대 대각선을 코드는 위 코드에서 바로 아래와 같습니다.xYSum += intArr[length-1-i][length-1-i];위에가 잘못 적용한 코드이고 (바로 위의 정대각선과 똑같은 작업을 하는것과 마찬가지입니다.)이것을 코딩채점사이트 상에 직접 돌려보면 정답으로 인정되지만 31 1 31 3 13 1 1이렇게 데이터 직접 넣어보면 9가 아닌 5가 최대값으로 출력됩니다.즉, 코딩채점에 반대 대각선에 대한 테스트케이스가 없다는 소리에요.xYSum += intArr[i][length-1-i];위 코드가 정답이고, 이렇게 했을때에는 처리가 되긴 되는데아무튼 현재 테스트케이스 상에 반대 대각선에 대한 누적합이 더 큰 경우가 없어서 처리가 안되고있습니다.그냥 반대 대각선 누적합 자체가 없는셈 치는거나 마찬가지에요
- 미해결자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비
replaceAll, subString
안녕하세요 강사님, 강의 잘 듣고 있습니다. 지난 시간에 배운 replaceAll, subString로 풀어봤고 코드를 입력하면 정답이 잘 나오는데, 채점 사이트에서는 오답이라고 떠서요. 왜 그런지 설명해주실 수 있으실까요? 감사합니다~ import java.util.Arrays; import java.util.Scanner; class Main { public String solution(String str){ String answer= ""; str= str.replaceAll("[^\\d]+",""); for(int i=0; i<str.length(); i++){ if(str.charAt(i) == '0'){ answer = str.substring(i+1); } else return answer; } return answer; } public static void main(String[] args) { Main T = new Main(); Scanner sc= new Scanner(System.in); String str= sc.nextLine(); System.out.println(T.solution(str)); } }
- 미해결자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비
공통원소구하기 시간초과관련
import java.util.*; public class Main { public List<Integer> solution(int n, int m, int[] x, int[] y) { List<Integer> answer = new ArrayList<>(); Map<Integer, Boolean> map = new HashMap<>(); for (int i = 0; i < n; i++) { map.put(x[i], true); } for (int i = 0; i < m; i++) { if (map.containsKey(y[i])) { answer.add(y[i]); } } //오름차순 정렬 Collections.sort(answer); return answer; } public static void main(String[] args) { Main t = new Main(); Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int[] x = new int[n]; for(int i = 0; i < n; i++){ x[i] = sc.nextInt(); } int m = sc.nextInt(); int[] y = new int[m]; for(int i = 0; i < m; i++){ y[i] = sc.nextInt(); } for(Integer i : t.solution(n,m,x,y)){ System.out.print(i+" "); } } }시간복잡도 신경 쓰다가 HashMap을 사용 해봤는데 그래도 아슬하게 세이프 인 것 같습니다... 혹시 제일 좋은 방법은 없을까요?
- 미해결자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비
강의와는 다르게 해봤습니다.
import java.util.Scanner; public class Main { public String solutions(int target, int[] high) { String answer = ""; for (int i = 0; i < target; i++) { if (answer.isEmpty()) { answer += high[i]+" "; } else if (high[i]>high[i-1]) { answer += high[i]+" "; } } return answer; } public static void main(String[] args) { Main t = new Main(); Scanner sc = new Scanner(System.in); int target = sc.nextInt(); int[] high = new int[target]; for (int i = 0; i < target; i++) { high[i] = sc.nextInt(); } System.out.println(t.solutions(target, high)); } }강의 보기전에 혼자 이렇게 해봤는데 채점 정답처리는 받았습니다. 혹시 문제가 없을까요?
- 미해결자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비
12번 멘토링 질문입니다!
안녕하세요, 12번 멘토링 문제 풀다가 첫 번째 채점 결과 값이 3으로 잘 나왔습니다. 그런데 그 다음 입력부터는 전부 오답이 나오는 상황인데, 어떤 부분에서 틀린 건지 알려주시면 감사하겠습니다 ㅠㅠ // package = " "; import java.io.*; import java.util.*; class Main { public int Solution(int n, int m, int arr[][]){ String mathMark = ""; ArrayList<Integer> ans = new ArrayList<>(); HashMap<String, Integer> countMap = new HashMap<>(); for(int i = 0; i < n; i++){ // 첫째부터 계속 다음 줄 내려가서 검사 for(int j = 0; j < m; j++){ // for(int k = 0; k < m; k++){ // System.out.println("j값 : "+j+", "+"k값 : "+k); if(j != k && j < k){ // System.out.println(arr[i][j]+", "+arr[i][k]); if(i == n-1 && j == m-1 && k == m-1){ mathMark += arr[i][j]+""+arr[i][k]; } else{ mathMark += arr[i][j]+""+arr[i][k]+" "; } } } } } /* m개 값을 가지고 있는 수 찾기 */ String numArray[] = mathMark.split(" "); // 숫자 등장 횟수 카운트 for(int i = 0; i < numArray.length; i++){ countMap.put(numArray[i],countMap.getOrDefault(numArray[i],0) + 1); } // 등장 횟수가 3 이상인 숫자 Count for(Map.Entry<String, Integer> entry : countMap.entrySet()){ System.out.println(entry.getKey()+" "+entry.getValue()); if(entry.getValue() == n){ ans.add(1); } } return ans.size(); } public static void main(String[] args) throws Exception{ Main m = new Main(); BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String[] numStr = br.readLine().split(" "); // 1. N과 M 입력받기 int column = Integer.parseInt(numStr[0]); int raw = Integer.parseInt(numStr[1]); int arr[][] = new int[raw][column]; for(int i = 0; i < raw; i++){ String[] test = br.readLine().split(" "); for(int j = 0; j < column; j++){ arr[i][j] = Integer.parseInt(test[j]); } } System.out.println(m.Solution(raw, column, arr)); br.close(); } }