프로그래머스 문제풀이 (알고리즘) - 표 편집 [2021 카카오 채용연계형 인턴십]
문제
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
들어가기 앞서
문제 풀이에 쓰인 enum 클래스와 command 클래스
static class Command {
private static Type type;
private static Integer spec;
public Command(String str) {
if (str.startsWith("U")) {
type = Type.UP;
spec = Integer.parseInt(str.split(" ")[1]);
}
else if (str.startsWith("D")) {
type = Type.DOWN;
spec = Integer.parseInt(str.split(" ")[1]);
}
else if (str.startsWith("C")) {
type = Type.DELETE;
}
else if (str.startsWith("Z")) {
type = Type.RESTORE;
}
}
public Integer getSpec() {
return spec;
}
}
static enum Type {
UP, DOWN, DELETE, RESTORE;
}
잡소리 (바쁘신 부분은 넘겨주세요)
프로그래밍을 하는데, 객체 지향을 사용하는 것은 결국 사람의 사고와 유사하게 프로그래밍 함으로써 코드에 대한 이해를 높이려는 시도의 일환이라고 생각합니다.
그래서 객체지향적으로 프로그래밍을 짜려고 노력 했습니다.
절차 지향인 코드보다 이해가 훨씬 쉽겠죠.
예를 들어서 다음과 같은 코드가 있다고 합시다.
class Solution {
private int[] arr = new int[10];
private String[] status = new String[10];
private int i = 5;
public void run() {
if (arr[i] == -1)
status[i] = "DELETED";
}
}
}우리는 if (arr[i] == -1) 을 통해서 arr 에 들어간 -1 이라는 값이 무엇을 의미하는지 알 수 있을까요?
이 의미를 파악하려면 status[i] = "DELETED"; 라는 코드까지 읽고 나서야 -1 이 "삭제"를 뜻한다는 것을 어림짐작 할 수 있습니다.
즉, 위 코드의 문제점은 2개입니다.
- arr 요소에 들어간 값의 의미를 파악하기 어렵다.
- arr 요소에 들어간 값의 의미를 모두 기억하고 있어야 한다.
따라서 메소드에 의미를 부여해서 다음과 같이 리펙토링 했습니다.
class Solution {
private int[] arr = new int[10];
private String[] status = new String[10];
private int i = 5;
public void run() {
if (isDeleted(i))
status[i] = "DELETED";
}
}
private boolean isDeleted(int i) {
return arr[i] == -1;
}
}물론 객체 지향으로 코드를 변경하려면 arr 가 다른 클래스 내부에 위치하고 이를 제어할 수 있는 api 로 isDeleted 가 주어지면 되겠죠.
여튼, 이렇게 코드를 작성함으로서 arr 에 들어간 요소가 -1 이면 삭제 된 것임을 한눈에 알 수 있게 되었습니다.
객체 지향 프로그래밍에는 이러한 장점이 있다고 생각합니다.
해당 코드의 의미를 덧붙이고, 재사용하고 데이터를 응집시키고.. 등등
문제 풀이 시도 1 (오답)
public String solution(int n, int k, String[] cmd) {
Memory memory = new Memory(k);
int size = n;
// 메모리에 기본 값을 채운다.
for (int i=0; i<n; i++)
memory.add(i);
// 명령어를 실행한다.
for (String c : cmd)
memory.execute(new Command(c));
// 결과 반환
String result = memory.getResult(size);
return result;
}
private static class Memory {
private List<Integer> memory = new ArrayList<>();
private Stack<Integer[]> deleted = new Stack();
private int cursor;
public Memory(int cursor) {
this.cursor = cursor;
}
// 테이블의 기본 값을 채운다.
public void add(Integer num) {
this.memory.add(num);
}
// 명령어 실행
public void execute(Command command) {
if (Type.DELETE.equals(command.type)) {
delete();
}
else if (Type.UP.equals(command.type)) {
up(command.getSpec());
}
else if (Type.DOWN.equals(command.type)) {
down(command.getSpec());
}
else if (Type.RESTORE.equals(command.type)) {
restore();
}
}
// 결과 반환
public String getResult(int size) {
StringBuilder sb = new StringBuilder();
String[] ox = {"O", "X"};
int cur = 0;
for (int i=0; i<memory.size(); i++) {
int til = memory.get(i);
if (til == cur) {
sb.append(ox[0]);
cur++;
} else {
while (cur < til) {
sb.append(ox[1]);
cur++;
}
sb.append(ox[0]);
cur++;
}
}
while (cur < size) {
sb.append(ox[1]);
cur++;
}
return sb.toString();
}
// 삭제
private void delete() {
// 가장 마지막에 삭제된 정보를 저장하고 메모리에서 데이터 삭제
deleted.add(new Integer[]{cursor, memory.get(cursor)});
memory.remove(cursor);
// 커서 갱신
if (cursor >= memory.size())
cursor -= 1;
}
private void up(int i) {
this.cursor -= i;
}
private void down(int i) {
this.cursor += i;
}
// stack 에 쌓인 삭제 정보 복원
private void restore() {
Integer[] pop = deleted.pop();
memory.add(pop[0], pop[1]);
// 복원시 현재 커서 이전의 내용을 복원하면 같은 내용을 가리키키 위해 커서도 +1
if (pop[0] <= cursor)
cursor += 1;
}
}
// ... Command 클래스와 enum Type 클래스 생략이 계산에는 큰 문제가 있었는데 Memory 를 구현할 때 ArrayList 를 사용했다는 점입니다.
이는 "삭제"를 할 때 가장 큰 문제가 되는데 특정 요소를 삭제했을 때 삭제한 인덱스 이후에 있는 요소의 자리를 1칸씩 앞으로 당겨오기 때문에 값의 이동이 많아지고 이는 속도 면에 있어서 성능 저하를 일으킵니다.
저는 단지 구현이 편하다는 이유로 이 자료형을 선택한 것이 큰 문제였습니다.
그러면 LinkedList 를 사용하면 나을까?
저는 아니라고 봅니다. 아래 링크로 가면 ArrayList 와 LinkedList 를 비교하는 부분이 있는데 결론만 얘기하면 다음과 같습니다.
https://github.com/donghyeon0725/algorithm_java/blob/master/src/com/dataType/speedTest/README.md
GitHub - donghyeon0725/algorithm_java: algorithm study with java
algorithm study with java. Contribute to donghyeon0725/algorithm_java development by creating an account on GitHub.
github.com
값을 추가할 때 (restore 호출 상황) 에는 대체로 ArrayList 가 성능상 이점이 있었고 삭제시엔 특정 상황에서 LinkedList 가 우위가 있었으나 그 상황 외에는 ArrayList 가 압도적인 성능 우위가 있었다는 점입니다.
즉, LinkedList 를 사용해도 그닥 성능 향상이 되지 않을 것이라고 생각했습니다.
따라서 Memory를 구현할 때 int[] 자료형을 사용하기로 했습니다.
테스트 결과
테스트 1 〉 통과 (0.91ms, 56.8MB)
테스트 2 〉 통과 (1.49ms, 74.1MB)
테스트 3 〉 통과 (2.89ms, 57.5MB)
테스트 4 〉 통과 (2.52ms, 57.7MB)
테스트 5 〉 통과 (1.76ms, 73.2MB)
테스트 6 〉 통과 (1.74ms, 57.5MB)
테스트 7 〉 통과 (1.71ms, 58.3MB)
테스트 8 〉 통과 (1.18ms, 58.3MB)
테스트 9 〉 통과 (1.97ms, 57.8MB)
테스트 10 〉 통과 (1.21ms, 56.6MB)
테스트 11 〉 통과 (3.79ms, 73.7MB)
테스트 12 〉 통과 (3.07ms, 57.6MB)
테스트 13 〉 통과 (2.59ms, 60.2MB)
테스트 14 〉 통과 (8.49ms, 57.1MB)
테스트 15 〉 통과 (3.03ms, 57.2MB)
테스트 16 〉 통과 (3.95ms, 73.4MB)
테스트 17 〉 통과 (6.46ms, 61.4MB)
테스트 18 〉 통과 (5.07ms, 57.4MB)
테스트 19 〉 통과 (4.68ms, 60.1MB)
테스트 20 〉 통과 (5.23ms, 59.1MB)
테스트 21 〉 통과 (4.20ms, 60.1MB)
테스트 22 〉 통과 (5.67ms, 57.4MB)
테스트 23 〉 통과 (1.16ms, 57.5MB)
테스트 24 〉 통과 (0.87ms, 59.5MB)
테스트 25 〉 통과 (1.32ms, 72.9MB)
테스트 26 〉 통과 (1.30ms, 58.3MB)
테스트 27 〉 통과 (0.92ms, 57.1MB)
테스트 28 〉 통과 (1.50ms, 73.3MB)
테스트 29 〉 통과 (1.11ms, 66.9MB)
테스트 30 〉 통과 (1.38ms, 56.9MB)
효율성 테스트
테스트 7 〉 통과 (504.92ms, 105MB)
테스트 8 〉 통과 (1030.86ms, 105MB)언급이 없는 테스트는 실패한 겁니다.
시도 2 (오답)
public class Solution {
public String solution(int n, int k, String[] cmd) {
// 메모리 생성
Memory memory = new Memory(n, k);
// 명령어 실행
for (String c : cmd)
memory.execute(new Command(c));
// 결과 반환
return memory.getResult();
}
private static class Memory {
// 메모리
private int[] memory;
// 삭제된 인덱스
private Stack<Integer> deleted = new Stack();
// 커서
private int cursor;
public Memory(int size, int cursor) {
memory = new int[size];
this.cursor = cursor;
}
public void execute(Command command) {
if (Type.DELETE.equals(command.type))
delete();
else if (Type.UP.equals(command.type))
up(command.getSpec());
else if (Type.DOWN.equals(command.type))
down(command.getSpec());
else if (Type.RESTORE.equals(command.type)) {
restore();
}
}
public String getResult() {
StringBuilder sb = new StringBuilder();
String[] ox = {"O", "X"};
for (int i : memory)
if (i == 0)
sb.append(ox[0]);
else
sb.append(ox[1]);
return sb.toString();
}
// 마지막 인덱스 찾기
private void resetCursor() {
int cursor = this.cursor;
int i = 1;
while (cursor < memory.length - 1 && i > 0) {
if (!isDeletedIndex(cursor + 1))
i--;
cursor++;
}
// 마지막까지 삭제되지 않은 인덱스를 못찾은 경우
if (i > 0) {
cursor = this.cursor;
while (cursor > 0 && i > 0) {
if (!isDeletedIndex(cursor - 1))
i--;
cursor--;
}
}
this.cursor = cursor;
}
private void delete() {
// 삭제 인덱스 저장
deleted.add(cursor);
// 삭제
memory[cursor] = -1;
// 커서 리셋
resetCursor();
}
private boolean isDeletedIndex(int i) {
return memory[i] != 0;
}
// 삭제 안된 인덱스를 찾아 up
private void up(int i) {
while (i > 0) {
// 삭제 안된 경우
if (!isDeletedIndex(cursor - 1))
i--;
cursor--;
}
}
// 삭제 안된 인덱스를 찾아 down
private void down(int i) {
while (i > 0) {
if (!isDeletedIndex(cursor + 1))
i--;
cursor++;
}
}
// 삭제된 내용 복원
private void restore() {
Integer pop = deleted.pop();
memory[pop] = 0;
}
}
}
// ... Command 클래스와 enum Type 클래스 생략
결과
테스트 1 〉 통과 (0.85ms, 57.1MB)
테스트 2 〉 통과 (1.19ms, 72MB)
테스트 3 〉 통과 (1.36ms, 58.1MB)
테스트 4 〉 통과 (1.15ms, 73.6MB)
테스트 5 〉 통과 (1.58ms, 70.6MB)
테스트 6 〉 통과 (1.06ms, 70.5MB)
테스트 7 〉 통과 (1.01ms, 57.9MB)
테스트 8 〉 통과 (1.05ms, 58.1MB)
테스트 9 〉 통과 (1.17ms, 58.2MB)
테스트 10 〉 통과 (1.08ms, 57.2MB)
테스트 11 〉 통과 (3.02ms, 57.2MB)
테스트 12 〉 통과 (3.84ms, 72.4MB)
테스트 13 〉 통과 (3.70ms, 74MB)
테스트 14 〉 통과 (4.13ms, 56.9MB)
테스트 15 〉 통과 (3.97ms, 57.1MB)
테스트 16 〉 통과 (2.71ms, 58.5MB)
테스트 17 〉 통과 (13.91ms, 73.9MB)
테스트 18 〉 통과 (25.41ms, 59.5MB)
테스트 19 〉 통과 (8.08ms, 58.6MB)
테스트 20 〉 통과 (12.80ms, 72.3MB)
테스트 21 〉 통과 (6.02ms, 73.7MB)
테스트 22 〉 통과 (6.71ms, 71.1MB)
테스트 23 〉 통과 (1.14ms, 57.1MB)
테스트 24 〉 통과 (1.01ms, 69.1MB)
테스트 25 〉 통과 (1.12ms, 57MB)
테스트 26 〉 통과 (1.28ms, 60.4MB)
테스트 27 〉 통과 (1.37ms, 57.5MB)
테스트 28 〉 통과 (0.88ms, 57.5MB)
테스트 29 〉 통과 (0.87ms, 58.3MB)
테스트 30 〉 통과 (0.98ms, 70.5MB)
효율성 테스트
테스트 1 〉 통과 (123.31ms, 109MB)
테스트 2 〉 통과 (135.59ms, 109MB)
테스트 3 〉 통과 (139.53ms, 108MB)
테스트 4 〉 통과 (174.03ms, 113MB)
테스트 5 〉 통과 (208.85ms, 112MB)
테스트 6 〉 실패 (시간 초과)
테스트 7 〉 실패 (시간 초과)
테스트 8 〉 실패 (시간 초과)
테스트 9 〉 실패 (시간 초과)
테스트 10 〉 실패 (시간 초과)
이는 성능상의 이점이 있어서 효율 테스트에서 이전보다 많은 테스트 케이스에서 통과를 했습니다.
그러나 오답이었습니다.
뭐가 문제일까 고민을 하다가 다음과 같은 결론을 냈습니다.
ArrayList 를 사용해서 Memory를 구현했을 때와 달리 Integer Array 를 사용하면
- 삭제
- 업
- 다운
위 세가지 케이스에 인덱스 위치를 다시 찾아 주어야 했습니다.
성능 개선 여지가 있는 부분
삭제를 할 때에는 항상 커서가 존재하는 위치의 노드를 삭제하는 것이기 때문에 이것이 다음 연산의 결과에 영향을 미치고 따라서 "현재 커서 위치"를 꼭 계산 해주어야 합니다.
한편, 업 & 다운은 명령을 한번 실행할 때마다 커서 위치를 계산하는 비용이 꽤나 크고, 한번에 모아서 계산해도 별 문제가 되지 않기 때문(다음 업다운 연산에 영향을 미치지 않음)에 버퍼에 업 & 다운 명령이 일어날때 마다 그 수치를 커서에 반영하기로 했습니다.
한편 Memory의 요소가 삭제 되었는지 여부에 따라서 인덱스 위치를 계산하는 방법이 달라지기 때문에 복원 명령이 수행되기 전에 커서를 옮겨주어야 한다고 생각했습니다.
시도 3 (정답)
public class Solution {
public String solution(int n, int k, String[] cmd) {
// 메모리 생성
Memory memory = new Memory(n, k);
// 명령 실행
for (String c : cmd)
memory.execute(new Command(c));
// 결과 반환
return memory.getResult();
}
private static class Memory {
private int[] memory;
private Stack<Integer> deleted = new Stack();
private int cursor;
private int buffer;
public Memory(int size, int cursor) {
memory = new int[size];
this.cursor = cursor;
}
// 핵심 ******
public void execute (Command command) {
// 삭제 되기 전에 버퍼 내역을 커서에 적용합니다.
if (Type.DELETE.equals(command.type)) {
flushAndClear();
delete();
}
else if (Type.UP.equals(command.type))
buffer -= command.getSpec();
else if (Type.DOWN.equals(command.type))
buffer += command.getSpec();
// 복원을 하기 전에 커서의 변경 내역을 반영합니다.
else if (Type.RESTORE.equals(command.type)) {
flushAndClear();
restore();
}
}
// 업 다운으로 발생한 버퍼의 내역을 커서에 반환하고 버퍼를 비웁니다.
public void flushAndClear() {
if (buffer < 0)
up(-buffer);
else if (buffer > 0)
down(buffer);
buffer = 0;
}
public String getResult() {
StringBuilder sb = new StringBuilder();
String[] ox = {"O", "X"};
for (int i : memory)
if (i == 0)
sb.append(ox[0]);
else
sb.append(ox[1]);
return sb.toString();
}
// 마지막 인덱스 찾기
private void resetCursor() {
int cursor = this.cursor;
int i = 1;
while (cursor < memory.length - 1 && i > 0) {
if (!isDeletedIndex(cursor + 1))
i--;
cursor++;
}
if (i > 0) {
cursor = this.cursor;
while (cursor > 0 && i > 0) {
if (!isDeletedIndex(cursor - 1))
i--;
cursor--;
}
}
this.cursor = cursor;
}
private void delete() {
deleted.add(cursor);
memory[cursor] = -1;
resetCursor();
}
private boolean isDeletedIndex(int i) {
return memory[i] != 0;
}
private void up(int i) {
while (i > 0) {
// 삭제 안된 경우
if (!isDeletedIndex(cursor - 1))
i--;
cursor--;
}
}
private void down(int i) {
while (i > 0) {
if (!isDeletedIndex(cursor + 1))
i--;
cursor++;
}
}
private void restore() {
Integer pop = deleted.pop();
memory[pop] = 0;
}
}
}
// ... Command 클래스와 enum Type 클래스 생략
테스트 결과 (통과)
테스트 1 〉 통과 (1.17ms, 56.7MB)
테스트 2 〉 통과 (1.14ms, 72.3MB)
테스트 3 〉 통과 (1.27ms, 57MB)
테스트 4 〉 통과 (3.56ms, 56.6MB)
테스트 5 〉 통과 (15.12ms, 55.5MB)
테스트 6 〉 통과 (1.72ms, 58.2MB)
테스트 7 〉 통과 (1.44ms, 56.9MB)
테스트 8 〉 통과 (1.10ms, 57.8MB)
테스트 9 〉 통과 (1.17ms, 67.5MB)
테스트 10 〉 통과 (1.61ms, 56.4MB)
테스트 11 〉 통과 (2.64ms, 58.6MB)
테스트 12 〉 통과 (5.43ms, 56.9MB)
테스트 13 〉 통과 (3.42ms, 57.9MB)
테스트 14 〉 통과 (4.37ms, 58.5MB)
테스트 15 〉 통과 (4.70ms, 57.6MB)
테스트 16 〉 통과 (3.89ms, 57.1MB)
테스트 17 〉 통과 (8.06ms, 57.6MB)
테스트 18 〉 통과 (18.76ms, 76.4MB)
테스트 19 〉 통과 (16.55ms, 58.9MB)
테스트 20 〉 통과 (6.97ms, 73.4MB)
테스트 21 〉 통과 (17.98ms, 71.4MB)
테스트 22 〉 통과 (5.35ms, 59.6MB)
테스트 23 〉 통과 (0.77ms, 57.6MB)
테스트 24 〉 통과 (1.23ms, 58.4MB)
테스트 25 〉 통과 (1.20ms, 66.4MB)
테스트 26 〉 통과 (1.04ms, 55.4MB)
테스트 27 〉 통과 (1.15ms, 60.1MB)
테스트 28 〉 통과 (1.45ms, 73.5MB)
테스트 29 〉 통과 (0.99ms, 59.8MB)
테스트 30 〉 통과 (1.01ms, 57.5MB)
효율성 테스트
테스트 1 〉 통과 (101.61ms, 108MB)
테스트 2 〉 통과 (123.89ms, 109MB)
테스트 3 〉 통과 (131.79ms, 109MB)
테스트 4 〉 통과 (221.78ms, 113MB)
테스트 5 〉 통과 (231.71ms, 112MB)
테스트 6 〉 통과 (169.23ms, 111MB)
테스트 7 〉 통과 (152.94ms, 95.3MB)
테스트 8 〉 통과 (1456.14ms, 98.1MB)
테스트 9 〉 통과 (161.37ms, 115MB)
테스트 10 〉 통과 (177.00ms, 114MB)'알고리즘 > 문제풀이' 카테고리의 다른 글
| 프로그래머스 문제풀이(알고리즘) - 보석 쇼핑[카카오 인턴] (0) | 2021.08.18 |
|---|---|
| 프로그래머스 문제풀이 (알고리즘) - 다단계 칫솔판매 (0) | 2021.08.18 |
| 프로그래머스 문제풀이 (알고리즘) - 셔틀버스 (0) | 2021.08.12 |
| 프로그래머스 문제풀이 (알고리즘) - N-Queen (0) | 2021.08.11 |
| 프로그래머스 문제풀이 (알고리즘) - 하노이 탑 (0) | 2021.08.10 |
댓글
이 글 공유하기
다른 글
-
프로그래머스 문제풀이(알고리즘) - 보석 쇼핑[카카오 인턴]
프로그래머스 문제풀이(알고리즘) - 보석 쇼핑[카카오 인턴]
2021.08.18 -
프로그래머스 문제풀이 (알고리즘) - 다단계 칫솔판매
프로그래머스 문제풀이 (알고리즘) - 다단계 칫솔판매
2021.08.18 -
프로그래머스 문제풀이 (알고리즘) - 셔틀버스
프로그래머스 문제풀이 (알고리즘) - 셔틀버스
2021.08.12 -
프로그래머스 문제풀이 (알고리즘) - N-Queen
프로그래머스 문제풀이 (알고리즘) - N-Queen
2021.08.11