package hash; import java.util.ArrayList; import java.util.Collection; import java.util.HashSet; import java.util.Scanner; public class TypeOfSales { static ArrayList<Integer> solution(int n, int k, int[] arr) { Collection<Integer> set = new HashSet<>(); Collection<Integer> list = new ArrayList<>(); ArrayList<Integer> result = new ArrayList<>(); int p1 = 1; for(int i = 0; i < k; i++) { list.add(arr[i]); } set.addAll(list); result.add(set.size()); while(p1 < n-k+1) { set.clear(); list.remove(arr[p1-1]); list.add(arr[p1+k-1]); set.addAll(list); result.add(set.size()); p1++; } return result; } public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int k = sc.nextInt(); int[] arr = new int[n]; for(int i = 0; i < n; i++) { arr[i] = sc.nextInt(); } for(int x : TypeOfSales.solution(n, k, arr)) { System.out.print(x + " "); } } } 시간 복잡도는 O(N)이 맞는거같은데 4번 5번 테스트 케이스에서 2초 가까이 뜨네용..
안녕하세요 큰돌님! go 재귀 함수에 대해 이해가 되지 않는 부분이 있습니다. 제가 완탐에 대한 이해가 부족해서 함수 호출에 대한 로직이 이해가 안되는 것 같습니다. 질문 Board d = c; 로 원본과 동일한 보드를 생성하고 d._move()하는 것 까지는 이해를 했습니다. 그런데 그 다음에 왜 d._rotate90();가 아닌 c._rotate90();를 하는지 모르겠습니다. move한 다음 rotate, 또 다시 move한 다음 rotate 과정을 반복하려면 d._rotate90();가 되어야하는 것 아닌가요..? d._move(); go(d, here + 1); c._rotate90(); 이 과정만으로 5번 이동시키는 완탐을 진행할 수 있는지 이해가 안됩니다 ㅜㅜ 혹시 함수 호출이 어떻게 진행되는지 그림으로 설명해주실 수 있나요? 제가 생각한 완탐 방식은 아래와 같습니다. 함수 호출 순서가 go(d, here + 1); c._rotate90(); 인데 그러면 마지막 호출되는 함수가 return 되고 rotate과정이 진행되는게 아닌가요? rotate함수가 언제 실행되는지 잘 모르겠습니다. 제가 생각하는 함수 호출 순서는 아래 그림과 같습니다. 뭔가 그림이 카오스네요.. 큰돌님 코드 void go(Board c, int here){ if(here == 5){ c.get_max(); return; } for(int i = 0; i < 4; i++){ Board d = c; // 동일한 구조체 생성 d._move(); go(d, here + 1); c._rotate90(); } return; }
- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요! - 먼저 유사한 질문이 있었는지 검색해보세요. - 서로 예의를 지키며 존중하는 문화를 만들어가요. - 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요 import java.util.*; public class Main { public static void main(String[] args){ Scanner sc = new Scanner(System.in); int cnt = sc.nextInt(); String pw = sc.next(); pw = pw.replaceAll("#","1").replaceAll("/*","0"); String answer = ""; for(int i=0 ; i<cnt*7 ; i+=7){ char target =(char)Integer.parseInt(pw.substring(i,i+7),2); answer +=target; } System.out.println("answer = " + answer); } } 콘솔창 : IntellJ에서는 직접 값을 입력하면 잘 뜨는데 강사님의 채점 프로그램에서는 작동하지 않습니다... 뭐가 문제일까요
백준에서 bfs와 dfs 관련 문제를 추가적으로 풀다보니까, Python3에서는 시간 초과를 해결되지 않는 문제가, PyPy3에서는 해결되는 경우가 있습니다. 이럴 때는 Python3에서도 해결 가능하도록 시간 복잡도를 줄이기 위해 노력해야 할까요? 아니면 PyPy3 환경에서 정답임을 만족해야 할까요...?
강사님 안녕하세요. 좋은 강의 잘 듣고 있습니다. 임시반장 정하기 문제에서 강사님이 작성해주신 코드와 동일하게 solution 메서드를 만들었다고 보이는데 런타임 에러로 나오는거 같습니다. 혹시 원인을 알 수 있을까요? 감사합니다. import java.util.*; public class Main { public int Solution(int n, int[][] array) { int answer=0, max=Integer.MIN_VALUE; for(int i=1; i <=n; i++) { int cnt = 0; for(int j=1; j<=n;j++) { for(int k=1; k<=5;k++) { if(array[i][k] == array[j][k]) { cnt++; break; } } } if(cnt>max) { max = cnt; answer = i; } } return answer; } public static void main(String[] args) { Scanner in=new Scanner(System.in); int n = in.nextInt(); Main T = new Main(); int[][] array = new int[n][n]; for(int i = 0; i < n ; i++) { for(int j = 0; j < n ; j++) { array[i][j] = in.nextInt(); } } System.out.println(T.Solution(n, array)); } }
기존코드 def two_sum(nums, target): memo = {} for v in nums: memo[v] = 1 for v in nums: needed_number = target - v if needed_number in memo: return True return False 기존 코드에서 첫번째 for문은 O(n)이고 두번째 for문은 O(1)이 n번 실행되니까 최종적으로는 O(n)이 되어서 해당 알고리즘의 시간복잡도는 O(n)이되는데 처음에 문제를 설명해주실때의 순서대로라면 4를 먼저넣고 target이 14니까 10이 있는지 확인해보고 없으니까 1을 넣고 13이없는지 확인해보고 없으니까 9를 넣고 5가 없으니까 7을 넣고 7이 없으니까 5를 넣고 9가 있으니까 true를 반환 이라고 생각을 했고 그렇게 로직을 짜면 아래와 같은 코드가 될것같습니다(제가 파이썬을 잘 몰라서 정확한지는 모르겠네요 ㅠㅠ) def two_sum(nums, target): memo = {} for v in nums: memo[v] = 1 needed_number = target - v if needed_number in memo: return True return False 해당 코드에서는 첫번째 for문 내부의 시간복잡도가 전부다 O(1)이고 그걸 n번 반복하는것이니 O(n)이라는 최종적인 시간복잡도라고 생각을 하는게 맞을까요?? 만약에 아래에 짠 로직이 올바른 로직이라면 위에 로직은 n번 연산하면서 dictionary에 넣고 후에 요소를 돌면서 답을 찾고 아래로직은(코드가 맞다면) dictionary를 다 넣지 않더라도 중간에 값이 나오면 중간에 연산을 끝낼 수 있으니까 조금더 효율적이라고 생각을 했습니다 제가 생각한 방식이 맞는지 그리고 이런 작은(?)효율성이 코딩테스트에서 의미있게 다가올지가 궁금합니다!
안녕하세요? 강사님께서 영상에서는 deque 자료형으로 바로바로 pop 하는 방식으로 코드를 짜셨는데요 강의 내용: arr.sort() arr = deque(arr) cnt = 0 while arr: if len(arr)==1: cnt += 1 break if arr[0]+arr[-1] > limit: arr.pop() cnt += 1 else: arr.popleft() arr.pop() cnt += 1 print(cnt) 그런데 비슷하다고 생각한 인덱스 이동 방식은 오답인 거 같습니다 arr.sort() lt = 0 rt = n - 1 while lt <= rt: if len(arr) == 1: cnt += 1 break sum = arr[lt] + arr[rt] if sum <= limit: cnt += 1 lt += 1 rt -= 1 else: cnt += 1 rt -= 1 # 맨 끝 가장 큰 수 pop print(cnt) 테스트 케이스는 강사님께서 댓글에 알려주신 8 149 71 72 73 74 75 76 77 78 149 로 돌려보니, 강의 내용은 5가 나오고 두번째 방식은 4가 나오네요? 근데 제가 이해가 딸려서 그런지 인덱스 이동하는 방식과 pop 방식의 차이가 잘 머리로 들어오지 않습니다..
- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요! - 먼저 유사한 질문이 있었는지 검색해보세요. - 서로 예의를 지키며 존중하는 문화를 만들어가요. - 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요. 아래와 같이 풀어도 될까요 ? 아래와 같은 경우에 시간복잡도는 어떻게 될까요 ...? const solution = (k, arr) => { let answer = Array.from({ length: k }, () => 0); for (let i = 0; i < arr.length; i++) { if (!answer.includes(arr[i])) { answer.unshift(arr[i]); answer.pop(); } else { let tmp = answer.filter((v) => v !== arr[i]); tmp.unshift(arr[i]); answer = tmp; } } return answer; }; console.log(solution(5, [1, 2, 3, 2, 6, 2, 3, 5, 7]));
enumerate 함수에 대해 질문 있습니다. a=[23, 12, 36, 53, 19] for x in enumerate(a): print(x) print() for x in enumerate(a): print(x[0], x[1]) print() for index, value in enumerate(a): print(index, value) print() 똑같은 enumerate함수를 썼는데 왜 첫번째 for문에서만 튜플 형태로 출력이 되고 두번째, 세번째에선 그냥 값만 출력이 되는 건가요?
안녕하세요 선생님! 복습하다가 의문점이 생겨 질문드립니다. from collections import defaultdict N = int(input()) T = int(input()) dic = defaultdict(list) discovered = [] for _ in range(T): a, b = map(int, input().split()) dic[a].append(b) dic[b].append(a) def dfs(node): global dic, discovered discovered.append(node) for n in dic[node]: if n not in discovered: dfs(n) return dfs(1) print(len(discovered) - 1) 이 코드에서 dic[b].append(a)를 지워도 문제 해결에는 영향이 없어 보이는데, 백준에 제출하면 틀린 답으로 나옵니다. 즉, 그래프를 양방향이 아닌 단방향으로 설정해도 문제 없지 않나요..?
코테를 볼때 1차 2차 나눠서 보는 기업이 있더라구요 (대표적으로 카카오)근데 1차는 알고리즘이고 2차는 api 통신을 해야하는 코테로 진행한다고 봤는데 이렇게 api통신을 이용해 코테를 보는 기업이 많을까요? 제가 찾을때는 카카오만 보여서 질문드렸습니다 또 sql 코테를 보는곳도있다고 들었는데 이것도 많이 보는지 여쭤보고 싶습니다
문제를 보면 입력 첫째 줄에 숫자의 개수 N (1 ≤ N ≤ 100)이 주어진다. 둘째 줄에 숫자 N개가 공백없이 주어진다. 라고 조건이 주어지는데 강의의 풀이를 보면 숫자의 개수를 N개로 제한하는 부분이 없고 실행해보면 N개 이상 또는 이하의 숫자가 들어가도 상관이 없이 실행되는데 보통 코테에서도 이런식으로 제한에 러프하게 코딩해도 상관이 없는 건가요? 아니면 문제에 제한이 있어서 코딩에서는 제한을 따로 두지않는건가요??
