[프로그래머스,java] Level3: 표 편집

 

문제분석:

 

이게 왜 Level3 인지....   기본지식과 각종 라이브러리 사용 + 최적화를 할수있는지를 따지면 레벨 4는 줘도 댈거같다.

 

 

문제는 커맨드가 나열된 문자열  U, D, C ,Z를 보고 명령을 수행한뒤,  원문과 비교하여 O, X를 붙여주는 문제다.

 

솔직히 커맨드대로 명령을 수행하고 원문과 비교해라~ 라는 문제만 풀면 Level2 ~ Level3 수준의 문제다. 

 

하지만 이 문제는 효율성이 매우 빡빡하다.

 

왜 빡빡한지 다음 이유라서 그렇다.

 

1. List 라이브러리를 사용하면 안된다.

 

필자도 처음에  ArrayList나 LinkedList를 사용했는데, 둘 다 쓰면 안된다.

 

ArrayList같은경우에는 "탐색(idx접근)" 이 빠르지만,  수정 삭제는 O(N)이 든다.

 

LinkedList 같은경우에는 "삽입,삭제"가 빠르지만, 탐색(순차탐색)이 O(N)이 든다.

 

이 문제는 사소한  O(N)의 작업을 칼같이 컷낸다....

 

2.String에  "+" 나 "concat()" 금지

 

이 문제에서 마지막 작업은  "O" 나 "X"를 하나씩 붙여주는것이다.

 

str +="O"  나  str +="X" 같은 코드를 짜지않았는가?  본인이그랬다

.

이 행위가  왜 안되냐면,  "+" 나 "concat()"은 아예 새로운 String객체를 생성하고 문자열을 붙힌다.

거기에 추가로 이전 String객체를 GarbageCollector작업도 추가로 든다.

 

기본지식을 다시한번 다져보자..

 

String, int ,long 같은 기본값타입은  값을 수정하면 "복제"가 일어난다. 

 

https://taehoung0102.tistory.com/189

JPA 값타입

 

복제가 일어나므로, 예를들어 "O"를 추가하는 행위가 10000번 일어나면,

10000만번의 생성과 가비지컬렉터 작업이 든다.

 

에이 뭐 이정도면 사소하지않을까요~?

 

사소하지 않는댄다...

 

그래서 불변타입인 String 기본값타입이아닌 

 

복제가 안일어나는 StringBuilder를 사용해야한다.

 

겨우 통과함...

StringBuilder가 있다 라는건 알고는 있었지만 사실 귀찮아서 계속 안쓰고있었다. 

이렇게 눈으로 효율성차이를 보니  진짜 무시 못하겠다.

 

문제풀이

 

효율성에 대해 정리도 마쳤으니 본격적으로 문제 풀이에 들어가겠다.

 

복원을 위한 Stack이 하나 필요하다.

 

lastIdx 를 하나 선언했는데  

 

아까 효율성 설명했을때, List라이브러리는 쓰면 안된다. 

그래서 이와 같은 조건을 체크하기위해 꼭 필요한 변수가 되겟다.

 

원래 원소가 제거되면 행번호가 유지가되지만, 

마지막 idx의 원소가 제거된다면 행번호가 하나 줄어야한다.

 

이 점만 유의하고 코드를 작성하면 남은작업은

 

1. 커맨드대로 시키는대로 코드짜기

 

2.StringBuilder로 마지막 결과문 작성하기

import java.util.*;
class Solution {
    public String solution(int n, int k, String[] cmd) {
        String answer = "";
        Stack<Integer> st = new Stack<>();
        
        int lastIdx= n;
        
        for(int i=0;i<cmd.length;i++){
            
            if(cmd[i].charAt(0)=='U'){
                k-= Integer.valueOf(cmd[i].substring(2));
            }
            else if(cmd[i].charAt(0)=='D'){
                k+=Integer.valueOf(cmd[i].substring(2));
            }
            else if(cmd[i].charAt(0)=='C'){            
                st.push(k);
                lastIdx--;
                if(lastIdx==k){
                    k--;    
                }     
            }
            else{
                int temp=st.pop();              
                lastIdx++;
                if(temp<=k){
                    k++;
                }
            }       
        }
    
       StringBuilder builder = new StringBuilder();
        for(int i=0; i<lastIdx; i++)
            builder.append("O");
        
        while(!st.isEmpty())
            builder.insert(st.pop().intValue(), "X");
        
         answer=builder.toString();
        return answer;
 
    
    }
}