swap() 배열의 두 인덱스의 원소를 교환하는 메소드이다. 정렬의 특성상 자주 사용되며 다음에 나올 예시들에서도 사용해도 된다.public static void swap(int[] arr, int idx1, int idx2) { int temp = arr[idx1]; arr[idx1] = arr[idx2]; arr[idx2] = temp; } 1. 버블 정렬 (Bubble Sort) 순서대로 근접한 두 수를 비교해서 오른쪽 수가 왼쪽 수보다 더 작으면 교환 이 작업을 한 번 수행할 때마다 맨 끝자리에 가장 큰수가 가게 된다. 시간 복잡도 : O(N^2) private static void bubbleSort(int[] arr) { int temp; for (int i = 0; i < arr.length..
빅오 표기법의 그래프는 x축은 입력의 갯수, y축은 시간을 나타낸다. 출처 : http://bigocheatsheet.com/ 빅오 표기법은 알고리즘의 최악의 경우 복잡도를 측정하는 기법이다. 보통 O(n)과 같이 표기하며 여기서 n은 입력의 개수를 의미한다. 따라서 n이 무한으로 접근할 때 무슨일이 일어날까? 정도로 생각하면 좋을 듯 하다. 가장 빠른 순 O(1) ->O(log n) -> O(n) -> O(n log n) -> O(n^2) -> O(2^n) Loof 내에서 Loof를 돌면? (이중 for문) public class Main { public static void printItems(int n) { for (int i =0; i O(n^2) O(100n^2)는 빅오 표기법으로 어떻게 쓰여질..
121. Best Time to Buy and Sell Stock 문제를 이해한 바로는, 순차적으로 읽어가며 가장 작은 값이 나온 경우 최소값을 대체하고, 최소값과 현재 시장가의 차로 수익을 계산 한다. 그리고 가장 그 차이가 큰 경우의 값을 리턴해준다. class Solution { public int maxProfit(int[] prices) { int answer =0; int min = Integer.MAX_VALUE; for(int i=0; ianswer) answer는 그 차이값으로 대체된다 409. Longest Palindrome 해당 input의 값으로 앞으로 읽어도, 뒤로 읽어도 같은 문자를 만들 때 그 길이를 묻는 문제다. ex) 수박이박수 ? 같은 느낌이랄까 class Solutio..
876. Middle of the Linked List 해당 노드의 가운데 헤드를 찾는 문제이다. 만약 중간 값이 두가지라면 뒤의 값을 반환. 문제를 해결하기 위해 보통 두가지 방법이 있다. class Solution { public ListNode middleNode(ListNode head) { ListNode A = head; ListNode B = head; while(B!=null && B.next != null){ B = B.next.next; A = A.next; } return A } } 문제 풀이 (1) - Fast and Slow Pointer Fast and Slow Pointer 라는 방법이 있다. B의 노드가 두 칸을 갈때, A의 노드는 한 칸씩 가는 방법이다. B가 마지막에 도..
206. Reverse Linked List 주어진 노드를 역순으로 새로 연결하는 것이다. class Solution { public ListNode reverseList(ListNode head) { ListNode prev = null; ListNode current = head; while(current != null){ ListNode next = current.next; current.next = prev; prev = current; current = next; } return prev; } } 문제 풀이 먼저 세개의 포인터가 필요하다 (prev, current, next) 가장 먼저 prev 포인터를 null로 만들어준다. 현재의 포인터 current를 head로 만들어준다. head가 nu..
205. Isomorphic Strings 문자열 s,t가 주어지고 s와 t가 동형체(isomorphic)인지 확인하는 문제이다. 즉 두 문자열이 동형체일 경우 s의 문자열 -> t로 변경 가능 하다는 뜻 class Solution { public boolean isIsomorphic(String s, String t) { HashMap map = new HashMap(); int length = s.length(); for (int i = 0; i < length; i++) { char sc = s.charAt(i); char tc = t.charAt(i); if (i == 0) { map.put(sc, tc); } else { if (map.containsKey(sc)) { if (map.get(sc..
1480. Running Sum of 1d Array 배열 속 숫자들을 누적시키며 합을 구하는 문제이다. class Solution { public int[] runningSum(int[] nums) { int[] answer = new int[nums.length]; int sum = 0; for (int i = 0; i < nums.length; i++) { int temp = nums[i]; sum += temp; answer[i] = sum; } return answer; } } 문제 풀이 정답의 배열 크기는 nums의 크기와 같다. 합을 나타내는 sum 변수를 0으로 초기화 해준다. nums의 배열 크기만큼 반복문을 돌고, temp라는 변수를 nums의 각 자리의 수로 할당해준다. sum변수에 ..
