문제링크 : 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
1. 이중연결리스트 2. 인덱스트리 3. 펜윅트리
문제를 가장 단순히 생각해보면, 표의 k번 위치에서 U나 D 입력이 들어왔을 때 U번 이동하면서 제거된 행은 횟수로 포함하지 않고 이동하면 될 것 같다. 또 C 입력에 대해서는 k번 위치의 행을 지우고 맨 아래가 아니면 제거되지 않은 아래행을 가리키도록 하며, Z 입력은 스택에 저장된 지워진 행을 반대로 복구하는 작업을 하면 될 것 같다. cmd에 등장하는 (모든 X들의 합이 1,000,000 이하) 라서 문제 없을 것 같지만 중간에 거의 모든 행을 지운 상태로 U, D 명령어가 들어오는 것을 생각해보면 U 1 명령어에 대해서 10만번 이상 조회하는 경우도 생길 것이다. 명령어 20만 중 10만번을 지우고 10만번을 U,D를 하는 경우를 생각해보자. 어쨌든 배열이 아닌 다른 방법을 생각해봐야 한다.
1. 이중연결리스트 활용
중간 노드의 삽입 삭제가 빈번할 경우 생각해볼 수 있는 간단한 자료구조이다.
(모든 X들의 합이 1,000,000 이하) <= 이 조건에 의해 중간에 삭제된 행이 많더라도 최대 이동은 100만번이다.
따라서 이중연결리스트로 해결할 수 있을 것 같다.
이 방법을 활용할 때 C와 Z 명령어에 유의하며 코드를 짜야한다.이중연결리스트를 직접 구현해본 사람은 삭제 명령어에 대해 포인터를 어떻게 다뤄야할 지 잘 알 것이다.그림을 그려보자면 아래와 같다.
1. 삭제될 노드의 left 노드의 다음(right) 노드로 삭제될 노드의 다음 노드를 가리키도록 한다.
2. 삭제될 노드의 right 노드의 이전(left) 노드로 삭제될 노드의 이전 노드를 가리키도록 한다.
삭제될 노드의 포인터는 그대로 둔다. (Z 명령어에 대해서 설명할 때 이유를 설명)
삭제 코드
public void delete(Node deleteNode){
deleteNode.right.left = deleteNode.left;
deleteNode.left.right = deleteNode.right;
}삭제 후에는 포인터를 다음(right)로 옮겨야한다.
문제의 조건에는 삭제되지 않은 맨 마지막 행일 경우에는 이전, 아닐 경우에는 다음 행을 가리키라 했다.
구현의 편의를 위해 리스트의 head와 tail을 만들었다. 다음이 tail일 경우에는 삭제 후 이전 노드를 가리키도록 한다
else if(query.charAt(0) == 'C'){
arr[pointer.nodeNum] = 1;
deletedNode.push(pointer);
list.delete(pointer);
if(pointer.right == list.tail){
pointer = pointer.left;
}else{
pointer = pointer.right;
}
}위 코드에서 arr 배열은 모든 명령어 수행 후에 어느 노드가 삭제되었고 삭제되지 않았는지를 저장한 배열이다.
N은 100만 이하이므로 배열로 표현 가능하다.
그리고 노드에는 head부터 tail 사이에 있는 노드의 순서대로 nodeNum이 있다.
deletedNode.push(pointer) : deletedNode는 삭제될 노드를 담는 Node 스택이다. Z 명령어 시 복구를 위해 존재한다.
pointer는 노드의 실제 주소를 가리킨다. 따라서 push(pointer)시 해당 노드를 담는다고 할 수 있다.
자, 그럼 노드의 복구를 해보자. deletedNode 스택에는 복구할 노드가 담겨있다.
아래 그림은 1,2,3 순서대로 행을 삭제 했을 때의 포인터 모습이다.
위 순서대로 리스트를 삭제했다고 가정하고 복구를 진행 할 것이다.
3번부터 복구가 시작된다. 가장 간단한 경우이다.
스택에서 꺼낸 노드는 3에서 삭제된 노드이며, 해당 노드는 이미 left,right를 잘 가리키고 있다.
복구노드의 left인 노드의 right는 Tail을 가리키고 있는데 이를 복구노드를 가리키게 바꿔준다.
복구노드의 right인 노드의 left는 복구노드의 left를 가리키고 있다. 이를 복구노드를 가리키게 바꿔준다.
그렇게 하면 맨 밑 그림에서 가운데 그림의 모습이 될 것이다.
다시 이를 반복하면 1번 그림이 될 것이고, 1번에서 복구하면 원상복구 될 것이다.
코드는 아래와 같다
else if(query.charAt(0) == 'Z'){
Node restoration = deletedNode.pop();
arr[restoration.nodeNum] = 0;
restoration.right.left = restoration;
restoration.left.right = restoration;
}전체 코드
전체 코드
import java.util.*;
class Solution {
public static int arr[];
public static class Node{
Node left;
Node right;
int nodeNum; //행 번호
}
public static class DoubleLinkedList{
//문제의 연산을 편리하게 하기 위한 head,tail
Node head;
Node tail;
public void init(int N){
if(head==null){
head= new Node();
tail= new Node();
head.right = tail;
tail.left = head;
}
for(int i=0;i<N;i++){
insert(i);
}
}
public void insert(int num){
Node cur = new Node();
cur.nodeNum = num;
cur.right = tail;
cur.left = tail.left;
tail.left.right = cur;
tail.left = cur;
}
public void delete(Node deleteNode){
deleteNode.right.left = deleteNode.left;
deleteNode.left.right = deleteNode.right;
}
}
public static String solution(int n,int k,String []cmd){
arr = new int[n+1];
StringBuilder ans = new StringBuilder();
Stack<Node> deletedNode = new Stack<Node>();
DoubleLinkedList list = new DoubleLinkedList();
list.init(n);
Node pointer = list.head.right;
for(int i=0;i<k;i++){
pointer = pointer.right;
}
for(int i=0;i<cmd.length;i++){
String query = cmd[i];
if(query.charAt(0) == 'U'){
int cnt = Integer.parseInt(query.substring(2));
for(int j=0;j<cnt;j++){
pointer = pointer.left;
}
}else if(query.charAt(0) == 'D'){
int cnt = Integer.parseInt(query.substring(2));
for(int j=0;j<cnt;j++){
pointer = pointer.right;
}
}else if(query.charAt(0) == 'C'){
arr[pointer.nodeNum] = 1;
deletedNode.push(pointer);
list.delete(pointer);
if(pointer.right == list.tail){
pointer = pointer.left;
}else{
pointer = pointer.right;
}
}
else if(query.charAt(0) == 'Z'){
Node restoration = deletedNode.pop();
arr[restoration.nodeNum] = 0;
restoration.right.left = restoration;
restoration.left.right = restoration;
}
}
for(int i=0;i<n;i++){
if(arr[i]==0){
ans.append("O");
}else{
ans.append("X");
}
}
return ans.toString();
}
}
2. 인덱스 트리 ( 3번은 바이너리 인덱스트리로 불리는 펜윅트리 )
현재 가리키는 행이 k이고 U가 1000이라고 가정하자. 1번 방식은 1000번 pointer.left를 반복하면 된다.
인덱스 트리는, 행이 N인 표가 있을 때, 2^x(음수가 아닌 정수)인 N보다 크거나 같은 수 중에 가장 작은 수만큼의 리프노드를 갖는 포화이진트리로 구성돼 있다. 부분합을 구하는 쿼리는 평균적으로 트리의 높이인 x+1의 시간복잡도를 갖는다.
삭제 또한 마찬가지이다. 결과적으로 삽입, 삭제, 구간합 모두 O(log N)이어서 해결할 수 있을 것 같다.
명령어가 U 1000일 때, 다음 포인터 위치를 가리키는 데는 ( 구간합 구하기 * 이분탐색 )만큼의 시간복잡도를 갖는다.
O( (log N)^2 )
구체적으로 알아보자.
위는 파일 표의 행이 전체 4개일 때, 문제를 풀기 위해 초기화 한 인덱스 트리이다.
리프노드는 모두 1(삭제되지 않은 행)이다. 리프노드가 아닌 노드들이 의미하는 것은 구간 합이다.
3번째 행을 제거하면, 구간합을 갱신 해준다.
위 정보를 가지고 이제 4번째 위치에서 U 명령어를 수행해보며 인덱스트리를 문제에서 어떻게 활용하는지 감을 잡아보자
U 1
1번 행 ~ X번째 위치 까지의 합 = 2인 X인 위치가 이동할 위치이다. 왜냐하면
1번 행 ~ 현재 위치인 K번째 위치 까지의 구간합 = 3이고 U 1을 수행하기 때문이다.
쿼리를 수행할 때, 2번째 행까지의 구간합이 2이며, 3번 째 행까지의 구간합 또한 2인 것에 주의하며
코드를 짜야 한다.
U 2
위와 마찬가지로 1번 행 ~ X번째 행까지의 구간합이 1인 X를 구해주며 포인터를 바꾼다.
D 명령어도 마찬가지로 한다.
여기까지 보면, 그렇다면 어떻게? X를 구하는지 의문이 들 것이다. 1번~X번째 위치까지의 구간합을
X = 1 ~ (K-1) (현재 위치 이전)을 모두 구해봐야 하는 것인가? 그럼 더 오래걸리는 것은 아닌가 하고 말이다.
여기서 힌트가 있다. 모두 구해보는 행위를 한다면 1~1, 1~2, 1~3, .... 1~X의 구간합을 구하는 쿼리를 반복적으로 수행하다보면 이 값들이 점점 커지는 것을 볼 수 있다. 이럴 때 사용하는 것이 이분탐색이다.
이분탐색으로 찾고자 하는 값 key를 행 번호로 한다.
위 그림에서 U 1를 수행할 때를 예를들어 보자
1행부터 K번째 행까지 구간합이 3이므로 우리는 합이 2인 행을 구해야 한다고 했었다.
현재 포인터의 위치는 K(4번째 이다).
따라서 이동할 후보지는 left = 1, right = 3 이다.
1~2(mid = ( 1 + 3 ) / 2 )의 구간합을 구한다. => 위 그림을 보면 구간합이 2이다.
찾았다.
다시 U 2를 수행할 때를 확인해보자
1 ~ X 까지의 구간합이 1인 X를 구하면 된다.
left = 1, right = 3
mid = 2
1~2의 구간합 = 2 이므로 찾고자 하는 구간합 1보다 크다. 따라서 mid = 2보다 작은 행에서 찾고자 하는 값을 찾을 수 있을 것이다. right = mid - 1 = 1
결국 X = 1인 결과를 얻을 수 있다.
다른 예시 또한 수행해보며 감을 익히면 될 것 같다.
이분탐색 코드는 아래와 같이 수행했다.
if(query.charAt(0) == 'U'){
int cnt = Integer.parseInt(query.substring(2)) + 1;
int right = k-1;
int left = 1;
while(left <= right){
int mid = (left+right)/2;
int sum = query(mid,k);
if(sum > cnt){
left = mid + 1;
}else if( sum < cnt){
right = mid - 1;
}else{
k = mid;
while(tree[k+reafSize-1] != 1){
k++;
}
break;
}
}위 코드는, 위 설명과 다르게 구현했다.
위 설명대로 코드를 수행하면 1~k 까지의 구간합을 구하는 쿼리가 한번 더 필요하다.
그래서 1~X 구간합을 구하는 쿼리가 아닌 X ~ K 구간합이 cnt + 1 (K를 포함하므로)인 X를 구해주는 방법으로 했다.
D 명령어도 U처럼 반대방향으로 탐색하도록 구현해주면 된다.
C 명령어는 삭제 행을 스택에 저장하며 트리를 업데이트 해주면 되고
Z 명령어는 스택에 저장된 값을 꺼내서 트리를 업데이트 해주면 된다.
인덱스트리를 통한 해결 방법은 아이디어만 참고하면 좋을 듯 하다.
코드가 보기 힘들고, 효율성이 떨어진다.
코드를 올려두긴 하겠다.
전체코드
class Solution{
public static int tree[];
public static int reafSize;
public static void update(int num,int val){
while(num!=0){
tree[num]+=val;
num/=2;
}
}
public static int query(int left, int right){
int s = left + reafSize -1;
int e = right + reafSize - 1;
int ret = 0;
while(s <= e){
if(s % 2 == 1){
ret += tree[s++];
}
if(e % 2 == 0){
ret += tree[e--];
}
s/=2;
e/=2;
}
return ret;
}
public static String solution(int n, int k, String[] cmd) {
Stack<Integer> st = new Stack<>(); // Z 명령어를 위함
StringBuilder sb = new StringBuilder();
k++;
reafSize = 1;
while(reafSize < n){
reafSize *=2;
}
tree = new int[reafSize*2];
for(int i=0;i<reafSize;i++){
update(i+reafSize,1);
}
for(int i=0;i<cmd.length;i++){
String query = cmd[i];
if(query.charAt(0) == 'U'){
int cnt = Integer.parseInt(query.substring(2)) + 1;
int right = k-1;
int left = 1;
while(left <= right){
int mid = (left+right)/2;
int sum = query(mid,k);
if(sum > cnt){
left = mid + 1;
}else if( sum < cnt){
right = mid - 1;
}else{
k = mid;
// mid가 삭제된 행을 가리킬 경우
while(tree[k+reafSize-1] != 1){
k++;
}
break;
}
}
}else if(query.charAt(0) == 'D'){
int cnt = Integer.parseInt(query.substring(2)) + 1;
int right = n;
int left = k+1;
while(left <= right){
int mid = (left+right)/2;
int sum = query(k,mid);
if(sum > cnt){
right = mid - 1;
}else if( sum < cnt){
left = mid + 1;
}else{
k = mid;
while(tree[k+reafSize-1] != 1){
k--;
}
break;
}
}
}else if(query.charAt(0) == 'C'){
st.push(k);
update(k+reafSize-1,-1);
int left = k+1;
int right = n;
boolean suc = false;
while(left <= right){
int mid = (left+right)/2;
int sum = query(k,mid);
if(sum > 1){
right = mid - 1;
}else if( sum < 1){
left = mid + 1;
}else{
suc = true;
k = mid;
while(tree[k+reafSize-1] != 1){
k--;
}
break;
}
}
if(!suc){
right = k-1;
left = 1;
while(left <= right){
int mid = (left+right)/2;
int sum = query(mid,k);
if(sum > 1){
left = mid + 1;
}else if( sum < 1){
right = mid - 1;
}else{
k = mid;
while(tree[k+reafSize-1] != 1){
k++;
}
break;
}
}
}
}
else if(query.charAt(0) == 'Z'){
int num = st.pop();
update(num+reafSize-1,1);
}
}
for(int i=0;i<n;i++){
if(tree[i+reafSize]==1){
sb.append("O");
}else{
sb.append("X");
}
}
return sb.toString();
}
}
3. 펜윅트리
펜윅트리는 구간합 문제에서 인덱스트리보다 빠르게 쿼리를 수행할 수 있는 자료구조이다.
아이디어는 인덱스트리와 같으니 생략한다.
인덱스트리로 구현한 코드에서, 원하는 구간합을 구한 위치가 지워진 행일 때 처리 또한 이분탐색으로 구현한 점이다.
전체코드
class Solution{
public static int tree[];
public static int arr[];
public static int N;
public static void update(int num,int val){
while(num <= N){
tree[num]+=val;
num += num&-num;
}
}
public static int getSum(int target){
int ret = 0;
while(target>0){
ret+= tree[target];
target-=target&-target;
}
return ret;
}
public static int findSum(int target){
int ret = 1;
int left = 1;
int right = N;
while(left < right){
int mid = (left+right)/2;
int sum = getSum(mid);
if(sum >= target){
right = mid;
}else if( sum < target){
left = mid + 1;
}
}
return right;
}
public static String solution(int n, int k, String[] cmd) {
N = n;
Stack<Integer> st = new Stack<>(); // Z 명령어를 위함
StringBuilder sb = new StringBuilder();
k++;
tree = new int[n+1];
arr = new int[n+1];
for(int i=1;i<=n;i++){
tree[i] = i&-i;
arr[i] = 1;
}
for(int i=0;i<cmd.length;i++){
String query = cmd[i];
if(query.charAt(0) == 'U'){
int target = getSum(k) - Integer.parseInt(query.substring(2));
k = findSum(target);
}else if(query.charAt(0) == 'D'){
int target = getSum(k) + Integer.parseInt(query.substring(2));
k = findSum(target);
}else if(query.charAt(0) == 'C'){
st.push(k);
arr[k] = 0;
update(k,-1);
int sum = getSum(k);
if(sum == n-st.size()){
k = findSum(sum);
}else{
k = findSum(sum+1);
}
}
else if(query.charAt(0) == 'Z'){
int num = st.pop();
arr[num] = 1;
update(num,1);
}
}
for(int i=1;i<=n;i++){
if(arr[i]==1){
sb.append("O");
}else{
sb.append("X");
}
}
return sb.toString();
}
}
'알고리즘 > 프로그래머스' 카테고리의 다른 글
| [프로그래머스] 입국심사 / JAVA (0) | 2022.02.18 |
|---|---|
| [프로그래머스] 2021 카카오인턴십 - 미로탈출 [JAVA] (0) | 2021.08.31 |
| [프로그래머스] N으로 표현 [JAVA] (0) | 2021.06.03 |
| [프로그래머스] kakao 2019 겨울 인턴십 / 호텔 방 배정 [JAVA] (0) | 2021.05.09 |
| [프로그래머스] kakao 2019 겨울 인턴십 크레인 인형뽑기 게임 [JAVA] (0) | 2021.05.09 |