문제
https://programmers.co.kr/learn/courses/30/lessons/81303?language=java
업무용 소프트웨어를 개발하는 니니즈웍스의 인턴인 앙몬드는 명령어 기반으로 표의 행을 선택, 삭제, 복구하는 프로그램을 작성하는 과제를 맡았습니다. 세부 요구 사항은 다음과 같습니다
"U X": 현재 선택된 행에서 X칸 위에 있는 행을 선택합니다."D X": 현재 선택된 행에서 X칸 아래에 있는 행을 선택합니다."C": 현재 선택된 행을 삭제한 후, 바로 아래 행을 선택합니다. 단, 삭제된 행이 가장 마지막 행인 경우 바로 윗 행을 선택합니다."Z": 가장 최근에 삭제된 행을 원래대로 복구합니다. 단, 현재 선택된 행은 바뀌지 않습니다.
생각하기
동작 방식을 보고 당연히 LinkedList와 Stack이 필요할 거라고 생각했는데,
Stack은 맞았지만, LinkedList는 필요가 없었다.
그냥 행에 남아있는 값들과 제거 된 행들을 구별해서
출력만 한다면 완벽히 해결이 됬다.
동작
Stack<Integer> backupList = new Stack<Integer>(); // 삭제한 대상을 가지고 있을 backupList
int rowMax_num = n; // 전체 행번호 (행의 최대값)
int cmd_len = cmd.length;행의 생성과 삭제를 구현할 자료구조와 변수를 미리 만들어준다.
최대한의 효율성을 뽑아내기 위해 cmd[] 배열의 길이도 미리 변수로 저장해둔다.
행의 최대번호는 곧 최대크기이기 때문에 rowMax_num도 만들어 준다.
for(int i=0; i<cmd_len; i++) {
st = new StringTokenizer(cmd[i]);
String order = st.nextToken();
if(order.equals("D") || order.equals("U")) {
int X = Integer.parseInt(st.nextToken());
if(order.equals("D")) {
k+= X;
}
else if(order.equals("U")) {
k-= X;
}
}
else if(order.equals("C")) {
backupList.push(k); // 삭제되면 현재 행의 번호를 backupList에 넣음.
rowMax_num--; // 전체 행의 수를 하나 줄임
//전체 행의 수와 현재 행의 번호가 같을 경우, 마지막 행이 삭제가 된것이므로,
// 하나 위의 행을 선택하기 위해 k값을 1줄임
if(k == rowMax_num) {
k--;
}
}
else if(order.equals("Z")) {
// 되돌리기가 마지막 행이 었을경우, 마지막행을 다시 선택해야 함.
// 행 번호를 기준으로 현재 선택한 행 번호를 찾아야 하기 때문에
// 현재 행의 위치가 백업리스트에서 가져온 값보다 크면
// 예를 들어 현재 선택된 행이 4인데, 4행이 백업되면, 현재 선택된 행은 5가 되어야 하므로
// 현재 선택된 행을 올려준다.
if(backupList.pop() <= k) {
k++;
}
// 행이 백업되어서 늘어났으므로 최대 행 번호도 올려준다.
rowMax_num++;
}
}cmd에서 나온 값의 각 명령에 따라 if문으로 동작한다.
U와 D 다음 token이 있으므로 StringTokenizer을 만들어서 따로 X값을 받도록 만들어준다.
C가 동작할 때
C는 현재 행을 삭제해야 한다.
현재 행은 k에 담고 있는데, k위치에 있는 값을 제거한다고 생각하면 된다.
제거 된 행의 값인 k는 backupList에 넣어준다.
그리고 행을 제거해서 행 하나가 줄어들었기 때문에, rowMax_num을 하나 줄여준다.
또 생각해야 할 부분이 전체 행의 수와 현재 행의 번호가 같을 때는
마지막 행이 삭제되었기 때문에 선택하고 있던 행의 위치를 위의 행 위치값으로 수정해주어야 한다.
그래서 k--가 필요하다.
Z가 동작할 때
Z는 되돌리기 이다.
Z는 그냥 backupList에서 pop()을 실행해서 가장 최근에 삭제된 행 번호를 가져오면 된다.
하지만, 현재 행의 위치인 k의 값이 backupList에서 가져온 값 보다 같거나 클 경우
즉, k가 4일 때, 4행이 백업되어서 들어 왔다면, 현재 선택된 행은 다시 뒤의 자리로 돌아가야 하기 때문에 k값을 증가해줘야 한다.
또한, 행이 늘어났으므로 최대 행의 번호 rowMax_num도 증가시켜준다.
sb = new StringBuilder();
for(int i=0; i<rowMax_num; i++) {
sb.append('O');
}
while( !backupList.isEmpty() ) {
sb.insert( backupList.pop().intValue() , 'X');
}
return sb.toString();LinkedList를 사용하지 않고 풀 수 있는 이유는 여기있다.
처음에 LinkedList를 사용해야겠다고 생각했던 이유는 기존에 있던 위치로 들어가야 하기 때문인데,
StringBuilder를 사용하면 이 부분을 완전하게 커버가 가능했다.
처음에 rowMax_num만큼 반복해서 'O'만 sb에 넣어주면 된다.
어차피 rowMax_num의 숫자는 삭제되지 않은 행의 숫자를 의미하기 때문이다.
마지막은 빈자리에 삭제 된 값을 'X'로 넣어주면 되는데
StringBuilder의 insert() 메소드를 사용하면 된다.
insert()메소드에 backupList의 값을 모두 빼내서 해당 값을 index로 사용해서
sb에 'X' 문자로 insert() 해주면 결과를 출력할 수 있다.
코드
import java.util.*; class Solution { public String solution(int n, int k, String[] cmd) { StringTokenizer st = null; StringBuilder sb = null; Stack<Integer> backupList = new Stack<Integer>(); int rowMax_num = n; int cmd_len = cmd.length; for(int i=0; i<cmd_len; i++) { st = new StringTokenizer(cmd[i]); String order = st.nextToken(); if(order.equals("D") || order.equals("U")) { int X = Integer.parseInt(st.nextToken()); if(order.equals("D")) { k+= X; } else if(order.equals("U")) { k-= X; } } else if(order.equals("C")) { backupList.push(k); rowMax_num--; if(k == rowMax_num) { k--; } } else if(order.equals("Z")) { if(backupList.pop() <= k) { k++; } rowMax_num++; } } sb = new StringBuilder(); for(int i=0; i<rowMax_num; i++) { sb.append('O'); } while( !backupList.isEmpty() ) { sb.insert( backupList.pop().intValue() , 'X'); } return sb.toString(); } // End of solution }
