2차원 DP 문제이다. 로봇은 좌상단에서 시작해 우측, 또는 아래로만 이동할 수 있으므로 첫 행, 첫 열은 가는 방법이 한 가지로 고정이다. 해당 조건에서 안쪽 좌표들의 경우 좌측에서 오는 경우와 위에서 오는 경우 두 가지 경우의 합이 해당 좌표로 가는 방법이기에 해당 조건으로 점화식을 세워 문제를 해결할 수 있었다.

public class Solution {  
    public int uniquePaths(int m, int n) {  
        int[][] dp = new int[m][n];  
  
        for(int i = 0; i < m; i++){  
            dp[i][0] = 1;  
        }  
  
        for(int i = 0; i < n; i++){  
            dp[0][i] = 1;  
        }  
  
        for(int i = 1; i < m; i++){  
            for(int j = 1; j < n; j++){  
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];  
            }  
        }  
  
        return dp[m - 1][n - 1];  
    }  
}

 

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

 

Valid Parentheses - LeetCode

Can you solve this real interview question? Valid Parentheses - Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid. An input string is valid if: 1. Open brackets must be closed by the sam

leetcode.com

 

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

 

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

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/

 

Valid Palindrome - LeetCode

Can you solve this real interview question? Valid Palindrome - A phrase is a palindrome if, after converting all uppercase letters into lowercase letters and removing all non-alphanumeric characters, it reads the same forward and backward. Alphanumeric cha

leetcode.com

 

문자열의 "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인 이유는 각 문자열를 비교하는 것에 이유가 있다. 하지만 자바의 경우 해당 클래스의 메서드를 활용하면 위와 같이 쉽게 해결 가능하다.

이 글을 포스트 한 이후 프로그래머스 문제를 실행 테스트 하기 위하여 코드를 리팩토링 하였다. 코딩 테스트를 준비하는 사람일 경우 프로그래머스 또한 연습해야 하는 사이트임에 분명하므로, 이 글이 아닌 링크 걸린 글을 확인하길 바란다.

[백준, 프로그래머스 문제 실행 테스트환경 (JAVA) 만들기 :: 꿀잠 (tistory.com)](https://ygs3004.tistory.com/17)

 


 

코딩테스트, 알고리즘을 위한 사이트들이 있는데 그 중 내가 이용하는 것은 프로그래머스와 백준 사이트이다.

프로그래머스의 경우 자체적으로 코드 실행을 할 수도 있고, 코드 실행중에 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();  
    }  

}

 

  1. package 이름 제거
  2. 클래스 이름 Main 으로 변경,
  3. main 메서드 이름 변경
  4. return 제거 후 정답 코드 출력(System.out.println 이 아니라 BufferWriter 등을 사용해도 된다.)

이후 런타임 오류가 없는데 문제가 틀린다면 문제를 다시 풀어보도록 하면된다.
열공하는 사람 모두 화이팅!

+ Recent posts