22년 1월 2주차 회고록 (스터디 자랑)

public class Solution { public int[] solution(int[] prices) { int[] answer = new int[prices.length]; for (int i = 0; i < prices.length; i++) { //price 길이만큼 반복 //종료조건 : 마지막은 무조건 0이다. ArraysOutOfIndex 방지 if(i == prices.length - 1) { answer[i] = 0; break; } int cnt = 0; // answer[i]의 갯수 int num = prices[i]; // 비교할 기준 숫자 for (int j = i + 1; j < prices.length; j++) { if (num <= prices[j]) cnt++; //다음 숫자와 비교해서 다음숫자가 더 크다면 ++ else if (num > prices[j]){ // 작다면 ++후 종료 cnt++; break; } } answer[i] = cnt; } return answer; } public static void main(String[] args) { Solution solution = new Solution(); Scanner sc = new Scanner(System.in); int[] prices = {1, 2, 3, 2, 3}; System.out.println(Arrays.toString(solution.solution(prices))); } }

public class SolutionBestCode { public int[] solution(int[] prices) { int len = prices.length; int[] answer = new int[len]; int i, j; for (i = 0; i < len; i++) { for (j = i + 1; j < len; j++) { answer[i]++; if (prices[i] > prices[j]) break; } } return answer; } public static void main(String[] args) { SolutionBestCode solution = new SolutionBestCode(); int[] prices = {1, 2, 3, 2, 3}; System.out.println(Arrays.toString(solution.solution(prices))); } }

public class MainOn2 { public static void main(String[] args) { /** * 시간복잡도가 O(n2)이다. */ Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int m = sc.nextInt(); int[] arr = new int[n]; for (int i = 0; i < n; i++) arr[i] = sc.nextInt(); int cnt = 0; for (int i = 0; i < arr.length; i++) { int sum = 0; for (int j = i; j < arr.length; j++) { if(sum < m) sum += arr[j]; if (sum == m) { cnt++; break; } } } System.out.println(cnt); } }

public class Main { /** * 투 포인터로 : 시간복잡도 최대 O(n)이다. * 시간복잡도 : Sum과 m을 비교하는 횟수 = start와 end가 움직이는 횟수 * 최대로 움직여봤자 2n번 움직이므로 O(n)이 된다. */ public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int m = sc.nextInt(); int[] arr = new int[n]; for (int i = 0; i < n; i++) arr[i] = sc.nextInt(); /** * 4 2 * 1 1 1 1 */ // start : 연속구간의 시작, end : 연속구간의 끝 int start = 0; int end = 0; int sum = 0; //연속되는 구간의 합 int cnt = 0; //정답인 갯수 while (true) { if (sum >= m) { sum -= arr[start++]; } else if (end >= n) { //종료조건 break; } else { //m보다 sum이 더 작으면 sum += arr[end++]; } if (sum == m) cnt++; } System.out.println(cnt); } }

from collections import deque def solution(prices): answer = [0]*len(prices) for i in range(len(prices)): stack = deque(prices[i:]) count = 0 critical = stack.popleft() while(len(stack)>0): value = stack.popleft() if(value >= critical): count += 1 else: count += 1 break answer[i] = count return answer print(solution([1,2,3,2,3])) # 4, 3, 1, 1, 0 print(solution([1,2,3,4,2,3])) # 5, 4, 2, 1, 1, 0 print(solution([1,2,3,2,1,4,2,3])) # 7, 3, 1, 1, 3, 1, 1, 0

def solution(prices): answer = [0]*len(prices) for i in range(len(prices)): pointer = i # pointer는 비교하고 싶은 숫자의 index를 나타냄 count = 0 critical = prices[pointer] pointer += 1 while(pointer < len(prices)): if (prices[pointer] >= critical): pointer += 1 count += 1 else: count += 1 break answer[i] = count return answer print(solution([1,2,3,2,3])) # 4, 3, 1, 1, 0 print(solution([1,2,3,4,2,3])) # 5, 4, 2, 1, 1, 0 print(solution([1,2,3,2,1,4,2,3])) # 7, 3, 1, 1, 3, 1, 1, 0

# 시간 초과 import sys factors = sys.stdin.readline().split(" ") length = int(factors[0]) goal = int(factors[1]) nums = list(map(int, sys.stdin.readline().split(" "))) counts = 0 for i in range(length): pointer = i sum = 0 while(pointer < length): sum += nums[pointer] if(sum == goal): counts += 1 break elif (sum > goal): break else: pointer += 1 print(counts)

import sys length, goal = map(int, sys.stdin.readline().split(" ")) nums = list(map(int, sys.stdin.readline().split(" "))) counts = 0 for i in range(length): sum = 0 for pointer in range(i, length): sum += nums[pointer] if(sum == goal): counts += 1 break elif (sum > goal): break print(counts)

import sys length, goal = map(int, sys.stdin.readline().split(" ")) nums = list(map(int, sys.stdin.readline().split(" "))) counts = 0 left_idx = -1 right_idx = -1 sum = 0 while (True): if(right_idx < length -1): if(sum < goal): right_idx += 1 sum += nums[right_idx] else: left_idx += 1 sum -= nums[left_idx] else: left_idx += 1 sum -= nums[left_idx] if(sum == goal): counts += 1 if (right_idx >= length -1) and (left_idx >= length -1): break print(counts)

# 해시 - 시간초과 from collections import defaultdict def solution(prices): N = len(prices) MAX_PRICE = max(prices) answer = [0] * N stock = defaultdict(list) stock[prices[0]].append(0) for i in range(1, N-1): for key in stock: if prices[i] >= key: continue while stock[key]!=[]: idx = stock[key].pop() answer[idx] = i - idx stock[prices[i]].append(i) for key in stock: while stock[key]!=[]: idx = stock[key].pop() answer[idx] = N - 1 - idx return answer prices = [1,2,3,2,3] print(solution(prices))

# 완전탐색 - 성공 def solution(prices): N = len(prices) answer = [0] * N for i in range(N): for j in range(i+1, N): answer[i] += 1 if prices[i] > prices[j]: break return answer print(solution([1,2,3,2,3]))

# 시간초과 N, M = map(int, input().split()) A = list(map(int, input().split())) count = 0 for i in range(N): sum_of_num = 0 for j in range(i,N): sum_of_num += A[j] if sum_of_num > M: break elif sum_of_num == M: count += 1 break print(count)

# 2003 https://www.acmicpc.net/problem/2003 # 완료 N, M = map(int, input().split()) A = list(map(int, input().split())) count = 0 sum_of_num = A[0] left = 0 i = 1 while(True): if sum_of_num == M: count+=1 sum_of_num -= A[left] left += 1 elif sum_of_num > M: sum_of_num -= A[left] left += 1 else: if i < N: sum_of_num += A[i] i +=1 else: break print(count)

def solution(N, M, arr): start, end = 0, 0 total = arr[0] cnt = 0 while True: if total < M: end += 1 if end >= N: break total += arr[end] elif total == M : cnt += 1 total -= arr[start] start += 1 else: total -= arr[start] start += 1 return cnt N, M = map(int, input().split()) arr = list(map(int, input().split())) print(solution(N, M, arr))

시간복잡도를 계산하는것과, for문이 아닌 다른 해법들을 찾는게 어려웠다.

백준 문제를 풀 때 two pointer라는 알고리즘을 떠올려야 했던 부분이 어려웠던 것 같다. 문제를 보면 풀이를 외워야하는 수준인건가... 라는 생각도 들었던 것 같다.

1. 틀렸을 때보다 시간초과가 날 때가 더 당황스러운 것 같다. 접근 방식을 바꾸어야 한다는 뜻이니까 생각해내기가 더 어려운 것 같다. 2. 투 포인터 문제에서 while 루프의 탈출 조건을 제대로 계획하지 않으면 무한루프가 나기 쉬운 것 같다.

two pointer 문제는 몇 번 풀어본적이 있었는데 역시 예외 부분을 떠올리는게 쉽지 않은 것 같습니다.. 이 부분을 조금 더 신경 써서 공부해야겠습니다..!

문제를 해결할때 어떻게하면 조금 더 효율적인 코드를 작성할 수 있을까? 어떻게 하면 더 깔끔한 코드를 작성할 수 있을까? 라는 생각을 하자!

deque()를 여러번 선언해야하는 경우는 시간이 더 오래걸릴 수 있으니 주의하자!

늘 효율성을 생각하면서 코드를 짜자. 먼저 직관적으로 생각나는 코드를 작성해보고, 이후에 되지 않으면 다른 방법을 생각해보는 방향으로 접근하자.

계속해서 코드를 작성하면서 느낀점이 반복문으로만 짜려는 느낌적 느낌이 있는데, 해당부분을 다른 방법이 있다면 다르게도 짜보는 노력을 해봐야겠습니다! 그리고 시간복잡도를 계산하는 노력을 하면 자연스럽게 좋은 코드가 나올 것 같다는 생각을 하게 되었습니다!

일단 풀고보면 해결이 될때도 있다. 어렵다고 시작하지 않을때도 있는데 그러지 말고 할수있는한 최선을 다해보자

저번 주랑 비슷하게 문제 유형에 따라 풀이를 정리하는 것이 필요하다는 것을 절실히 느꼈다.

시간복잡도를 더 생각하면서 코드를 짜는 습관을 길러야 할 것 같다.

생각대로 짠 로직에서 예외부분은 없는지 있다면 어떻게 처리해야할지에 대한 생각을 계속해서 하는 노력을 해야겠습니다 ㅠ