알고리즘 괄호 풀기
프로그래머스 올바른 괄호
문자열 함수
•
s.contains(”a”) : String s 내에 “a” 문자열이 존재하면 true, 존재하지 않으면 false를 반환한다.
•
s.indexOf(”a”) : String s 내에 “a” 문자열이 등장하는 첫번째 index를 반환하고, 없으면 -1을 반환한다.
•
s.replace(”a”, ””) : String s 내에 “a” 문자열 자리를 “”로 대체한다.
•
s.replaceAll(”a”, ””) : String s 내에 “a” 문자열 자리를 “”로 대체한다. (정규 표현식을 인자로 사용가능)
정규 표현식
public static void main(String[] args) {
String str = "1q2w3e4r";
str = str.replaceAll("[0-9]","");
System.out.println(str);
}
// 출력 qwer
Java
복사
1. indexOf 함수 사용
boolean solution(String s) {
while (s.indexOf("()") >= 0) {
s = s.replace("()","");
}
return s.length() == 0;
}
Java
복사
2. split 함수 사용
boolean solution2(String s) {
while (s.indexOf("()")>=0) {
String[] split = s.split("\\(\\)");
s = String.join("",split);
}
return s.length() == 0;
}
Java
복사
3. stack 사용
boolean solution3(String s) {
Stack<Character> st = new Stack<>();
for (int i = 0; i < s.length(); i++) {
if ('(' == (s.charAt(i))) {
st.push(s.charAt(i));
} else if (')' == (s.charAt(i))) {
if(st.empty()) return false;
st.pop();
}
}
return st.empty();
}
Java
복사
함수 비교
indexOf(), split() 함수를 사용하는 방식은 시간 복잡도가 O(N^2)
stack을 사용하는 방식은 시간 복잡도가 O(N)
stack을 사용하는 방식이 시간 복잡도를 줄일 수 있다.
알고리즘 - 정희준
괄호문제 풀기 알고리즘
괄호가 바르게 짝지었다는 것은 '(' 문자로 열렸으면 반드시 짝지어서 ')'문자로 닫혀야 한다는 뜻 입니다. '(',')'로만 이루어진 문자열이 입력으로 들어올때 괄호가 바르게 짝지어져 있다면 true를 아니라면 false를 반환하시오.
replace,indexOf 메서드를 사용하여 해결하는 방법
해결 아이디어
먼저 입력되는 문자열에서 indexOf 메서드를 사용하여 "()"가 문자열에 포함되어 있다면 위치 인덱스를 반환하여 replace 메서드를 이용해 문자열에서 "()" 를 ""으로 변경하고 반복하여 만약 이제 없다면 indexOf 를 사용한 메서드가 -1를 반환해 반복문을 탈출하게 됩니다. 반복문을 탈출한 문자열의 길이가 0이라면 true를 반환하고 0이 아니라면 false를 반화해주는 아이디어 입니다. 아래는 아이디어를 구현한 코드 입니다.
먼저 입력되는 문자열에서 indexOf 메서드를 사용하여 "()"가 문자열에 포함되어 있다면 위치 인덱스를 반환하여 replace 메서드를 이용해 문자열에서 "()" 를 ""으로 변경하고 반복하여 만약 이제 없다면 indexOf 를 사용한 메서드가 -1를 반환해 반복문을 탈출하게 됩니다. 반복문을 탈출한 문자열의 길이가 0이라면 true를 반환하고 0이 아니라면 false를 반화해주는 아이디어 입니다. 아래는 아이디어를 구현한 코드 입니다.public boolean sovwBracketReplace(String i) {
while (i.indexOf("()") >= 0) {
i = i.replace("()", "");
}
return i.length() == 0;
}
Java
복사
하지만 이 방법은 효율성 테스트에서 떨어지기 때문에 오답으로 처리 됩니다.
split,join 메서드를 사용하여 해결하는 방법
해결 아이디어
먼저 입력되는 문자열에서 indexOf 메서드를 사용하여 "()"가 문자열에 포함되어 있다면 위치 인덱스를 반환하여 split 메서드를 사용하여 "()"을 기준으로 배열로 나누고 그 배열을 다시 join 메서드를 이용하여 문자열을 합쳐 줍니다. 반복문을 계속 반복하여 문자열 안에 "()"가 없어 indexOf 메서드가 -1 을 반환할때까지 반복 해 줍니다. 그 후 반복문을 탈출한 문자열의 길이가 0이라면 true를 반환하고 0이 아니라면 false를 반환해주는 아이디어 입니다. 아래는 아이디어를 구현한 코드 입니다.
먼저 입력되는 문자열에서 indexOf 메서드를 사용하여 "()"가 문자열에 포함되어 있다면 위치 인덱스를 반환하여 split 메서드를 사용하여 "()"을 기준으로 배열로 나누고 그 배열을 다시 join 메서드를 이용하여 문자열을 합쳐 줍니다. 반복문을 계속 반복하여 문자열 안에 "()"가 없어 indexOf 메서드가 -1 을 반환할때까지 반복 해 줍니다. 그 후 반복문을 탈출한 문자열의 길이가 0이라면 true를 반환하고 0이 아니라면 false를 반환해주는 아이디어 입니다. 아래는 아이디어를 구현한 코드 입니다.public boolean solution2(String s){
while (s.indexOf("()") >= 0) {
String[] splitted = s.split("\\(\\)");
s = String.join("",splitted);
}
return s.length() == 0;
}
Java
복사
stack 이용
public class StackSolveBracket {
public boolean solution(String s) {
Stack<Character> st = new Stack<>();
for (int i = 0; i < s.length(); i++) {
if ('(' == s.charAt(i)) {
st.push(s.charAt(i));
} else if (')' == s.charAt(i)) {
st.pop();
}
}
return st.empty();
}
}
Java
복사
위의 코드로 작성하면 문제가 없이 잘 해결된다고 할 수 있다.
하지만 만약 입력되는 문자열이 )()인 경우 스택이 비어있는데 pop 메서드가 호출되어 EmptyStackException 오류가 난다. 해결하기 위해 다시 코드를 작성하면
public class StackSolveBracket {
public boolean solution(String s) {
Stack<Character> st = new Stack<>();
for (int i = 0; i < s.length(); i++) {
if ('(' == s.charAt(i)) {
st.push(s.charAt(i));
} else if (')' == s.charAt(i)) {
if(st.empty()) return false;
st.pop();
}
}
return st.empty();
}
}
Java
복사
코드를 설명하자면 ")"일때 st.empty() 이면 짝이 맞지 않는 경우이기 때문에 false를 리턴 해 줍니다.
Spring
리팩토링,테스트를 하는 이유
지금까지 UserDao 클래스에 코드를 작성하면서 Connection,PrereparedStatement,ResultSet 등을 close 해주었다. 가끔 너무 큰 프로그램을 개발하다 보면 이것들 중 close를 해주지 않아 회수하지 못하고 메서드가 종료되는 경우가 있다. 한 두개 정도 깜빡한 상황에서는 사실 프로그램을 돌려보면 큰 문제가 안 생긴다. 하지만 해당 메소드가 호출되고 나면 커넥션이 점점 쌓여 가는데 지속되면 서버가 종료되는 상황이 생길 수 있다.
전략 패턴 - 조예지
전략패턴 (p.216)
이전의 코드의 문제점
•
try/catch/finally 예외상황 처리는 완료되었다. 그러나 UserDao의 모든 메소드마다 복잡한 블록이 나온다.
•
이러한 복잡한 코드의 반복은 Human Error의 가능성을 높이고, 유지/보수 또한 어렵게한다.
문제 해결의 핵심은 변하지 않으며 많은 곳에서 중복되는 코드와 로직에 따라 확장되고 변하는 코드를 분리해내는 것이다.
⭕️ 분리와 재사용을 위한 디자인 패턴 적용
•
PreparedStatement를 만들어서 업데이트용 쿼리를 실행하는 메소드라면 deleteAll() 메소드와 구조의 거의 비슷할 것이다.
•
아래의 deleteAll(), add() 두 메서드에서 노란색 박스 안의 부분은 동일한 구조를 갖는다.
•
deleteAll()에서 가운데 부분만 수정하면 add()를 만들 수 있다.
deleteAll()
add()
○ 전략 패턴이란?
•
오브젝트를 아예 둘로 분리하고 클래스 레벨에서는 인터페이스를 통해서만 의존하도록 만드는 전략 패턴이다.
•
확장에 해당하는 부분을 별도의 클래스로 만들어 추상화된 인터페이스를 통해 위임하는 방식이다.
•
Context의 contextMethod()에서 일정한 구조를 가지고 동작하다가 특정 확장 기능은 Strategy 인터페이스를 통해 외부의 독립된 전량 클래스에 위입하는 것이다.
○ 전략 패턴의 장점
개방 폐쇄 원칙 (OCP)을 잘 지키는 구조이면서도 유연하고 확장성이 뛰어나다.
○ 전략 패전의 적용
Strategy interface•
이를 deleteAll()에 적용하면, 앞에서 보았듯이 deleteAll()의 context 중에서 Preparement를 만드는 부분만이 변하는 부분이다.
•
따라서 이를 외부 기능 (전략) 으로 만들어서 호출할 것이다.
•
변하는 부분을 인터페이스로 만들어두고 인테페이스의 메소드를 통해 PreparedStatement 생성을 호출한다.
•
context가 만들어 둔 connection을 받아서 PreparedStatement 오브젝트를 반환하는 메소드를 가진 인터페이스를 만들다.
public interface StatementStrategy {
PreparedStatement makePreparedStatement (Connection c) throws SQLException;
}
Java
복사
DeleteAllStatement AddStatement Context method•
context가 어떤 전략을 사용할 것인지는 context를 사용하는 앞단의 client가 결정하는 것이 일반적이다.
•
client가 구체적인 전략을 선택하고 오브젝트로 만들어서 context에 전달한다.
•
Context method는 clinet로부터 StatementStrategy 타입의 전략 오브젝트를 제공받는다. 그리고 제공받은 오브젝트는 PreparedStatement 생성이 필요한 시점에 호출해서 사용한다.
•
메소드로 분리한 context codepublic void jdbcContextWithStatementStrategy(StatementStrategy stmt) throws SQLException {
Connection conn = null;
PreparedStatement ps = null;
try {
conn = connectionMaker.makeConnection();
ps = stmt.makePreparedStatement(conn);
ps.executeUpdate();
} catch (SQLIntegrityConstraintViolationException e) {
throw new SQLIntegrityConstraintViolationException(e);
} catch (SQLException e) {
throw e;
} finally {
if(ps != null){
try {
ps.close();
} catch (SQLException e) {
}
}
if (conn != null) {
try {
conn.close();
} catch (SQLException e) {
}
}
}
}
Java
복사
client•
컨텍스트를 별도의 메소드로 분리했으니 deleteAll() 메소드가 클라이언트가 된다.
•
deleteAll()은 전략 오브젝트를 만들고 컨텍스트를 호출하는 책임을 가지고 있다.
public void deleteAll() throws SQLException {
jdbcContextWithStatementStrategy(new DeleteAllStatement());
}
Java
복사
•
add() 메소드는 user 정보를 생성자를 통해 전달해준다.
public void add(User user) throws SQLException {
AddStatement addStatement = new AddStatement(user);
jdbcContextWithStatementStrategy(addStatement);
}
Java
복사
비록 클라이언트와 컨텍스트는 클래스를 분리하지 않았지만, 의존관계과 책임으로 볼 때 이상적인 클라이언트/컨택스트 관계를 갖고 있다.
특히 클라이언트가 컨택스트가 사용할 전략을 정해서 전달한다는 면에서 DI 구조라고도 할 수 있다.
