꿀잠

https://leetcode.com/problems/kth-largest-element-in-an-array/description/

sort를 쓰지 않고 배열의 K번째로 큰 요소를 찾는 문제이다.
알고리즘을 복습하려고 따라가고 있는 리트코드 로드맵상에선 Heap & Priority Queue로 지정되어있어 Priority Queue를 이용해서 풀었다.

사실 PriorityQueue도 sort를 이용하는게 아닌가 하는 의구심이 들기는 한다.
하지만 Arrays.sort()를 이용하여 문제를 풀 경우 오류를 내뱉었다.

문제에서 PriorityQueue를 사용시 오류가 발생하지 않으며 이는 PriorityQueue를 허용한다는 의미이며

그것이 문제의 의도라고 확인하였다.
문제 풀이에 성공한 코드는 아래와 같다.

import java.util.*;  
  
public class Solution {  
    public int findKthLargest(int[] nums, int k) {  
        PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> b - a);  
        // PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());  
        for (int num : nums) {  
            pq.add(num);  
        }  
  
        while (k-- > 1) {  
            pq.poll();  
        }  
  
        return pq.poll();  
    }  
}

PriorityQueue 는 기본적으로 Integer 의 compareTo 메서드에 따라 오름차순으로 정렬하기 때문에 생성시 새로운 compareTo 메서드를 오버라이드 해야한다. Collections.reverseOrder()를 이용해 간단히 역순 정렬을 할 수도 있으며, 직접 수식을 compareTo 메서드에 오버라이드 해주는 것도 방법이다. 이 때 화살표 함수로 손쉽게 메서드를 표기할 수 있다.

PriorityQueue에 nums 배열을 넣은 후에는 간단하다. k번째로 큰수이기 때문에 k번째의 수를 뽑아내주면 된다. k-1 번째까지 뽑은 후 리턴시 k번째 수를 poll하여 반환하였다.

https://leetcode.com/problems/binary-tree-level-order-traversal/description/

주어진 커스텀 클래스인 이진트리 노드를 레벨에 따른 중첩 List배열로 반환하는 문제이다.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */

class Solution {  
    public List<List<Integer>> levelOrder(TreeNode root) {  
        List<List<Integer>> answer = new ArrayList<>();  
        if (root == null) {  
            return answer;  
        }  
  
        Queue<TreeNode> que = new ArrayDeque<>();  
        que.offer(root);  
  
        while (!que.isEmpty()) {  
            List<Integer> levelList = new ArrayList<>();  
            int queSize = que.size();  
  
            while (queSize-- > 0) {  
                TreeNode node = que.poll();  
                levelList.add(node.val);  
                if (node.left != null) {  
                    que.offer(node.left);  
                }  
  
                if (node.right != null) {  
                    que.offer(node.right);  
                }  
            }  
            if (levelList.size() > 0) {  
                answer.add(levelList);  
            }  
        }  
  
        return answer;  
    }
}

레벨 단위로 처리하기 위해서 Queue를 이용하였다. 하나의 레벨을 Queue 에 넣어 전부 꺼내며 리스트를 완성하고, 전부 꺼내는 동안 다음 레벨의 노드를 Queue에 넣어 순차적으로 레벨 List를 만들어 주었다. 하나의 레벨을 꺼내며 Queue에 새로 넣기 때문에 하나의 레벨을 빼내기 전에 사이즈를 체크해서 꺼내면 된다.

https://leetcode.com/problems/reverse-linked-list/description/

주어진 커스텀 클래스 형태인 Linked List 를 역순으로 생성해서 반환하는 문제이다.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */

class Solution {
    public ListNode reverseList(ListNode head) {
		ListNode answer = null;  
		  
		while(head != null){  
		    answer = new ListNode(head.val, answer);  
		    head = head.next;  
		}  
		  
		return answer;
    }
}

문제는 간단하게 헤드를 기준으로 새로운 노드를 만들고 순서대로 이어 붙이면 된다.
문제는 헤드부터 주어진 리스트 노드를 기준으로 새로 노드를 만들면 next에 할당하면 된다. 생성자 및 null 체크를 잘 활용해야 했다.

https://leetcode.com/problems/binary-search/description/

이진탐색 알고리즘을 알고있는지 체크하는 문제로 O(log n) 시간복잡도를 요구한다.
특이점으로는 존재하지 않는 값을 타겟으로 하는 문제가 존재하고 그럴경우 -1 값을 리턴해야 한다는 것이다.

이진 탐색을 위해 low, high 값을 설정하고 mid를 인덱스로 하여 값을 비교하고, 값에 따라 low, high 미드값을 변경하여 mid 인덱스로 타겟을 찾아가는 방식이다

class Solution {  
    public int search(int[] nums, int target) {  
        int len = nums.length;  
        int low = 0;  
        int high = len - 1;  
        int mid = (low + high) / 2;  
  
        // while 의 조건문을 통해 타겟에 도달했는지 확인  
        while(nums[mid] != target){  
            int cur = nums[mid];  
            if(cur > target){  
                // index 범위를 초과하거나, 답이 없거나를 체크  
                if(mid - 1 < 0 || nums[mid - 1] < target){  
                    mid = -1;  
                    break;  
                }  
                // 중간점 체크를 위해 값 비교를 통해, low - high 값 전환  
                high = mid - 1;  
  
            }else{  
                // index 범위를 초과하거나, 답이 없거나를 체크  
                if(mid + 1 >= nums.length || nums[mid + 1] > target){  
                    mid = -1;  
                    break;  
                }  
  
                // 중간점 체크를 위해 값 비교를 통해, low - high 값 전환  
                low = mid + 1;  
            }  
            // 변경된 low, high 값을 이용해 새로운 중간점 변경  
            mid = (high + low) / 2;  
        }  
  
        return mid;  
    }  
}

답이 없는 부분을 체크하기 위해, 바로 근처 값을 확인 하는 방식을 넣었다.

이 때 인덱스가 배열의 범위를 초과하는지 체크하지 않으면 배열의 범위를 초과하는 인덱스 값을 검사하여

오류를 발생 시킬 수 있다.

이진 탐색 문제를 풀 때는 항상 범위를 잘못 처리하거나,

인덱스 조정 시 실수하여 while문을 탈출하지 못하는 실수를 할 때가 많다.

다행히 해당 문제는 조건이 까다롭지 않고 기초적인 이진탐색을 요구하기에 이진탐색을 입문하기 좋은 문제였다.

https://leetcode.com/problems/valid-parentheses/description/

주어진 문자열의 괄호들이 제대로 닫혀있는지 물어보는 문제이다.
정상적으로 닫혀 있다면 순서대로 닫혀야 하므로 스택을 이용한 문제이다.
스택을 공부할 때 가장 기본적으로 나오는 문제이다. 사실 이와 같은 형태의 문제를 보았을 때 처음 보는 경우에는 왜 스택이 필요한지 이해가 되지 않을 수도 있다.

스택의 개념을 머리에 넣고 주어진 문자열을 차례대로 넣었다가 빼는 것을 확인해 보면 마지막에 넣은 것을 먼저 빼는 스택의 성질이 괄호를 정확히 순서대로 닫아준다는 것을 확인할 수 있다.
아래는 문제를 해결한 코드이다.

import java.util.*;

class Solution {  
    public boolean isValid(String s) {  
	  // Java의 경우 tack, LinkedList 후에 추가된 클라스인 ArrayDeque의 성능이 좋은 것으로 알려져 있다.
        Deque<Character> stack = new ArrayDeque<>();  
        
        for(int i = 0; i < s.length(); i++){  
            char c = s.charAt(i);  
            while(true){  
	         // 1. 스택이 비어있거나, 짝이 맞지 않는다면 문자열을 스택에 넣고 다음으로 넘어간다.
                // 2. 1조건이 맞지 않는다면 스택이 비어있지 않고, isPair(짝) 인 것이기에 
                //    짝에 맞는 스택의 값을 빼내준다. 이후 순차적으로 다시 비교하기 위해 c에 값을 할당 하면 
                //    while 문이 반복되면서 처리한다.
                
                if(stack.isEmpty() || !isPair(stack.peekLast(), c)){  
                    stack.offerLast(c);  
                    break;  
                }else {  
                    stack.pollLast();  
                    if(stack.isEmpty()){  
                        break;  
                    }else{  
                        c = stack.pollLast();  
                    }  
                }  
            }  
        }  
  
	  // 스택이 비어있다면 모든 괄호의 값들이 짝이 맞아 제거 된 것이므로 valid 하다
        return stack.isEmpty();  
    }  
  
    public boolean isPair(char a, char b){  
        return (a =='(' && b ==')')  
                || (a =='{' && b =='}')  
                || (a =='[' && b ==']');  
    }  
}

짝이 맞는 괄호일 때 while 문을 이용하여 연속적으로 확인하여 중첩된 괄호를 확인할 수 있다.
isPair의 경우 신규 값인 b의 값이, 스택에 있던 a의 값을 닫는 형태인지 체크하고 있다.

https://leetcode.com/problems/valid-palindrome/description/

문자열의 "palindrome" 이라는 조건을 알려주고 해당 조건에 맞는지 여부를 boolean으로 리턴하는 문제이다.

palindrome의 조건은 다음과 같다.

1. 대문자를 소문자로 바꾼다.
2. non-alphanumeric 문자를 지운다.
3. 1-2 과정을 통해 나온 문자를 앞에서 뒤로, 뒤에서 앞으로 읽을 때 같은 문자열이다

해결한 코드는 아래와 같다.

import java.util.*;
// util 패키지를 임포트 해야 어레이리스트를 사용할 수 있다.

class Solution {

	public boolean isPalindrome(String s) {  
		// 1. 문자열의 소문자 변환  
		s = s.toLowerCase();  
		  
		// 2. non-alphanumeric 문자를 제거, alphanumeric 문자만으로 문자열을 새로 구성하기 위해 StringBuilder를 이용  
		StringBuilder createdSb = new StringBuilder();  
		for(int i = 0; i < s.length(); i++){  
		    char c = s.charAt(i);  
		    if(c >= 'a' && c <= 'z'){  
		        createdSb.append(c);  
		    }  
		    if(c >= '0' && c <= '9'){  
		        createdSb.append(c);  
		    }  
		}  
		  
		// 3. StringBuilder의 reverse() 메서드를 이용하여 boolean 값 체크  
		String newStr = createdSb.toString();  
		String reverseStr = new StringBuilder(newStr).reverse().toString();  
		return newStr.equals(reverseStr);
	}

}

자바의 StringBuilder의 메서드 활용하여 풀었다. 이 문제는 예전에 다른 곳에서 본 기억이 살짝 있다. 당시엔 StringBuilder 클래스를 잘 활용하지 못하고 직접 순회하였었다. 이 문제의 카테고리가 Two Pointers인 이유는 각 문자열를 비교하는 것에 이유가 있다. 하지만 자바의 경우 해당 클래스의 메서드를 활용하면 위와 같이 쉽게 해결 가능하다.

https://leetcode.com/problems/two-sum/description/

두 값의 합이 Target과 일치하는 인덱스를 배열로 반환하는 문제이다.
알고리즘이 필요하기보다. 배열을 다룰 수 있는 지에 가까운 문제였다.

class Solution {
public int[] twoSum(int[] nums, int target){  
    for(int i = 0; i < nums.length; i++){  
        for(int j = i + 1; j < nums.length; j++){  
            if(nums[i] + nums[j] == target){  
                return new int[]{i, j};  
            }  
        }  
    }  
	return null;  
}

문제에서 반드시 하나의 답이 존재한다고 조건을 주어서 순회가 끝난 경우 null 로 처리하였다.
Exception으로 처리하려 하였으나 리트코드에서는 문제에서 별도의 익셉션 처리를 할 수 없는 듯 하였다. throws Exception 메세지를 추가하자 아래와 같은 오류가 발생하였다.

Line 7: error: unreported exception Exception; must be caught or declared to be thrown [in __Driver__.java] int[] ret = new Solution().twoSum(param_1, param_2); ^

로드맵의 첫 문제라서 그런지 굉장히 쉬웠다.