(코테) 프로그래머스_표 편집 *Set ,stack

 

 

문제 링크

 

 

https://school.programmers.co.kr/learn/courses/30/lessons/81303?language=java

 

 

 

import java.util.*;

class Solution {
    public String solution(int n, int k, String[] cmd) {
        String answer = "";
        
        //  "U X" 1행 업 선택
        //  "D X" 1행 다운 선택
        //  "C"   삭제후 아래행   , 예외로 아래가 마지막 행이라면 바로 위행 선택
        //  "Z"  가장 최근 삭제된 행을 원래로 복구  //삭제된 목록 스택?
        char[] result = new char[n];
        //기본 O로 다채움.
        Arrays.fill(result,'O');        
        Stack<Integer> stack = new Stack<>();
        
        TreeSet<Integer> set = new TreeSet<>();
        for(int i=0;i<n;i++)  set.add(i);
        
        //실시간 인덱스를 구하는게 광건,.
        int nowIndex = k;
        
        for(String next:cmd){
            String movingType=null;
            int movingIndex=0;
            if(next.contains("U") || next.contains("D")){
                String[] strList=next.split(" ");
                 movingType=strList[0];                
                 movingIndex= Integer.parseInt(strList[1]);
            }else{
                 movingType=next;
            }            
            
            //higer는 업시키는게 아니라 현재 값에서 하나 더 높은거 즉 큰거를 찾아줌. -> 내 시점에서 좌표는 다운임.            
            
            //업
            if("U".equals(movingType)){
                for(int i=0;i<movingIndex;i++){
                    //Integer down = set.higher(nowIndex);
                    Integer up = set.lower(nowIndex);                    
                    if(up==null) break;
                         nowIndex=up;
                }                                
            }
            //다운
            if("D".equals(movingType)){                
               for(int i=0;i<movingIndex;i++){
                      Integer down = set.higher(nowIndex);
                    if(down==null) break;
                        else nowIndex=down;
                }  
            }
            //삭제
            if("C".equals(movingType)){
                /*
                if(nowIndex==set.size()-1){
                    //업에 현재 인덱스 세팅
                    nowIndex--;
                } 
                */
                Integer down = set.higher(nowIndex);
                Integer up = set.lower(nowIndex);
                set.remove(nowIndex);
                stack.push(nowIndex);
                result[nowIndex] = 'X';
                if(down==null) nowIndex=up;
                    else nowIndex=down;                                
            }
            //되돌리기
            if("Z".equals(movingType)){            
                    int pre=stack.pop();
                    set.add(pre);                
                    result[pre] = 'O';                
                //스택에서 꺼내서
                //set에 다시 삽입 자동 순서 정렬
            }                                
        }        
        
        return new String(result);
    }
}

 

 

회고.

 

이번 문제는 비교적 쉬운??? 문제였다. 한번에 풀지는 못함...

-> 우선 구조를 짤때  큰 구조는 쉬웠다.

1. 힙,set,map 중 저장 구조를 사용해서 풀기 

2. 삭제한 인덱스는 stack 에 넣어 나중에 되돌리기시 꺼내기

 

로 큰 틀을 잡고 시작하였다.

 

저장 구조 힙,map,set중에 고민하였다.  처음에는 큐로 배열이나 리스트를 삽입을하여 정렬 기준을 인덱스? 넣어주고 

우선순위큐로 꺼내면서 사용을 할까? 했지만 중간에 있는 인덱스를 꺼내는 상황도 있기에 큐는 맞지 않겠다고 판단. 

그래서 set, List 중 또 고민을 하다가..... List는 특정 조건으로? 정렬이 되지 않으니... 혹은 되더라도 관리가 복잡하거나 모든 값을 뻇다가 넣었다가 시간복잡도가 높아져,  treeSet을 선택하였다. 우선 set이라 중복제거가 되고,순서 보장이된다. treeset이라 오름,내림차순 정렬이 되어 아주 적합했다. 

하지만 treeset에서 원하는 인덱스???를 꺼내고 현재 위치를 관리하는 포인트르 어떻게 할지 고민중 set을 기준으로 현재 인덱스를 기준으로 삼기로 하였다. 그 과정에서 필요한게   set.higher(찾는 인덱스);  set.lower(찾는 인덱스) 라는 set 에 메소드를 찾았다. 

 

set  => { 10 ,11 ,14,25  } 가 포함되고 있음

set.higher(찾는 인덱스)   -> 찾는 인덱스값에서 큰 값중 가장 작은값        ex)  찾는값 set.higher(11)     결과 14   (14,25중 가장 작은값)

set.lower(찾는 인덱스)  -> 찾는 인덱스값에서 작 은중 가장 큰값        ex)  찾는값 set.lower(14)     결과 11  (10,11중 가장 큰값)

 

이다.