월 17,600원
5개월 할부 시다른 수강생들이 자주 물어보는 질문이 궁금하신가요?
- 미해결자바 코딩테스트 - it 대기업 유제
최대 길이 연속수열 질문
정답의 경우 아래와 같이 되어있습니다.public int solution(int[] nums){ int answer = 0; HashSet<Integer> set = new HashSet<>(); for(int x : nums) set.add(x); for(int x : set){ if(set.contains(x - 1)) continue; int cnt = 0; while(set.contains(x)){ cnt++; x++; } answer = Math.max(answer, cnt); } return answer; }제가 푼 방식 : set으로 중복되지 않은수만 우선순위 큐(pQ)에 넣어 계산.물론 풀이에서의 코드가 간결하고 사용하는 자료형도 적으니 좋은 코드같습니다만은 이렇게 풀었을때 시간 복잡도 면에서도 많이 불리한지 피드백 부탁드립니다. public int solution(int[] nums){ int answer = 1 , cnt=1; PriorityQueue<Integer> pQ= new PriorityQueue<>(); HashSet<Integer> set = new HashSet<>(); for(int i : nums){ if(!set.contains(i)) pQ.offer(i);// set.add(i); } int N = pQ.poll(); while ( !pQ.isEmpty() ){ int nextN = pQ.poll(); if( N+1 == nextN ){ cnt++; N = nextN; } else if( N+1 != nextN ) { cnt = 1; N = nextN; } answer=Math.max(answer,cnt); } return answer; }
- 미해결자바 코딩테스트 - it 대기업 유제
잃어버린 강아지 문제 count 관련 질문있습니다
안녕하세요 강사님 강의 잘 듣고 있습니다!잃어버린 강아지 문제에서 count관련 이해가 안되는 부분이 있어서요. 관련 부분만 가져왔는데 count는 처음에 0으로 초기화 된 상태에서 while문에 들어가자마자 1이 증가하고, 마지막으로 들어갈 때는 9999상태에서 들어가서 10000이 되고, 그시점에 마지막 번째 while을 실행하면서 현수가 강아지를 찾아서 x1 == x2 && y1 == y2이 된 후 break(사실상 while문이 끝나서 break된거나 마찬가지지만)될수도 있는건데 강아지를 못찾고 반환하는 0을 리턴하는 조건이 count >= 10000이 되면 10000번째에 찾더라도 못찾은걸로 표현될수 있지 않나 싶어서요.그런데 이런 생각을 하다보니까 그러면 진짜로 10000을 넘을때까지 못찾는 경우는 어떻게 알수 있게 되지? 라는 생각이 들면서 정리가 안되기 시작했습니다. ㅠㅠ count가 while안에 있기 때문에 10000번째에 딱 찾고 끝나고 나면 더이상 count를 올려줄 방법이 없는데, 어떻게 해야 만번 이상을 했고 그래도 찾을수 없었던걸 증명할수 있을지...일단 생각으로는 while을 true로 해놓고 break하는 조건을 하나 더 둬서 if(x1 == x2 && y1 == y2) break; 아래에 if(count == 10000) break;나 if(count >= 10000) break; 이렇게 하는 방법이 떠오르긴 하는데 이렇게 해도 괜찮을지, 강사님이 해주신 코드로 충분한데 제가 이해를 못하고 있는것일지.. 설명 늘 자세히 해주시는데도 질문해서 죄송합니다🥲 항상 감사합니다int d1 = 0, d2 = 0, count = 0; while (count < 10000) { count++; int nx1 = x1 + dx[d1]; int ny1 = y1 + dy[d1]; int nx2 = x2 + dx[d2]; int ny2 = y2 + dy[d2]; boolean flag1 = true, flag2 = true; if (nx1 < 0 || nx1 >= n || ny1 < 0 || ny1 >= n || board[nx1][ny1] == 1){ d1 = (d1 + 1) % 4; flag1 = false; } if (nx2 < 0 || nx2 >= n || ny2 < 0 || ny2 >= n || board[nx2][ny2] == 1){ d2 = (d2 + 1) % 4; flag2 = false; } if(flag1 == true){ x1 = nx1; y1 = ny1; } if(flag2 == true){ x2 = nx2; y2 = ny2; } if(x1 == x2 && y1 == y2) break; } if (count >= 10000) return 0;
- 미해결자바 코딩테스트 - it 대기업 유제
바둑대회 질문입니당
안녕하세요! 강의 잘 듣고있습니다! 바둑대회 문제 관련해서 제가 풀어낸 방식은 흑돌팀과 백돌팀 각각 인원을 세어주는 배열과 팀능력치를 계산하는 배열 두 개를 선언하고, 깊이가 다 다랐을 때 정답을 계속해서 초기화하는 방식을 사용했습니다. 예제 코드에서는 문제가 따로 생기진 않았는데 혹시 이런 방식의 풀이도 다른 문제를 접근하는게 큰 문제가 없을지 그리고 다른 입력에도 문제가 없을지 궁금합니다.package DFS; package DFS; import java.util.*; public class 바둑대회 { } class Solution6 { static int[] sum; static int[] teamCount; static int[][] cansArr; static int minNumber; static ArrayList<Integer>[] list; public static int solution(int[][] cans){ int answer; sum = new int[2]; teamCount = new int[2]; cansArr = cans; minNumber = Integer.MAX_VALUE; list = new ArrayList[2]; for (int i = 0; i < list.length; i++) { list[i] = new ArrayList<>(); } DFS(0); answer = minNumber; return answer; } public static void DFS(int lv){ if(lv == cansArr.length){ if(Math.abs(sum[0] - sum[1]) < minNumber){ minNumber = Math.abs(sum[0] - sum[1]); } return; } for (int i = 0; i < 2; i++){ if( teamCount[i] < cansArr.length/2 ){ sum[i] += cansArr[lv][i]; teamCount[i]++; DFS(lv+1); sum[i] -= cansArr[lv][i]; teamCount[i]--; } } } public static void main(String[] args){ Solution6 T = new Solution6(); System.out.println(T.solution(new int[][]{{87, 84}, {66, 78}, {94, 94}, {93, 87}, {72, 92}, {78, 63}})); System.out.println(T.solution(new int[][]{{10, 20}, {15, 25}, {35, 23}, {55, 20}})); System.out.println(T.solution(new int[][]{{11, 27}, {16, 21}, {35, 21}, {52, 21}, {25, 33},{25, 32}, {37, 59}, {33, 47}})); } }
- 미해결자바 코딩테스트 - it 대기업 유제
5. "최대 길이 바이토닉 수열" 에서 설명해주신 방법과 제가 직접 구현한 방법이 달라, 확인 한번 부탁드립니다
안녕하세요 수업 강의를 보다가, 풀어주신 방법이 저와 다르고 for 문 하나만으로 해결이 가능하지 않나 싶어서 확인차 질문 드려봅니다.pdf 상의 정답은 모두 맞춘 상태입니다. 간단하게 하라도 피드백 주신다면 감사합니다class Solution5 { public static int solution(int[] nums){ // answer : 정답 // len : 현재 수열 길이 // d : 현재 수열의 방향 ( 0: 증가, 1: 감소) // prevNum : 이전 숫자 int answer = 0, len = 0, d = 0, prevNum = Integer.MIN_VALUE; for (int num : nums) { if (d == 0) { // 1. 현재 수열이 증가하고 있는 상황 // 2. 수열이 증가하고 있는 상황에서의 시뮬레이션 if (prevNum > num) { // 이전 숫자보다 작을 경우, 수열의 방향을 감소로 변경 d = -1; } else if (prevNum == num) { // 이전 숫자와 값이 같을 경우, 바이토닉 수열이 아니므로 길이 초기화 len = 0; } // 길이 증가 len++; } else { // 1. 현재 수열이 감소하고 있는 상황 // 2. 수열이 감소하고 있는 상황에서의 시뮬레이션 if (prevNum > num) { // 2-1. 이전 숫자보다 작을 경우, 길이 증가 len++; } else { // 2-2. 이전 숫자보다 크거나, 같을 경우 수열이 끝났다고 판단 // 2-2-1. 현재까지의 길이를 계산하여 더 길면 정답으로 변경 if (answer < len) { answer = len; } // 2-2-2. 초기화 len = 1; // 현재 숫자부터 다시 시작하므로 값은 1 d = 0; // 2-2-3. 현재 숫자 이전의 값을 비교했을 때, 증가하고 있었다면 길이 하나 증가 if (prevNum < num) { len++; } } } prevNum = num; } // 현재 진행중이던 수열이 감소하고 있고 길이가 정답보다 크다면, 정답으로 변경 if (answer < len && d == -1) { answer = len; } return answer; } public static void main(String[] args){ Solution5 T = new Solution5(); System.out.println(Solution5.solution(new int[]{1, 2, 1, 2, 3, 2, 1})); System.out.println(Solution5.solution(new int[]{1, 1, 2, 3, 5, 7, 4, 3, 1, 2})); System.out.println(Solution5.solution(new int[]{3, 2, 1, 3, 2, 4, 6, 7, 3, 1})); System.out.println(Solution5.solution(new int[]{1, 3, 1, 2, 1, 5, 3, 2, 1, 1})); } }
- 미해결자바 코딩테스트 - it 대기업 유제
알파코드 풀이질문입니다
전문제 "ip주소"와 비슷하게 해결하였는데 이렇게 풀면 시간초과가 발생할까요?class Solution { static int n, answer; static void dfs(int L, String s) { if (L == n) { answer++; } else { for (int i = L; i < n; i++) { String temp = s.substring(L, i + 1); if (check(temp)) { dfs(i + 1, s); } else{ break; } } } } static boolean check(String str) { if (str.charAt(0) == '0') { return false; } int num = Integer.parseInt(str); return num >= 1 && num <= 26; } public int solution(String s) { answer = 0; n = s.length(); dfs(0, s); return answer; } public static void main(String[] args) { Solution T = new Solution(); System.out.println(T.solution("25114")); System.out.println(T.solution("23251232")); System.out.println(T.solution("21020132")); System.out.println(T.solution("21350")); System.out.println(T.solution("120225")); System.out.println(T.solution("232012521")); } }
- 미해결자바 코딩테스트 - it 대기업 유제
7번 비밀 번호 문제에 시간복잡도가 궁금합니다!
안녕하세요! 선생님 덕분에 매일 알고리즘 푸는 법을 재밌게 배우고 있습니다 🙂문제의 제한 사항에 "password의 길이는 200,000을 넘지 않습니다." 라서 효율성을 생각하고 풀어야 된다고 하셨는데, 인접한 숫자를 찾는 과정에서 삼중 for문을 사용하는 것이 괜찮은지 궁금합니다!
- 해결됨자바 코딩테스트 - it 대기업 유제
혹시 이렇게 작성해도 괜찮나요?
코딩테스트 공부하면서 항상 궁금했는데..강의 내용을 보면 클래스나 함수는 꼭 필요한 부분에서만 사용하시는 것 같더라구요..아래처럼 써도 되나요? 면접관님들은 어떻게 생각하실지 궁금합니다. public static int[] run(int[] nums) { return Arrays.stream(nums) .mapToObj(MyNumber::new) .peek(user -> user.one = Integer.bitCount(user.value)) .sorted(Comparator.comparingInt(MyNumber::one)) .mapToInt(MyNumber::value) .toArray(); } public static class MyNumber { final int value; int one; MyNumber(int value) { this.value = value; this.one = 0; } int value() { return value; } int one() { return one; } }
- 미해결자바 코딩테스트 - it 대기업 유제
문제풀이 확인 부탁드립니다.
package com.company.대기업유제.그래프; import java.util.*; class 교육과정 { public String[] solution(String[] subjects, String[] course){ String[] answer = {}; /** * n개의 교육과정 수료해야함 * 교육과목에는 선수과목이 있다. * 선수과목 관련해서는 위상정렬을 사용한다. * n개의 과목을 모두 이수할수있는 순서를 배열에 담아 반환 * (답이 여러개면 그 중 아무거나 반환) 위상정렬의 특징 * subjects : n개의 과목 목록 * course : 선수과목 정보 * */ //먼저 선수과목을 구분하기 위해 노드들을 생성 Map<String, Node> nodes = createNodes(subjects, course); //후위순회로 탐색 LinkedList<String> result = new LinkedList(); Set<Node> discovered = new HashSet<>(); for (var entry : nodes.entrySet()) { if(!discovered.contains(entry.getValue())){ DFS(entry.getValue(), result, discovered); } } return result.toArray(String[]::new); } private void DFS(Node node, LinkedList<String> result, Set<Node> discovered) { discovered.add(node); for (Node next : node.nexts) { if(!discovered.contains(next)){ DFS(next, result, discovered); } } result.addFirst(node.name); } private Map<String, Node> createNodes(String[] subjects, String[] course) { Map<String, Node> nodeMap = new HashMap<>(); for (String subject : subjects) { nodeMap.put(subject, new Node(subject)); } for (String s : course) { String[] split = s.split(" "); //선수과목 String parent = split[1]; // parent -> child String child = split[0]; Node parentNode = nodeMap.get(parent); Node childNode = nodeMap.get(child); parentNode.nexts.add(childNode); } return nodeMap; } class Node{ public Node(String name) { this.name = name; } final String name; Set<Node> nexts = new HashSet<>(); //하위 과목 } public static void main(String[] args){ 교육과정 T = new 교육과정(); System.out.println(Arrays.toString(T.solution(new String[]{"english", "math", "physics", "art", "music"}, new String[]{"art math", "physics art", "art music", "physics math", "english physics"}))); System.out.println(Arrays.toString(T.solution(new String[]{"art", "economics", "history", "chemistry"}, new String[]{"chemistry history", "economics history", "art economics"}))); System.out.println(Arrays.toString(T.solution(new String[]{"math", "science", "music", "biology"}, new String[]{"science music", "math music", "math science", "biology math"}))); } }
- 미해결자바 코딩테스트 - it 대기업 유제
혼자서 푼 문제 확인 부탁드립니다.
package com.company.대기업유제.그래프; import java.util.HashMap; import java.util.Map; import java.util.PriorityQueue; class 공굴리기 { public int solution(int[][] board, int[] s, int[] e) { /** * n * m 격자판 * 0은 빈공간 1은 벽 * * 공은 격자의 상하 좌우 네방향으로 빈공간을 이동할수있음 벽을 만나면 멈춘다. * s 공의 위치 * e 공의 목표지점 * 목표위치까지 최단거리 ㄱ * 목표지점까지 도달못하면 -1 * * */ int[] dx = {-1, 0, 1, 0}; int[] dy = {0, -1, 0, 1}; PriorityQueue<Candidate> queue = new PriorityQueue<Candidate>(); Map<String, Integer> minPosMap = new HashMap<>(); Pos first = new Pos(s[1], s[0]); for (int i = 0; i < 4; i++) { queue.add(new Candidate(first, 0, i)); } while (!queue.isEmpty()) { int size = queue.size(); for (int i = 0; i < size; i++) { Candidate candi = queue.poll(); Pos poll = candi.pos; //벽을 만나지 않았으면 가던 방향으로 계속 이동 if(!candi.frontWall(board, dx, dy)){ Pos newPos = new Pos(candi.pos.x + dx[candi.direction], candi.pos.y + dy[candi.direction]); Candidate newCandi = new Candidate(newPos, candi.cnt + 1, candi.direction); Integer basePrice = minPosMap.getOrDefault(newPos.getName(), Integer.MAX_VALUE); if (basePrice < newCandi.cnt) continue; queue.add(newCandi); minPosMap.put(newPos.getName(), newCandi.cnt); }else{ //벽을 만나면 그때 방향 돌리기 //벽을 만났을때만 목표지점 체크하기 if (poll.x == e[1] && poll.y == e[0]) { // print(board); return minPosMap.getOrDefault(poll.getName(), Integer.MAX_VALUE); } for (int j = 0; j < 4; j++) { int moveX = dx[j] + poll.x; int moveY = dy[j] + poll.y; if (moveX < 0 || moveY < 0 || moveX >= board[0].length || moveY >= board.length) continue; // * 0은 빈공간 1은 벽 if(board[moveY][moveX] == 1) continue; Pos newPos = new Pos(moveX, moveY); Candidate newCandi = new Candidate(newPos, candi.cnt + 1, j); Integer basePrice = minPosMap.getOrDefault(newPos.getName(), Integer.MAX_VALUE); if (basePrice < newCandi.cnt) continue; queue.add(newCandi); minPosMap.put(newPos.getName(), newCandi.cnt); } } } } return -1; } public void print(int[][] board){ for (int i = 0; i < board.length; i++) { for (int j : board[i]) { System.out.print(j + " "); } System.out.println(); } } class Pos { int x; int y; public Pos(int x, int y) { this.x = x; this.y = y; } public String getName() { return x + "" + y; } } class Candidate implements Comparable<Candidate> { Pos pos; int cnt; int direction; public Candidate(Pos pos, int cnt, int direction) { this.pos = pos; this.cnt = cnt; this.direction = direction; } public boolean frontWall(int[][] board, int[] dx, int[] dy){ int moveX = dx[direction] + pos.x; int moveY = dy[direction] + pos.y; if (moveX < 0 || moveY < 0 || moveX >= board[0].length || moveY >= board.length) return true; // * 0은 빈공간 1은 벽 if(board[moveY][moveX] == 1) return true; return false; } @Override public int compareTo(Candidate o) { return this.cnt - o.cnt; } } public static void main(String[] args) { 공굴리기 T = new 공굴리기(); System.out.println(T.solution(new int[][]{{0, 0, 1, 0, 0, 0}, {0, 0, 1, 0, 0, 0}, {0, 0, 0, 0, 1, 0}, {1, 0, 1, 1, 1, 0}, {1, 0, 0, 0, 0, 0}}, new int[]{1, 0}, new int[]{4, 5})); System.out.println(T.solution(new int[][]{{0, 0, 1, 0, 0, 0}, {0, 0, 1, 0, 0, 0}, {0, 0, 0, 0, 1, 0}, {1, 0, 1, 1, 1, 0}, {1, 0, 0, 0, 0, 0}}, new int[]{0, 0}, new int[]{4, 2})); System.out.println(T.solution(new int[][]{{1, 0, 1, 0, 0}, {0, 0, 0, 0, 0}, {0, 0, 0, 1, 0}, {1, 1, 0, 1, 1}, {0, 0, 0, 0, 0}}, new int[]{0, 3}, new int[]{4, 2})); System.out.println(T.solution(new int[][]{{0, 1, 0, 1, 0, 0}, {0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 1, 0}, {0, 1, 1, 0, 1, 1}, {0, 0, 0, 0, 0, 0}}, new int[]{0, 0}, new int[]{4, 5})); System.out.println(T.solution(new int[][]{{0, 0, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 0}, {0, 1, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 1, 0, 0, 0}, {0, 0, 1, 0, 0, 0, 0, 0}}, new int[]{0, 0}, new int[]{4, 3})); } } 문제를 다 이해했다고 생각했는데 한참 헤맸네요.. ㅜㅜ AI인턴이 어떻게 동작하는지 모르겠지만 AI로 답변 달아주셔도 됩니다.
- 미해결자바 코딩테스트 - it 대기업 유제
혼자서 푼 문제 확인 부탁드립니다.
import java.util.HashMap; import java.util.Map; import java.util.PriorityQueue; class 방향바꾸기 { public int solution(int[][] board) { int answer = 0; /** * n * m 격자판 지도정보 * 격자판에는 각 1,2,3,4 의 값이 존재 * 1: 오른쪽의 인접한 격자로 이동 * 2. 왼쪽의 인접한 격자로 이동 * 3: 아래로 이동 * 4: 위로 이동 * 0,0부터 오른쪽 아래 맨 끝으로 이동하려고함 * board가 주어지면 목표지점까지 가기위해 방향을 바꾸는 최소 격자 개수 * 한 격자의 방향은 원하는 방향으로 한번만 바꾸기 가능 * * * */ //다익스트라로 인접 순회 할때마다 내가 그 격자를 바라보고있는지 확인 //내가 그 격자를 바라보고있으면 1추가 안함 , 바라보지 않으면 1 추가 int[] dx = {-1, 0, 1, 0}; int[] dy = {0, -1, 0, 1}; PriorityQueue<Candidate> queue = new PriorityQueue(); Map<String, Integer> minPosMap = new HashMap<>(); for (int i = 0; i < board.length; i++) { for (int j = 0; j < board[i].length; j++) { minPosMap.put(j + ":" + i, Integer.MAX_VALUE); } } Pos first = new Pos(0, 0); //첫번째 시작을 넣는다. queue.add(new Candidate(first, 0)); while (!queue.isEmpty()) { int size = queue.size(); for (int i = 0; i < size; i++) { Candidate candidate = queue.poll(); Pos pos = candidate.pos; if (pos.x == board[0].length - 1 && pos.y == board.length - 1) { // print(board, minPosMap); return candidate.cnt; } for (int j = 0; j < 4; j++) { int moveX = dx[j] + pos.x; int moveY = dy[j] + pos.y; if (moveX < 0 || moveY < 0 || moveX >= board[0].length || moveY >= board.length) continue; //현재 Pos 가 moveX, moveY 를 바라보고 있는지 체크 boolean isLookAt = isLookAt(board[pos.y][pos.x], pos, moveX, moveY); //바라보면 cnt 그대로 바라보지 않으면 cnt++ //내가 추가할 값이 기존에 있는 값보다 작아야함 Pos newPos = new Pos(moveX, moveY); int cnt; if (isLookAt) { cnt = candidate.cnt; } else { cnt = candidate.cnt + 1; } Integer baseCnt = minPosMap.get(newPos.getName()); if (cnt < baseCnt) { minPosMap.put(newPos.getName(), cnt); Candidate newCandi = new Candidate(newPos, cnt); queue.add(newCandi); } } } } return answer; } private static void print(int[][] board, Map<String, Integer> minPosMap) { int cnt = 0; for (Integer value : minPosMap.values()) { System.out.print(value + " "); cnt++; if (cnt % board[0].length == 0) System.out.println(); } } private boolean isLookAt(int direction, Pos pos, int moveX, int moveY) { int x = pos.x; int y = pos.y; // * 1: 오른쪽의 인접한 격자로 이동 // * 2. 왼쪽의 인접한 격자로 이동 // * 3: 아래로 이동 // * 4: 위로 이동 int[][] directionCalculate = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}}; return y + directionCalculate[direction - 1][0] == moveY && x + directionCalculate[direction - 1][1] == moveX; } class Pos { int x; int y; public Pos(int x, int y) { this.x = x; this.y = y; } public String getName() { return x + ":" + y; } } class Candidate implements Comparable<Candidate> { Pos pos; int cnt; public Candidate(Pos pos, int cnt) { this.pos = pos; this.cnt = cnt; } @Override public int compareTo(Candidate o) { return cnt - o.cnt; } } public static void main(String[] args) { 방향바꾸기 T = new 방향바꾸기(); System.out.println(T.solution(new int[][]{{3, 1, 3}, {1, 4, 2}, {4, 2, 3}})); System.out.println(T.solution(new int[][]{{3, 2, 1, 3}, {1, 1, 4, 2}, {3, 4, 2, 1}, {1, 2, 2, 4}})); System.out.println(T.solution(new int[][]{{3, 2, 1, 3, 1, 2}, {2, 1, 1, 1, 4, 2}, {2, 2, 2, 1, 2, 2}, {1, 3, 3, 4, 4, 4}, {1, 2, 2, 3, 3, 4}})); System.out.println(T.solution(new int[][]{{3, 2, 1, 3, 1, 2, 2, 2}, {2, 1, 1, 1, 4, 2, 1, 1}, {2, 2, 2, 1, 2, 2, 3, 4}, {1, 3, 3, 4, 4, 4, 3, 1}, {1, 2, 2, 3, 3, 4, 3, 4}, {1, 2, 2, 3, 3, 1, 1, 1}})); System.out.println(T.solution(new int[][]{{1, 2, 3, 2, 1, 3, 1, 2, 2, 2}, {1, 2, 2, 1, 1, 1, 4, 2, 1, 1}, {3, 2, 2, 2, 2, 1, 2, 2, 3, 4}, {3, 3, 1, 3, 3, 4, 4, 4, 3, 1}, {1, 1, 1, 2, 2, 3, 3, 4, 3, 4}, {1, 1, 1, 2, 2, 3, 3, 1, 1, 1}})); } }AI로 답변을 달아주시는 것 같은데 이번에도 확인 부탁드립니다. 해설을 보면 강사님이랑 풀이방식은 비슷한것같습니다.
- 미해결자바 코딩테스트 - it 대기업 유제
혼자서 푼 문제 확인 부탁드립니다.
package com.company.대기업유제.너비우선탐색; import java.util.ArrayDeque; import java.util.ArrayList; import java.util.List; import java.util.Queue; class 숲속의기사 { static class Pos { int x; int y; public Pos(int x, int y) { this.x = x; this.y = y; } } public int solution(int[][] board) { int answer = Integer.MAX_VALUE; /** * 영희는 궁전에서 기사가 지키는 숲을 통과해서 나가야함 * 안전하게 가기위해 기사에게 산딸기를 줘야함 * 최대한 빨리 기사에게 산딸기를 줘야함 * 숲의 지도: R * C 판 형태 * 영희 시작위치, 기사 위치, 산딸기 위치가 표시, 영희가 가지 못하는 위치 * 영희는 산딸기 없이 기사를 지나쳐갈수없음 * 동서남북 하루에 한칸씩 이동 * 영희가 산딸기를 기사에게 가져다주는 가장 짧은 날의 수 * 0 : 영희가 움직일수 있는곳 * 1: 영희가 움직일수 없는곳 * 2. 영희의 시작위치 * 3: 숲속기사의 위치 * 4: 산딸기 위치 * * */ //산딸기 위치 저장 List<Pos> strawberryList = new ArrayList<>(); for (int i = 0; i < board.length; i++) { for (int j = 0; j < board[i].length; j++) { if (board[i][j] == 4) { strawberryList.add(new Pos(j, i)); } } } for (Pos pos : strawberryList) { //* 2. 영희의 시작위치 int count1 = BFS(pos.y, pos.x, board, 2); //* 3: 숲속기사의 위치 int count2 = BFS(pos.y, pos.x, board, 3); answer = Math.min(count1 + count2, answer); } return answer; } private static int BFS(int y, int x, int[][] board, int posType) { //산딸기 위치들로부터 영희의 최소거리, 기사의 최소거리 BFS 각각 한번씩 돌기 Queue<Pos> queue = new ArrayDeque<>(); //BFS를 위한 queue queue.add(new Pos(x, y)); int[] dx = new int[]{-1, 0, 1, 0}; int[] dy = new int[]{0, -1, 0, 1}; boolean[][] ch = new boolean[board.length][board[0].length]; int day = 0; while (!queue.isEmpty()) { int size = queue.size(); for (int i = 0; i < size; i++) { Pos pos = queue.poll(); //현재위치로부터 if(board[pos.y][pos.x] == posType) return day; for (int j = 0; j < 4; j++) { //동서남북 이동 int moveX = pos.x + dx[j]; int moveY = pos.y + dy[j]; if (moveY < 0 || moveX < 0 || moveX >= board[0].length || moveY >= board.length) continue; if(ch[moveY][moveX]) continue; if (board[moveY][moveX] == 1) continue;//1: 영희가 움직일수 없는곳 ch[moveY][moveX] = true; queue.add(new Pos(moveX, moveY)); } } day++; } return -1; } public static void main(String[] args) { 숲속의기사 T = new 숲속의기사(); System.out.println(T.solution(new int[][]{{4, 1, 0, 0, 0, 0, 1, 0}, {0, 0, 0, 1, 0, 1, 0, 0}, {0, 2, 1, 1, 3, 0, 4, 0}, {0, 0, 0, 4, 1, 1, 1, 0}})); System.out.println(T.solution(new int[][]{{3, 0, 0, 0, 1, 4, 4, 4}, {0, 1, 1, 0, 0, 0, 1, 0}, {0, 1, 4, 0, 1, 0, 0, 0}, {0, 0, 0, 1, 0, 0, 0, 0}, {1, 0, 1, 0, 0, 1, 1, 0}, {4, 0, 0, 0, 1, 0, 0, 0}, {4, 1, 0, 0, 1, 0, 0, 0}, {4, 0, 0, 0, 0, 0, 1, 2}})); System.out.println(T.solution(new int[][]{{4, 1, 0, 1, 0}, {0, 1, 0, 1, 0}, {0, 0, 2, 3, 4}, {0, 1, 0, 1, 0}})); } }딸기위치를 기준으로 영희와 숲속의 기사의 최단거리를 각각 따로 BFS로 구하였는데 괜찮은 방법인가요?
- 미해결자바 코딩테스트 - it 대기업 유제
이렇게 풀어도 되는지 궁금합니다.
import java.util.*; class Node implements Comparable<Node>{ int time; char state; public Node(int time, char state){ this.time = time; this.state = state; } @Override public int compareTo(Node o){ if(this.time == o.time)return this.state - o.state; return this.time - o.time; } } class Solution { public int solution(int[] laser, String[] enter){ int answer = 0; ArrayList<Node> arr = new ArrayList<>(); for(String s:enter){ String t = s.split(" ")[0]; String l = s.split(" ")[1]; int start = Integer.parseInt(t.split(":")[0])*60 + Integer.parseInt(t.split(":")[1]); int end = start + laser[Integer.parseInt(l)]; arr.add(new Node(start, 's')); arr.add(new Node(end, 'e')); } Collections.sort(arr); int cnt = 0; for(Node x:arr){ if(x.state == 's')cnt++; else{ cnt--; answer = Math.max(answer, cnt); } } return answer; } public static void main(String[] args){ Solution T = new Solution(); System.out.println(T.solution(new int[]{30, 20, 25, 15}, new String[]{"10:23 0", "10:40 3", "10:42 2", "10:52 3", "11:10 2"})); System.out.println(T.solution(new int[]{30, 20, 25, 15}, new String[]{"10:23 0", "10:40 3", "10:42 2", "10:52 3", "15:10 0", "15:20 3", "15:22 1", "15:23 0", "15:25 0"})); System.out.println(T.solution(new int[]{30, 20, 25, 15}, new String[]{"10:20 1", "10:40 1", "11:00 1", "11:20 1", "11:40 1"})); System.out.println(T.solution(new int[]{30, 20, 25, 15}, new String[]{"10:20 1", "10:20 1", "10:20 1", "10:20 1", "10:20 1"})); } } 입문강의 결혼식과 비슷한 문제로 생각해 이렇게 짰는데 답은 맞게 나왔습니다. 혹시 반례가 있을까요? 아니면 이 방법도 맞는 방법일까요?
- 미해결자바 코딩테스트 - it 대기업 유제
정렬해서 문제풀면
안녕하세요! hashset을 만들고 정렬한뒤 뒤를 확인하는 식으로 풀면 실제 코딩테스트 문제에서는 시간초과가 나타날까요?
- 미해결자바 코딩테스트 - it 대기업 유제
타일점프 질문있습니다
private int BFS(int first) { int answer = -1; queue.add(first); int level = 0; while(!queue.isEmpty()){ int size = queue.size(); level++; for (int i = 0; i < size; i++) { Integer poll = queue.poll(); int num = nums[poll]; //현재로부터 타일 수만큼 모든 경우의 수를 큐에 집어넣는다. //만약 범위를 벗어나거나 도착하면 바로 반환 for (Integer j = 1; j <= num; j++) { if(poll + j < nums.length){ if(poll + j == nums.length -1){ return level; } queue.add(poll + j); } } } } return answer; } 제가 작성한 코드인데 체크라는 배열은 이 문제에서 필요하지 않을것같아 사용하지 않았습니다. 이 경우에도 올바른 답인가요?
- 미해결자바 코딩테스트 - it 대기업 유제
방향바꾸기 문제 질문드립니다.
import java.io.*; import java.util.*; class Node implements Comparable<Node>{ int x; int y; int c; Node(int x, int y, int c){ this.x=x; this.y=y; this.c=c; } @Override public int compareTo(Node o) { return this.c-o.c; } } class Main { public int solution(int[][] board) { int answer = 0; int n=board.length; int m=board[0].length; int[][] dist =new int[n][m]; int INF = (int)1e9; PriorityQueue<Node> q = new PriorityQueue<>(); q.add(new Node(0,0,0)); for(int i=0; i<n; i++) Arrays.fill(dist[i], INF); dist[0][0]=0; int[] dx = {0,0,1,-1}; int[] dy = {1,-1,0,0}; while(!q.isEmpty()) { Node tmp = q.poll(); int nowx = tmp.x; int nowy = tmp.y; int nowc=tmp.c; int dir = board[nowx][nowy]-1; if(nowc>dist[nowx][nowy]) continue; for(int i=0; i<4;i++) { int nx = nowx+dx[i]; int ny = nowy+dy[i]; if(i==dir && dist[nx][ny]>nowc) { dist[nx][ny] = nowc; if(q.add(new Node(nx,ny,dist[nx][ny]))); } else if(i!=dir && dist[nx][ny]>nowc+1) { dist[nx][ny] = nowc+1; q.add(new Node(nx,ny,dist[nx][ny])); } } } answer = dist[n-1][m-1]; return answer; } public static void main(String[] args){ Main T = new Main(); System.out.println(T.solution(new int[][]{{3, 1, 3}, {1, 4, 2}, {4, 2, 3}})); System.out.println(T.solution(new int[][]{{3, 2, 1, 3}, {1, 1, 4, 2}, {3, 4, 2, 1}, {1, 2, 2, 4}})); System.out.println(T.solution(new int[][]{{3, 2, 1, 3, 1, 2}, {2, 1, 1, 1, 4, 2}, {2, 2, 2, 1, 2, 2}, {1, 3, 3, 4, 4, 4}, {1, 2, 2, 3, 3, 4}})); System.out.println(T.solution(new int[][]{{3, 2, 1, 3, 1, 2, 2, 2}, {2, 1, 1, 1, 4, 2, 1, 1}, {2, 2, 2, 1, 2, 2, 3, 4}, {1, 3, 3, 4, 4, 4, 3, 1}, {1, 2, 2, 3, 3, 4, 3, 4}, {1, 2, 2, 3, 3, 1, 1, 1}})); System.out.println(T.solution(new int[][]{{1, 2, 3, 2, 1, 3, 1, 2, 2, 2}, {1, 2, 2, 1, 1, 1, 4, 2, 1, 1}, {3, 2, 2, 2, 2, 1, 2, 2, 3, 4}, {3, 3, 1, 3, 3, 4, 4, 4, 3, 1}, {1, 1, 1, 2, 2, 3, 3, 4, 3, 4}, {1, 1, 1, 2, 2, 3, 3, 1, 1, 1}})); } }이렇게 작성하니까 배열 길이가 맞지 않다고 뜹니다.어디가 잘 못된건가요???
- 미해결자바 코딩테스트 - it 대기업 유제
문제 풀이 질문드립니다.
혼자 풀다가 막힌 문제인데 어떻게 풀어야 할지 몰라서 질문드립니다. 문제를 간략하게 설명하면, 문제가 n*n행렬이 나오는데 (0,0)에서 사람이 움직이는데, 움직이는 조건이 왼손을 터치할 수 있는 방향으로만 움직일 수 있습니다. (0,0)에서 (n-1,n-1)로 나가는 경로의 길이를 구하라. 입니다.만약 s에서 e로 간다면 답이 12가지 입니다.s가 사람 모양이고 왼손을 터치할 수 있는 곳만 움직일 수 있습니다. 레벨탐색으로 하면서 큐를 잡는데Queue<int[]> q = new LinkedList<>();q.add(new int[] {x,y,1}); // x와y는 좌표, 1은 왼손을 터치할 수 있다는 표시로 풀려고 했는데 풀리지 않았습니다. 솔루션이 궁금합니다.
- 미해결자바 코딩테스트 - it 대기업 유제
'ch' 배열을 boolean이 아닌 int로 지정하는 부분에 대해 궁금한 점이 있습니다.
각 학생별 교환 여부만 확인하기위해 선언한 배열이라면, boolean 타입으로도 충분히 판별이 가능할 것 같은데, int 배열로 지정한 부분에 대해 궁금한 점이 있습니다.
- 미해결자바 코딩테스트 - it 대기업 유제
질문 있습니다!!
강의 너무 잘 보고 있습니다!!!백엔드 Java 개발자를 꿈꾸는 대학생입니다!!다름이 아니라 혹시 강의에서 배운 내용을 제 개인 블로그에 정리해도 될지 궁금해서 글 남깁니다!!!
- 미해결자바 코딩테스트 - it 대기업 유제
cpu스케쥴링 질문드립니다.
import java.io.*; import java.util.*; public class Main { public int[] solution(int[][] tasks){ int[] answer = {}; int n=tasks.length; PriorityQueue<int[]> q = new PriorityQueue<>((a,b) ->a[0]==b[0] ? a[1] - b[1] : a[0] - b[0]); LinkedList<int[]> list = new LinkedList<>(); int i=0; for(int[] x :tasks) { list.add(new int[] {x[0],x[1],i}); i++; } answer = new int[n]; list.sort((a,b) ->a[0]-b[0]); int ft=0; for(int idx=0; idx<n; idx++) { if(q.isEmpty()) ft = Math.max(ft, list.peek()[0]); while(!list.isEmpty() && list.peek()[0]<=ft) { //ft를 맨 처음 값으로 만들어주고 int[] x = list.pollFirst(); q.add(new int[] {x[1],x[2]}); //실행시간이랑 작업번호 대입 } int[] ex = q.poll(); ft+=ex[0]; answer[idx] = ex[1]; } return answer; } public static void main(String[] args){ Main T = new Main(); System.out.println(Arrays.toString(T.solution(new int[][]{{2, 3}, {1, 2}, {8, 2}, {3, 1}, {10, 2}}))); System.out.println(Arrays.toString(T.solution(new int[][]{{5, 2}, {7, 3}, {1, 3}, {1, 5}, {2, 2}, {1, 1}}))); System.out.println(Arrays.toString(T.solution(new int[][]{{1, 2}, {2, 3}, {1, 3}, {3, 3}, {8, 2}, {1, 5}, {2, 2}, {1, 1}}))); System.out.println(Arrays.toString(T.solution(new int[][]{{999, 1000}, {996, 1000}, {998, 1000}, {999, 7}}))); } }while(!list.isEpmty() || !q.isEmpty()){}이렇게 생각을 못할 거 같아서그냥 애초에 for(int idx=0; idx<n; idx++){}로 바꿨습니다.답을 똑같이 나오는데, 이렇게 작성해도 상관없는건가요??
- 미해결자바 코딩테스트 - it 대기업 유제
백준 <수확> 코드
public class Main { public static int solution(int[] value, int N) { int[][] dynamic = new int[N + 1][N + 1]; int[] sum = new int[N + 1]; for (int i = 1; i <= N; i++) { dynamic[i][i] = value[i]; } sum[1] = 1; for (int i = 2; i <= N; i++) { sum[i] = sum[i - 1] + value[i]; } for (int i = 1; i < N ; i++) { for (int j = 1; j <= N - i; j++) { dynamic[j][j + i] = Math.max(dynamic[j + 1][j + i], dynamic[j][j + i - 1]) + (sum[j + i] - sum[j - 1]); } } return dynamic[1][N]; } public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); int N = Integer.parseInt(st.nextToken()); int[] value = new int[N + 1]; for (int i = 1; i <= N; i++) { value[i] = Integer.parseInt(br.readLine()); } System.out.println(solution(value, N)); } }강사님, 안녕하세요! 강의 보고 구현한 코드인데, 백준에서 채점이 틀리게 나와서 혹시 로직이 틀린건지 궁금합니다. [해결 됐습니다!]1부터 n까지 합 저장하는 배열인 sum을 초기화하면서sum[1] = value[1] 을 해야 할 것을 sum[1] = 1; 로 잘못 초기화 했네요.우연히 테스트 케이스 value[1] 값이 1이어서 해당 답만 맞았던 것 같습니다.강의 보면서 실력이 늘고 있음을 느끼고 있습니다. 감사합니다:)