오늘 할일
1. LeetCode
2. 창엔 2차 성적반영 및 3차 공지방 초대
3. 대기업 과제 출력
4. 인공지능 개론 다음 실습 준비 및 수업 중 실습 파일 실행 후 github 업로드, 교재 질의 인공지능 Exprerss? 혼자배우는 머신러닝 딥러닝? 전자! 구매하자. 인공지능 과제 절편의 의미 편향? 추가할까 말까
5. 노트북 포맷?
오늘 한일
2. 3차 공지방은 확인해보닌 이전에 미리 해뒀고, 4차 공지방은 학과 변경으로 인해 나중에 초대.
- LeetCode
- Decode String을 오늘엔 꼭 마무리해보도록 하자.
자체 case1 디버깅을 통해 ]]처럼 연속으로 닫힐 경우 .repeat을 수행하게끔 예외처리 코드 추가하여 pass
- Decode String을 오늘엔 꼭 마무리해보도록 하자.
else if(c==']'){
char tmp=stack_c.pop();
String target;
if(tmp=='['){
target=result.toString();
int repeat=stack_i.pop();
result.append(target.repeat(repeat-1));
continue;
} else {
target = "";
while (tmp != '[') {
target = tmp + target;
tmp = stack_c.pop();
}
int repeat = stack_i.pop();
result.append(target.repeat(repeat));
}
} 자체 case2 디버깅을 통해 3[a2[c]]와 같은 경우 a+2[c]연산이 수행되지 않는다는 것을 발견. 문제는 stack pop시 나중에 쓰일 3이 a를 만났을 때 발생하는 것을 발견. 이유는 정수를 담는 stack과 문자를 담는 stack을 분리하여 작성했기 때문. 이유는 반복되는 숫자가 10의자리 이상이라면 char단위로 분석하는 현재 코드에서 정확한 반복횟수가 적용되지 않기 때문이었다. 우선 이를 해결하기 위해 stack을 통합할 것인데, integer parsing을 미리 하지 않고 stack pop시 하도록 코드를 수정하고 stack로 통일하여 코드를 재작성해보겠다.
를 시도했으나 코드가 너무 복잡하여 알고리즘을 다시 설계해보기로 했다.
두번째 접근으로 알고리즘을 재설계해보려고 한다. 현재의 자체적인 테스트 케이스는 아래와 같다.
숫자가 나오면 []안의 문자를 반복한다. 이 때 []안의 문자 안에 또 []가 반복될 수 있다. 즉 이를 재귀적으로 처리 가능하다. 이것만 고려하면 첫번째 테스트케이스를 통과할 수 있다. 다음으로 고려해야할 것은 문자열의 덧샘연산인데 위의 2[]꼴을 제외한 나머지들을 전부 덧셈처리하면 될 듯 하다.
숫자[표현식]꼴을 처리하는 재귀함수를 설계하자. 종료조건은 무엇인가? ]을 만났을 때 표현식.repeat(숫자)를 처리한 후 반환.
그 외의 경우 +연산을 진행하다가 [를 만나면 재귀..를 하려했는데 1[2[as]ss4[as]]를 예시로 해보자..재귀함수도 어떻게 접근해야할지 감이 잘 안잡힌다..
세번째 접근으로 기존에 가장 많은 ㅔㅌ스트 케이스를 통과한 코드를 기반으로 TDD개발을 해보기로 했다.
class Solution {
private boolean is_num(char c){ return '0'<=c&&c<='9'?true:false; }
private boolean is_alpha(char c){ return 'a'<=c&&c<='z'?true:false; }
public String decodeString(String s) {
int size=s.length();
/*
숫자 뒤 괄호열림은 *연산, ]뒤 숫자는 +연산, 문자뒤 숫자도 +연산, [없이 문자는 +연산
*/
StringBuilder result=new StringBuilder();
Stack<Integer> stack_i=new Stack<>();
Stack<Character> stack_c=new Stack<>();
StringBuilder integer_parser=new StringBuilder();
for(char c: s.toCharArray()){
if(is_alpha(c)){
stack_c.push(c);
} else if(c=='['){
stack_i.push(Integer.valueOf(integer_parser.toString()));
integer_parser.delete(0, integer_parser.length());
stack_c.push(c);
} else if(c==']'){
char tmp=stack_c.pop();
String target="";
while (tmp!='['){
target=tmp+target;
tmp=stack_c.pop();
}
int repeat=stack_i.pop();
result.append(target.repeat(repeat));
} else if(is_num(c)){
integer_parser.append(c);
} else{
}
}
while (!stack_c.isEmpty()){
char tmp = stack_c.pop();
result.insert(0, tmp);
}
return result.toString();
}
} 
14까지의 테스트케이스를 통과했다.
숫자가 나왔을 때 이전에 붙어있는 알파벳이 있다면 append하는 코드 추가
private boolean is_num(char c){ return '0'<=c&&c<='9'?true:false; }
private boolean is_alpha(char c){ return 'a'<=c&&c<='z'?true:false; }
public String decodeString(String s) {
StringBuilder result=new StringBuilder();
Stack<Integer> stack_i=new Stack<>();
Stack<Character> stack_c=new Stack<>();
StringBuilder integer_parser=new StringBuilder();
String target="";
for(char c: s.toCharArray()){
if(is_alpha(c)){
stack_c.push(c);
} else if(c=='['){
target="";
stack_i.push(Integer.valueOf(integer_parser.toString()));
integer_parser.delete(0, integer_parser.length());
stack_c.push(c);
} else if(c==']'){
char tmp=stack_c.pop();
while (tmp!='['){
target=tmp+target;
tmp=stack_c.pop();
}
int repeat=stack_i.pop();
result.append(target.repeat(repeat));
} else if(is_num(c)){
if(!stack_c.isEmpty() && is_alpha(stack_c.peek())){
result.append(stack_c.pop());
}
integer_parser.append(c);
}
}
return result.toString();
} 
중간백업 자체케이스 3개통과. 하지만 여전히 어떻게 접근해야할지 난해하다..
네번째 접근으로, 아예 효율성을 버리고 직관적인 방법을 택하고자 일반 표현식으로 변환, 후위 표기식으로 변환, 계산 순서로 코드를 짜보았다.
class Solution {
private boolean is_num(char c){ return '0'<=c&&c<='9'?true:false; }
private boolean is_alpha(char c){ return 'a'<=c&&c<='z'?true:false; }
private int priority(char ch){
switch (ch){
case '(': case ')':
return 0;
case '+':
return 1;
case '*':
return 2;
}
return -1;
}
public String decodeString(String s) {
char[] origin=s.toCharArray();
StringBuilder expression=new StringBuilder();
StringBuilder integer_parser=new StringBuilder();
for(int i=0; i<origin.length; i++){
char c=origin[i];
if(is_alpha(c)){
expression.append(c);
if(i+1<origin.length && is_alpha(origin[i+1]))
expression.append('+');
} else if(is_num(c)){
if(i-1>=0 && is_alpha(origin[i-1]))
expression.append('+');
integer_parser.append(c);
while(is_num(origin[++i])){
integer_parser.append(origin[i]);
}
i--;//for i++ after for loop
expression.append(Integer.valueOf(integer_parser.toString()));
integer_parser.delete(0, integer_parser.length());
expression.append('*');
} else if(c=='['){
expression.append('(');
} else if(c==']'){
expression.append(')');
if(i+1<origin.length && origin[i+1]!=']')
expression.append('+');
}
}
System.out.println("normal expression: "+expression.toString());
StringBuilder post_expression=new StringBuilder();
Stack<Character> stack=new Stack<>();
//step 2
for(char c : expression.toString().toCharArray()){
switch(c){
case '+': case'*':
while(!stack.isEmpty() && (priority(c)<=priority(stack.peek())))
post_expression.append(stack.pop());
stack.push(c);
break;
case '(':
stack.push(c);
break;
case ')':
char top_op=stack.pop();
while(top_op!='('){
post_expression.append(top_op);
top_op=stack.pop();
}
break;
default:
post_expression.append(c);
break;
}
}
while(!stack.isEmpty()){
post_expression.append(stack.pop());
}
System.out.println("post_expression: "+post_expression.toString());
//step3
Stack<String> stringStack=new Stack<>();
String op1, op2;
for(char c: post_expression.toString().toCharArray()){
String c_s=""+c;
if(!c_s.equals("+") && !c_s.equals("*")){
stringStack.push(c_s);
} else{
op2= stringStack.pop();
op1= stringStack.pop();
if(c_s.equals("+")){
stringStack.push(""+op1+op2);
} else if(c_s.equals("*")){
stringStack.push(op2.repeat(Integer.valueOf(op1)));
}
}
}
System.out.println("result: "+stringStack.peek());
return stringStack.pop();
}
} 
숫자를 제대로 Parsing하는 부분만 수정하면 될 듯 하다.
