2021 카카오 인턴 코테 문제
5시간을 잡고 실전처럼 진행하였으며 코드의 최적화나 알고리즘은 정확하지 않음.
코딩테스트 연습 - 표 편집 | 프로그래머스 (programmers.co.kr)
코딩테스트 연습 - 표 편집
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
3번문제 였으며 3시간 정도 걸렸다.
이상하게 1, 2번이 너무 쉽다 했더니 3번이 복병이었다.
정확도 / 효율성으로 나뉜 문제였으며 정확도는 빠르게 해결하였으나 아무리 해도 효율성이 모두 통과되지 않았다.
문제 자체는 어렵진 않고 그냥 구현문제였으나, 효율성을 해결할 방법이 떠오르지 않았다.
문제 조건을 다시 보니 C와 U가 반복해야하고 C나 Z는 1타임에 해결해야하는거 같았다.
그래서 양방향 linked list를 구현하였더니 풀렸다.
너무 오랜만에 이런 코드를 보니 바로바로 생각나지 않았다.
linked list만 구현하면 다른 전처리 없이 풀릴거같다.
#include <string>
#include <vector>
#include <stdlib.h>
using namespace std;
typedef struct list {
int num;
list* prev;
list* next;
}list;
list* start = NULL;
list* cur = NULL;
list* last_node = NULL;
void push_back_node(int n)
{
list* temp = (list*)malloc(sizeof(list));
temp->num = n;
temp->next = NULL;
temp->prev = last_node;
if (start == NULL)
start = temp;
if (last_node != NULL)
last_node->next = temp;
last_node = temp;
}
void delete_node()
{
if (cur->prev == NULL)
{
cur->next->prev = NULL;
start = cur->next;
cur = cur->next;
}
else if (cur->next == NULL)
{
cur->prev->next = NULL;
last_node = cur->prev;
cur = cur->prev;
}
else
{
cur->prev->next = cur->next;
cur->next->prev = cur->prev;
cur = cur->next;
}
}
void append_node(list* node)
{
int n = node->num;
if (n < start->num)
{
node->next = start;
node->prev = NULL;
start->prev = node;
start = node;
}
else if (n > last_node->num)
{
push_back_node(n);
}
else
{
if (n > cur->num)
{
for (list* temp = cur; temp->next != NULL; temp = temp->next)
if (temp->next->num > n)
{
node->prev = temp;
node->next = temp->next;
temp->next->prev = node;
temp->next = node;
break;
}
}
else
{
for (list* temp = cur; temp->prev != NULL; temp = temp->prev)
if (temp->prev->num < n)
{
node->prev = temp->prev;
node->next = temp;
temp->prev->next = node;
temp->prev = node;
break;
}
}
}
}
string solution(int n, int k, vector<string> cmd) {
string answer = "";
int size = n - 1;
vector<list*> deleted;
//vector<int> deleted;
for (int i = 0; i < n; i++)
{
answer += "X";
push_back_node(i);
if (i == k)
cur = last_node;
}
int cnt = 0;
int end_ind = cmd.size() - 1;
for (int i = cmd.size() - 1; i >= 0; i--)
{
char opt = cmd[i][0];
if (opt == 'C')
{
if (cnt == 0)
{
end_ind = i;
break;
}
else
cnt--;
}
else if (opt == 'Z')
cnt++;
}
for (int i = 0; i <= end_ind; i++)
{
cnt = 0;
char opt = cmd[i][0];
if (opt == 'U')
{
int num = stoi(cmd[i].substr(2, cmd[i].size() - 2));
for (int j = 0; j < num; j++)
cur = cur->prev;
}
else if (opt == 'D')
{
int num = stoi(cmd[i].substr(2, cmd[i].size() - 2));
for (int j = 0; j < num; j++)
cur = cur->next;
}
else if (opt == 'C')
{
deleted.push_back(cur);
delete_node();
}
else if (opt == 'Z')
{
list* recovered = deleted[deleted.size() - 1];
deleted.pop_back();
append_node(recovered);
}
}
for (list* temp = start; temp != NULL; temp = temp->next)
answer[temp->num] = 'O';
for (list* temp = start->next; temp != NULL; start = temp, temp = start->next)
free(start);
free(start);
return answer;
}
'Coding_Test > 2021_KAKAO_INTERN' 카테고리의 다른 글
| [2021 카카오 인턴] 거리두기 확인하기 (C++) (0) | 2022.05.12 |
|---|---|
| [2021 카카오 인턴] 숫자 문자열과 영단어 (C++) (0) | 2022.05.12 |