주식의 판매 금액을 배열로 주고 가장 이득을 보는 경우의 이익 값을 찾는 문제이다. 배열의 인덱스를 적절하게 조절하여 문제를 풀어야 했다.
가장 쌀 때 사서 비싸게 파는 경우를 찾는 문제이므로, 파는 것을 기준으로 순회 하였으면, 값을 체크해서 가장 낮은 금액일 경우 해당 금액을 사는 날로 변경하였다.
시간의 개념이 들어가므로 파는 날짜보다 사는 날짜가 이전에 있어야 하기 때문에 무작정 최소 값을 사는 기준으로 하는 것이 아니라 파는 날짜를 순회해서 기준이 되는 날짜를 찾았다.
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;
}
}
이진탐색 알고리즘을 알고있는지 체크하는 문제로 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문을 탈출하지 못하는 실수를 할 때가 많다.
다행히 해당 문제는 조건이 까다롭지 않고 기초적인 이진탐색을 요구하기에 이진탐색을 입문하기 좋은 문제였다.
문자열의 "palindrome" 이라는 조건을 알려주고 해당 조건에 맞는지 여부를 boolean으로 리턴하는 문제이다.
palindrome의 조건은 다음과 같다.
대문자를 소문자로 바꾼다.
non-alphanumeric 문자를 지운다.
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인 이유는 각 문자열를 비교하는 것에 이유가 있다. 하지만 자바의 경우 해당 클래스의 메서드를 활용하면 위와 같이 쉽게 해결 가능하다.
두 값의 합이 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;
}
}
코딩테스트, 알고리즘을 위한 사이트들이 있는데 그 중 내가 이용하는 것은 프로그래머스와 백준 사이트이다.
프로그래머스의 경우 자체적으로 코드 실행을 할 수도 있고, 코드 실행중에 System.out.println 을 이용하여 디버깅도 나름 가능하다.
하지만 백준의 경우 디버깅을 하기가 힘들다. 또한 문제를 풀다가 왜 틀렸는지 알 수 없어 질문하기 쪽을 보다 보니 input 데이터에 공백이 들어가 있는 것 같다는 대답을 들은 적도 있다. 실제로 공백을 처리하는 로직을 추가하였더니 통과된 경험도 있다.
그래서 공백까지 들어가있는 테스트 데이터를 만들거나, InputStream 으로 input 데이터가 들어오는 문제를 실행 및 테스트를 할 수 있는 코드를 만들었고 이를 공유하고자 이 글을 포스트한다. 해당 코드는 아래와 같다.
import java.io.*;
import java.lang.reflect.InvocationTargetException;
import java.net.URL;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.concurrent.atomic.AtomicBoolean;
public class Main {
public static void main(String[] args) throws Exception {
test(new Form());
}
private static void test(Object problem) throws Exception {
URL classDir = problem.getClass().getResource("");
File[] files = new File(classDir.toURI()).listFiles();
// Result 저장
Map<String, String> result = new HashMap();
Arrays.stream(files).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 (FileNotFoundException e) {
throw new RuntimeException(e);
} catch (IOException e) {
throw new RuntimeException(e);
}
});
AtomicBoolean isSuccess = new AtomicBoolean();
isSuccess.set(true);
// Input 실행
Arrays.stream(files).forEach(file -> {
String fileName = file.getName();
boolean isInput = fileName.startsWith("input");
if(isInput){
String testSeq = fileName.substring(fileName.indexOf("input") + "input".length(), fileName.lastIndexOf("."));
System.out.println("** " + testSeq + "번 테스트 실행 **");
try {
long startTime = System.nanoTime();
String testResult
= (String) problem.getClass()
.getDeclaredMethod("solution", InputStream.class)
.invoke(problem, new FileInputStream(file));
long endTime = System.nanoTime();
System.out.println("실행시간: " + (endTime-startTime)/1_000_000.00 +"ms");
System.out.println();
String expectResult = result.get(testSeq);
System.out.println("정답");
System.out.println(expectResult);
System.out.println();
System.out.println("결과");
System.out.println(testResult);
System.out.println();
if(testResult.equals(expectResult)){
System.out.println(testSeq + "번 테스트 성공");
isSuccess.set(isSuccess.get());
}else{
System.out.println(testSeq + "번 테스트 실패");
isSuccess.set(false);
}
} catch (IllegalAccessException | FileNotFoundException e) {
throw new RuntimeException(e);
} catch (NoSuchMethodException e) {
System.out.println("solution 메서드가 없습니다");
throw new RuntimeException(e);
} catch (InvocationTargetException e) {
e.printStackTrace();
throw new RuntimeException(e);
}
System.out.println("=======================================================================================");
}
});
if(isSuccess.get()){
System.out.println("모든 테스트가 통과하였습니다.");
}else{
System.out.println("************** 실패한 테스트가 있습니다. 결과를 확인해주세요 **************");
}
}
}
해당 코드를 활용하기 위해서는 우선 문제 풀이를 작성할 Form 클래스(클래스 이름은 문제마다 또는 원하는 형태)를 하나 만든다.
import java.io.BufferedReader;
import java.io.InputStream;
import java.io.InputStreamReader;
public class Form {
public String solution(InputStream systemIn) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(systemIn));
StringBuilder result = new StringBuilder();
// 문제풀이코드
System.out.println(result);
return result.toString();
}
}
문제 풀이 코드는 위와 같은 형태로 작성한다. 테스트 데이터는 input1.txt, result1.txt 형태로(input/result + 케이스 번호) 텍스트 파일을 만들어 문제 풀이 클래스와 동일한 디렉토리에 저장한다. 아래와 같은 형태면 된다.
프로젝트 루트 ├── package1 │ ├── 문제1 Class │ └── input1.txt │ └── input2.txt │ └── input3.txt │ └── result1.txt │ └── result2.txt │ └── result33.txt ├── package2 │ ├── 문제2 Class │ └── input1.txt │ └── result1.txt └── Main
if(isSuccess.get()){
System.out.println("모든 테스트가 통과하였습니다.");
}else{
System.out.println("************** 실패한 테스트가 있습니다. 결과를 확인해주세요 **************");
}
테스트 코드의 성공 여부에 따라 위와같은 멘트가 콘솔창에 출력된다. 폴더 구조 및 출력멘트는 Main 클래스에서 입맛에 맞게 변경하면 될 것이다.
백준에 제출하기 전에 내 PC 에서 실행하던 클래스를 적절히 변경 후 제출하면 된다.
// 실행환경 패키지 이름 제거
import java.io.BufferedReader;
import java.io.InputStream;
import java.io.InputStreamReader;
// public class Form { 임의의 클래스명 -> Main
public class Main {
// public String solution(InputStream systemIn) throws Exception{
public static void main(String[] args) throws Exception{
// systemIn => System.in
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder result = new StringBuilder();
// 문제풀이코드
System.out.println(result);
// return result.toString();
}
}
package 이름 제거
클래스 이름 Main 으로 변경,
main 메서드 이름 변경
return 제거 후 정답 코드 출력(System.out.println 이 아니라 BufferWriter 등을 사용해도 된다.)
이후 런타임 오류가 없는데 문제가 틀린다면 문제를 다시 풀어보도록 하면된다. 열공하는 사람 모두 화이팅!
