[2024 카카오 코테 대비] - Lv3. 표 편집 (2021 카카오 인턴)

코테 문제 보이는 대로 풀었다가 처참히 망해버림

그래서 공식 카카오 문풀을 참고해서 정리해 두려한다...

 

문제

https://school.programmers.co.kr/learn/courses/30/lessons/81303

프로그래머스

 

HOW TO SOLVE IT

 

효율성 검사가 있어서 전략적으로 푸는 방법이 필요하다.

 

정확성 테스트

핵심 지식은 다음과 같다.

1. 삭제할 여부를 표시하는 배열 선언 -> arr
2. 중간 처리 과정을 위해 현재 선택된 행의 번호도 저장 -> selected
3. 최근 삭제된 순으로 저장하는 스택 선언

U,D,C 명령은 최악의 경우 O(n), Z 명령은 O(1)에 처리할 수 있다.

 

여기까지만 보면 정확성 테스트 케이스의 제한 조건에서 5 ≤ n ≤ 1,000이므로 충분히 해결할 수 있다.
하지만 효율성 테스트 케이스의 경우,  5 ≤ n ≤ 1,000,000 이므로 배열을 사용해서 해결하기에는 수행시간이 너무 오래 걸린다.

---

효율성 테스트

핵심 지식은 다음과 같다.

1. 링크드 리스트 사용
   • U,D 명령: X번만 링크를 따라가면 되기 때문에 O(X)에 처리 가능
   • C 명령: 선택된 노드와 그 노드의 앞 뒤로 연결된 노드들의 링크 정보만 변경하면 되기 때문에 O(1) 처리 가능
   • Z 명령: 삭제된 노드 정보를 스택에 담아 두면 나중에 해당 노드에 O(1)에 접근하여 링크 정보를 복구할 수 있어서 O(1)에 가능
2. Segment Tree 또는 Fenwick Tree 사용
   일부 참가자들이 사용한 풀이 방법이다.
   먼저 정확성 풀이 처음에 나왔던 방식을 떠올려보자, 각 행의 삭제 여부를 0과 1로 나타냈던 방식이었다.
   
   이 때, 배열의 특정 구간의 합은 해당 구간의 삭제되지 않은 행의 수로 볼 수 있다.
   그렇다면, U와 D 명령을 다음과 같이 생각할 수 있다.
   
   1.  U X: 현재 선택된 행에서, 그 위쪽 구간의 합이 X가 되는 지점으로 이동
   2.  D X: 현재 선택된 행에서 , 그 아래쪽 구간의 합이 X가 되는 지점으로 이동

        이 방법을 사용하기 위해서는 선택된 행 위쪽 또는 아래쪽으로 얼마나 이동했는지 구간 합이 X가 되는지를 빠르게 구해야 한다.

        만약 배열 전체를 순회할 경우 O(X)가 되어 배열을 사용한 풀이와 동일해지기 때문에 더 빠른 방법을 찾아야 한다.

• Segment Tree 또는 Fenwick Tree
  • 이 자료구조를 사용하면 크기가 n인 배열의 구간 합을 O(log2 n) 시간에 구함
• 이분 탐색
  • 선택된 행 앞, 또는 뒤로 몇 칸을 이동해야 할지를 이분 탐색을 사용해 O(log2 n) 시간에 구할 수 있음 

        두 기법을 조합해서 어느 지점까지 이동해야할지 O((log2n)^2) 시간에 구할 수 있다.

 

---

문제 복기

 

음.. 나는 정확성 테스트까지 했다. 근데 확실히 효율성 테스트에서 처참히 갈려버려서 segment tree랑 Fenwick Tree까지는 아니더라도 linked list로 풀어봐야겠다.