Step-by-Step
[Java] 프로그래머스 - 표편집 본문
https://programmers.co.kr/learn/courses/30/lessons/81303
코딩테스트 연습 - 표 편집
8 2 ["D 2","C","U 3","C","D 4","C","U 2","Z","Z"] "OOOOXOOO" 8 2 ["D 2","C","U 3","C","D 4","C","U 2","Z","Z","U 1","C"] "OOXOXOOO"
programmers.co.kr
밑에 설명과 같은 그림이 들어오면 명령어에 따라 선택된 행 이동, 삭제, 복구 작업을 수행한다.
처음에는 효율성 생각 안하고 정확도만 따지기 위해 다음과 같은 방법을 이용했는데,
결론부터 말하면 정확도, 효율성 모두 통과 못한다.
[통과 못한 코드]
import java.util.*;
class Solution {
public String solution(int n, int k, String[] cmd) {
StringBuilder sb = new StringBuilder();
Stack<Integer> removed = new Stack<>();
ArrayList<String> arr = new ArrayList<String>();
for(int i=0; i<n; i++){
arr.add(Integer.toString(i));
}
for(String s : cmd){
char ch = s.charAt(0);
switch(ch){
//up : index 작아짐
case 'U':{
int num = s.charAt(2)-'0';
for(int i=0; i<num && k>0;i++){
if(arr.get(k).equals("-")){
i--;
}
k--;
}
break;
}
//down : index 커짐
case 'D':{
int num = s.charAt(2)-'0';
for(int i=0; i<num && k<arr.size()-1;i++){
if(arr.get(k).equals("-")){
i--;
}
k++;
}
break;
}
case 'C':{
removed.push(k);
arr.set(k, "-"); //del 넣어줌
if(k==(arr.size()-1))
k--;
else
k++;
break;
}
default:{
if(removed.size()==0)
break;
int num = removed.pop();
arr.set(num, Integer.toString(num));
}
}
}
for(String s : arr){
if(s.equals("-"))
sb.append("X");
else
sb.append("O");
}
return sb.toString();
}
}
ArrayList를 사용한 이유는 행을 삭제하면 뒤에 있는 요소들의 index가 한 칸씩 당겨지기 때문이었다.
그리고 stack은 대표적인 LIFO 방식이기 때문에 최근에 삭제된 행을 복구할때 유용할거같아서 사용했다.
그러면 복구할때, 앞뒤 숫자를 찾은 후 복구를 해야하기 때문에
삭제시 "-"와 같이 일종의 null을 나타내는 String을 만들어 넣어준 후, removed에 넣어 저장하였다.
근데 이런 방법을 사용하면 정확도는 둘째치고 절대 효율성에서 통과하지 못한다.
행 개수 n <= 1,000,000이고 명령어 개수 200,000이므로 각 명령어당 전체 행 개수를 탐색하게 된다면
효율성을 만족하지 못한다.
출처 : https://technote-mezza.tistory.com/106
위의 방식을 쓰게 되면 O(n^2)의 효율성이 나오게 된다.
여러 해결책이 있는데, 그 중 LinkedList에 대한 이해가 제일 높아 LinkedList를 사용하였다.
LinkedList를 사용하게 되면 삽입, 삭제는 O(1) 이고, 이동은 O(x)이기 때문에 훨씬 효율적이다.
Doubly LinkedList를 사용하여 양방향 노드와 Root와 Tail까지 구현하였고,
만약 현재 Node에서 삭제 요청이 오면 prev와 Next의 정보를 가진 현재 Node를 그대로 Removed Stack에 넣어주고
현재 Node의 앞 뒤를 연결하면 된다!
반대로 최근에 삭제된 Node를 복구하는 요청이 오면 Stack에서 꺼낸 후,
복구할 Node의 prevNode의 next와 Nextnode의 prev부분에 복구할 Node를 넣어주면 다시 연결된다!
이 방식으로 코드를 작성하면 된다. 문제 해결한 코드는 올려도 되는지 잘 모르겠다.. 일단 지웠다.!
카카오 코딩테스트는 블로그에 문제 해설도 많이 있기 때문에 참조하면 좋을 듯 하다..!
https://tech.kakao.com/?s=%EC%BD%94%EB%94%A9%ED%85%8C%EC%8A%A4%ED%8A%B8
Search for "코딩테스트"
카카오는 사람과 사람, 사람과 기술을 한층 가깝게 연결함으로써, 어제보다 더 나은 세상을 만들어 갑니다.
tech.kakao.com
[참조]
'언어 > JAVA' 카테고리의 다른 글
[Java] 백준 15591 - Mootube(Silver) (0) | 2022.06.30 |
---|---|
[Java] 프로그래머스 - 신고 결과 받기 (0) | 2022.05.20 |
[Java] 프로그래머스 - 숫자 문자열과 영단어 (0) | 2022.05.05 |
[JAVA] 백준 - 주사위 굴리기 (0) | 2022.02.18 |
[JAVA] 백준 - 2048(Easy) (0) | 2022.02.15 |