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하여 반환하였다.
주어진 커스텀 클래스인 이진트리 노드를 레벨에 따른 중첩 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에 새로 넣기 때문에 하나의 레벨을 빼내기 전에 사이즈를 체크해서 꺼내면 된다.
주식의 판매 금액을 배열로 주고 가장 이득을 보는 경우의 이익 값을 찾는 문제이다. 배열의 인덱스를 적절하게 조절하여 문제를 풀어야 했다.
가장 쌀 때 사서 비싸게 파는 경우를 찾는 문제이므로, 파는 것을 기준으로 순회 하였으면, 값을 체크해서 가장 낮은 금액일 경우 해당 금액을 사는 날로 변경하였다.
시간의 개념이 들어가므로 파는 날짜보다 사는 날짜가 이전에 있어야 하기 때문에 무작정 최소 값을 사는 기준으로 하는 것이 아니라 파는 날짜를 순회해서 기준이 되는 날짜를 찾았다.
public class Solution {
public int maxProfit(int[] prices) {
int maxProfit = 0;
int minPrice = prices[0];
int buy = 0;
// 매일 파는 값을 체크, 사는 지점은 값(minPrice)이 가장 낮은 지점일 때
for(int sell = 1; sell < prices.length; sell++){
int buyPrice = prices[buy];
int sellPrice = prices[sell];
int curProfit = sellPrice - buyPrice;
// 최저가일 경우 구매점으로 변경
if(sellPrice < minPrice){
buy = sell;
minPrice = sellPrice;
continue;
}
maxProfit = Math.max(curProfit, maxProfit);
}
return maxProfit;
}
}
주어진 문자열의 괄호들이 제대로 닫혀있는지 물어보는 문제이다. 정상적으로 닫혀 있다면 순서대로 닫혀야 하므로 스택을 이용한 문제이다. 스택을 공부할 때 가장 기본적으로 나오는 문제이다. 사실 이와 같은 형태의 문제를 보았을 때 처음 보는 경우에는 왜 스택이 필요한지 이해가 되지 않을 수도 있다.
스택의 개념을 머리에 넣고 주어진 문자열을 차례대로 넣었다가 빼는 것을 확인해 보면 마지막에 넣은 것을 먼저 빼는 스택의 성질이 괄호를 정확히 순서대로 닫아준다는 것을 확인할 수 있다. 아래는 문제를 해결한 코드이다.
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의 값을 닫는 형태인지 체크하고 있다.
두 값의 합이 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); ^
코딩테스트의 대표 사이트인 백준과 프로그래머스의 문제에는 형식에 차이가 있다. 백준의 경우 테스트로 입력되는 파라미터가 System.in으로 입력되고, 정답의 경우 출력을 통하여 문제를 푼다면. 프로그래머스의 경우에는 solution 함수를 만들고, 해당 solution 함수의 파라미터로 테스트 케이스가 입력되고, 정답의 경우 return 값으로 처리 된다.
첫 줄에 남겨둔 링크인 이전 코드의 경우 백준을 고려하여 만들다보니 프로그래머스의 문제풀이 테스트 결과를 확인할 수 없는 문제가 있었다. 프로그래머스의 테스트 케이스를 문자열로 하여 적절하게 타입 변환 해주는 코드들을 작성할 수도 있었겠지만 Jackson 라이브러리 등을 붙이는 것이 아니면 과한 작업 소요라고 생각하였고, HashMap을 통하여 테스트 케이스 및 결과 케이스를 저장하는 형태로 테스트 환경을 구축하였다.
또한 실제 사이트에 제출 전 IDE에서 작성한 부분을 수정하는 작업을 최대한 적게 줄일 수 있도록 코드를 작성하였다.
백준과 프로그래머스의 두 케이스로 나누기 위해 전략패턴을 사용하고자 하였고, 우선 한 일은 문제에 대한 Interface 화이다.
백준과 프로그래머스에서 달라지는 케이스인 InputCase 와 ResultCase 를 구현 체에서 작성하게 하였고 test() 자체는 동일하게 구성하였다. 틀렸을 경우 확인하기 쉽도록 GPT의 도움을 받아 console 창에 색상과, 소리가 나는 코드를 추가하였다. 또한 케이스를 프린트 해볼 경우 Array 안의 다른 Object 가 있는 경우가 있어 print 관련하여서도 메서드를 추가하였다. 프로그래머스의 경우 input 과 return 의 타입이 변경될 수 있어서 제네릭을 이용하였다.
아래는 BaekJoon과 Programmers에서 Interface 메서드들을 구현한 내용들이다.
class BaekJoon
import java.io.*;
import java.lang.reflect.Constructor;
import java.net.URL;
import java.util.Arrays;
import java.util.HashMap;
public class BaekJoon implements Problem<File, String>{
Object answer;
File[] testFiles;
public Problem<File, String> setAnswer(Object answer) {
this.answer = answer;
URL classDir = answer.getClass().getResource("");
try{
testFiles = new File(classDir.toURI()).listFiles();
}catch (Exception e){
e.printStackTrace();
throw new RuntimeException(e);
}
return this;
}
@Override
public HashMap<String, File> getInputCase() {
HashMap<String, File> testCase = new HashMap<>();
Arrays.stream(testFiles)
.filter((file) -> file.getName().startsWith("input"))
.forEach(file -> {
String fileName = file.getName();
String testSeq = fileName.substring(fileName.indexOf("input") + "input".length(), fileName.lastIndexOf("."));
testCase.put(testSeq, file);
});
return testCase;
}
@Override
public HashMap<String, String> getResultCase() {
HashMap<String, String> result = new HashMap<>();
try {
Arrays.stream(testFiles)
.filter((file) -> file.getName().startsWith("result"))
.forEach(file -> {
String fileName = file.getName();
String testSeq = fileName.substring(fileName.indexOf("result") + "result".length(), fileName.lastIndexOf("."));
StringBuilder resultSb = new StringBuilder();
try {
BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream(file)));
String line = "";
while ((line = br.readLine()) != null) {
resultSb.append(line).append(System.lineSeparator());
}
result.put(testSeq, resultSb.toString().trim());
} catch (IOException e) {
throw new RuntimeException(e);
}
});
} catch (Exception e) {
throw new RuntimeException(e);
}
return result;
}
@Override
public String solve(File file) throws Exception {
InputStream parameter = new FileInputStream(file);
System.setIn(parameter);
ByteArrayOutputStream resultOutputStream = new ByteArrayOutputStream();
PrintStream resultSave = new PrintStream(resultOutputStream);
PrintStream resultConsole = System.out;
System.setOut(resultSave);
// Solution class 변수 초기화를 위해 solve 마다 새로운 instance 생성
Constructor constructor = answer.getClass().getConstructor();
Object instance = constructor.newInstance();
instance.getClass()
.getDeclaredMethod("main", String[].class)
.invoke(instance, (Object) null);
System.out.flush();
String testResult = resultOutputStream.toString().trim(); // System.out.println() 으로 정답 입력시 개행문자 제거
resultOutputStream.close();
parameter.close();
System.setOut(resultConsole);
return testResult;
}
}
