오늘 할일
1. 창의엔트리 4차 학생 초대 및 3차&4차 미설치 학생 개별 연락
2. LeetCode
3. 포맷?
4. 알고리즘 수업 중 실습 과제 제출
- LeetCode
- Decode String 어제 코드에서의 문제를 찾았다. 후위표기식으로 변환하는 과정에서 일반 String타입으로 표현하기에 10의자리를 넘어가는 숫자의 경우 혼동이 발생한다. 그런데 문제는, 이를 List형태로 받지도 못하는 것이 타입을 통일시켜야하는데 문자를 숫자로 변경하면 진짜 숫자가 나왔을 때 문자로 오해할 수 있고, 숫자를 문자로 변경하면..십의자리 이상 숫자에서 혼동이 오는 것을 마찬가지다. 잠시 생각을 가다듬고 새로 시작해야할까? 우선 현재의 코드 백업을 해보자.
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
char[] charr2=expression.toString().toCharArray();
for(int i=0; i< charr2.length; i++){
char c=charr2[i];
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;
char[] charr=post_expression.toString().toCharArray();
for(int i=0; i<charr.length; i++){
String c_s=""+charr[i];
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();
}
}
넘모 어렵다... stack을 제대로 활용하고 있지도 않은데...
인터넷을 통해 검색해보니 연속되는 숫자들 사이에 /같은 토큰을 넣는 방법을 알게되었다.
해당 아이디어를 사용하여 코드를 수정해보자. pop할 시 숫자간의 구분을 /기호를 하게 하였다.
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.print("normal expression: "+expression.toString());
StringBuilder post_expression=new StringBuilder();
Stack<Character> stack=new Stack<>();
//step 2
char[] charr2=expression.toString().toCharArray();
for(int i=0; i< charr2.length; i++){
char c=charr2[i];
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);
if(is_num(c) && i+1< charr2.length && !is_num(charr2[i+1])){
post_expression.append("/");//숫자 끝의 표시
}
break;
}
}
while(!stack.isEmpty()){
post_expression.append(stack.pop());
}
//System.out.print(",\tpost_expression: "+post_expression.toString());
//step3
Stack<String> stringStack=new Stack<>();
String op1, op2;
char[] charr=post_expression.toString().toCharArray();
for(int i=0; i<charr.length; i++){
String c_s=""+charr[i];
if(!c_s.equals("+") && !c_s.equals("*")){
stringStack.push(c_s);
} else{
op2= stringStack.pop();
op1= stringStack.pop();
//특수처리시작
if(op1.equals("/")){
op1=stringStack.pop();//숫자
while(!stringStack.isEmpty()&&is_num(stringStack.peek().charAt(0))){
op1=stringStack.pop()+op1;
}
}
//특수처리종료
if(c_s.equals("+")){
stringStack.push(""+op1+op2);
} else if(c_s.equals("*")){
stringStack.push(op2.repeat(Integer.valueOf(op1)));
}
}
}
//System.out.println(",\tresult: "+stringStack.peek());
return stringStack.pop();
}
}
문자열을 사용하여 문자가 아닌 숫자간의 구분을 하려고하니 도통 아이디어가 떠오르지 않았었는데, 특정 문자를 이용해서 직접 구분자를 만들어 해결할 수도 있다는 새로운 관점을 알 수 있었던 것 같다. 3일?정도 걸린 것 같은데 추가적으로 스택에 대한 공부가 필요해보인다..!
- Number of Recent Calls는 잘 모르겠다ㅋㅋㅋ 큐를 이용하라는데 새로운 형태의 문제 제출 방식이라 우선 감 잡히는대로 이해한대로 가장 간단하게 제출해보았다.
class RecentCounter {
private int current_time;
private final int range=3000;
private List<Integer> requests;
public RecentCounter() {
current_time=0;
requests=new ArrayList<>();
}
private int find_request_count(int t){
int count=0;
for(int request : requests)
if(t-range<=request && request<=current_time)
count++;
return count;
}
public int ping(int t) {
current_time+=t;
requests.add(current_time);
return find_request_count(t);
}
}
나름 10개까지의 테스트케이스를 통과하였다! 비슷하게 이해한 듯 하다.
이제 3학년..