[프로그래머스:코딩테스트 연습]2021 카카오 채용연계형 인턴쉽

https://programmers.co.kr/learn/challenges

코딩테스트 연습

문제 모음 선택 - 2021 카카오 채용연계형 인턴쉽

---

 

숫자 문자열과 영단어

풀이 :

문자열을 숫자로 바꾸는 문제, 문자열 관련 함수를 사용하면 되는 문제.

미리 저장해둔 문자열(0~9)과 비교해서 숫자로 저장하였다.

내 풀이에서는 compare와 stoi를 사용하였지만, ("zer"을 "zeo"로 써서 헤맸다.)

다른 사람들의 풀이를 보고 느낀 점은 굳이 3자리로 저장할 이유가 없다(다 저장해서 비교하면 됨)와

replace, regex_replace, substr  등의 함수 사용도 있다는 점..

#include <string>
#include <vector>
using namespace std;

string arr[10] = {"zer","one", "two", "thr", "fou", "fiv", "six", "sev", "eig", "nin"};
int arrlen[10] = {4, 3, 3, 5, 4, 4, 3, 5, 5, 4};

int solution(string s) {
    int answer = 0;
    int cnt =0;
    string ans ="";
    int size = s.size();
    for(int i=0; i<size; ++i) {
        if('0' <= s[i] && s[i] <= '9') {	// 문자열이 숫자인경우
            ans += s[i];
        }else {								// 문자열이 문자인경우
             char tmp[4], num[2];			// 3글자만 비교 하도록 저장
                tmp[0] = s[i];
                tmp[1] = s[i+1];
                tmp[2] = s[i+2];
                tmp[3] = 0;
            string ttmp = tmp;
            for(int j=0; j<10; ++j) {
                if(ttmp.compare(arr[j])==0) {	//같다면 정답에 추가
                    sprintf(num,"%d", j);
                    ans+=num;
                    i+= arrlen[j]-1;
                }
            }
        }
    }
    answer = stoi(ans.c_str());
    return answer;
}

 

 

거리두기 확인

풀이 :

5X5 대기실에서 응시자 간의 거리가 2 이하로 앉아있는지 찾는 문제

그래프탐색, DPS를 사용해서 문제를 풀었다.

시간은 넉넉하기 때문에 효율성 부분은 덜 생각했다.

//만약 더 빠르게 하려면 P를 찾았을 때 리턴하는 부분을 if( ret == 0) return 0; 식으로 하면 바로 리턴한다.  

대부분은 이중포문, DFS, BFS를 사용해서 푼 것 같다.

#include <string>
#include <vector>
#include <iostream>
#include <cmath>
using namespace std;

int dy[4] = {-1, 0, 1, 0};
int dx[4] = {0, -1, 0, 1};
int visited[5][5];
int dps(vector<string> &map, int cnt, int y, int x) {
    int ret = 1;
    if( cnt == 3) return 1;             // 인접 2거리 안에 없다면 리턴 1
    if(cnt!= 0 && map[y][x]=='P') return 0; // 자신 제외하고 P라면 리턴 0
    
    
    for(int i=0; i<4; ++i) {
        int ny = y+dy[i];
        int nx = x+dx[i];
        if(0<=ny && ny< 5 && 0<= nx && nx <5 && visited[ny][nx]==0 &&
           map[ny][nx]!='X') {          // 범위, 비짓, 파티션확인 
            ret = min(ret, dps(map, cnt+1, ny, nx));
        }
    }
    return ret;
}
vector<int> solution(vector<vector<string>> places) {
    vector<int> answer = {1, 1, 1, 1, 1};
    for(int i=0; i<5; ++i) {
        memset(visited, 0, sizeof(visited));
        for(int h=0; h<5&& answer[i]==1; ++h) {     //&& answer[i]==1, 이미 0이면 다른 것을 더 확인 할 필요가 없음.
            for(int w=0; w<5&& answer[i]==1; ++w) {
                if(places[i][h][w]=='P') {
                    visited[h][w] = 1;          // 자신을 다시 방문하면 안됨.
                    if(dps(places[i],0, h, w)==0) {
                        answer[i] = 0;
                    }
                }
            }
        }
    }
    return answer;
}

 

 

표 편집

정확성 테스트와 효율성 테스트가 같이 있는 문제.

링크드 리스트로 구현하여 삭제, 복구 등을 신경 써서 구현하여 풀었다.

삭제 시 stack push, 복구 시 stack pop 하였고, 

링크드 리스트 간의 연결을 경우에 따라 분류하여 연결했다.

//숫자 표현을 처음에 int num = char - '0'; 으로 해서 디버깅이 오래 걸렸다.

다른 사람들의 풀이를 보니 set을 사용하여 간결하게 구현하거나, 팬윅트리를 사용한 고수분들도 있었다..

#include <string>
#include <vector>
#include <stack>
using namespace std;

struct node {
	int num;
	struct node * front;
	struct node * back;
    node(int num) :num(num), front(NULL), back(NULL) {};
};

string solution(int n, int k, vector<string> cmd) {
	string answer(n, 'O');
	vector<node*> arr(n);
	stack<int> del;         //삭제한 순서대로 저장.
	node* cur;  //현재 커서 위치
	for (int i = 0; i < n; ++i) {
		arr[i] = new node(i);
	}
	arr[0]->back = arr[1];
	arr[n - 1]->front = arr[n - 2];
	for (int i = 1; i < n - 1; ++i) {
		arr[i]->front = arr[i - 1];
		arr[i]->back = arr[i + 1];
	}
	cur = arr[k];

	int size = cmd.size();
	for (int i = 0; i<size; ++i) {
		if (cmd[i][0] == 'U') {
			int cnt = stoi(cmd[i].substr(2));
			while (cnt--) 	cur = cur->front;
		}
		else if (cmd[i][0] == 'D') {
			int cnt = stoi(cmd[i].substr(2));
			while (cnt--) cur = cur->back;
		}
		else if (cmd[i][0] == 'C') {
			del.push(cur->num);
			if (NULL != cur->front) {
				(cur->front)->back = cur->back;
			}
			if (NULL != cur->back) {
				(cur->back)->front = cur->front;
				cur = cur->back;
			}
			else cur = cur->front;
		}
		else if (cmd[i][0] == 'Z') {
			int num = del.top();
			del.pop();
			node* tmp = arr[num];
			if (NULL != tmp->front) {
				(tmp->front)->back = tmp;
			}
			if (NULL != tmp->back) {
				(tmp->back)->front = tmp;
			}
		}
    }
	//답
	while (!del.empty()) {
		int num = del.top();
		del.pop();
		answer[num] = 'X';
	}
	return answer;
}

 

 

미로 탈출

풀이 : 

내 이론상으론 시간 초과가 안 뜨는데 풀이상 문제가 있어서 시간 초과로 시간 안에 못 푼 문제.

DPS + DP, 비트 마스크로 구현을 했다.

노드 방문 개수(노드 개수x트랩 가능한 수)(1000x1024) x 노드 한번 방문 시 (인접노드확인, x 트랩확인)(1000x10)으로 100초가 넘어서 시간초과가 됬다.

->DFS는 노드랑 엣지가 있어서 노드를 한번만 접근하는 경우에 쓰자.

->O(ElogV)다익스트라로 해야될것 같다. E=1024*3000, V=1000*1024

#include <string>
#include <vector>
#include <cmath>
using namespace std;

int maps[1001][1001];   // 첫 그래프 상태 저장
int ans = 1e9+1;
int dis[1024][1001]; // 트랩이 이러한 상태에서(비트마스크) 2^10 -1, 몇번 노드까지 가는데 걸린 시간. 


void dps(int n, int pos, int cnt, int end, vector<int> traps, int bit) { //노드개수, 현재위치, 거리, 도착지점, 트랩 현황, 밣은 트렙 비트마스크
    //cout << pos << endl;
    if(pos == end) {    // 도착하면 리턴
        if(cnt < ans) ans = cnt;
        return;
    }
    //cout << "pos1" << endl;
   if(dis[bit][pos] > cnt) {    // 현재 위치와 밣은 트랩 현황에서 거리 비교
        dis[bit][pos] = cnt;
    }else return;
    //cout << "pos2" << endl;
    for(int i=1; i<=n; ++i) {
        //no traping함수
        int isBothTrap = 0;
        int goTime =0;
        //cout << pos << " next : " << i<< " init"<<endl;
        for(int t=0; t<traps.size(); ++t) {
            if(traps[t] == pos) {
                if((int)pow(2,t)&bit) {
                    isBothTrap++;
                    //cout << pos << " next : " << i<< "++"<<endl;
                }
            }
            if(traps[t] == i) {
                if((int)pow(2,t)&bit) {
                    isBothTrap++;
                    //cout << pos << " next : " << i<< "++"<<endl;
                }
            }
        }
        if(isBothTrap % 2 == 0) goTime = maps[pos][i];  // 양쪽 트랩밣은 상태 확인 후 둘다 일경우 기본, 하나일경우 반전
        else goTime = maps[i][pos];
        //cout << pos << " next : " << i<< ", goTime : " <<goTime<< ", bit : " << bit << endl;
        //
        if(goTime == 0) continue;             //간선이 없을 경우
        //cout << pos << " next : " <<i<< endl;
        bool isTrap = false;
        int tsize = traps.size();
        int iBit=0;
        for(int j = 0; j<tsize; ++j){
            if(traps[j]==i) {           //이동할 위치가 트랩?
                isTrap = true;
                iBit = pow(2, j);
                if(bit & iBit) iBit = -1 * iBit;
            }  
        } 
        dps(n, i, cnt+goTime, end, traps, bit+iBit);
    }
    
}

int solution(int n, int start, int end, vector<vector<int>> roads, vector<int> traps) {
    int answer = 0;
    
    for(auto v : roads) { // 길이 두개여도 굳이 시간이 더 걸리는 길로 갈필요가 없음
        if(maps[v[0]][v[1]] == 0 || maps[v[0]][v[1]] > v[2]) maps[v[0]][v[1]] = v[2];
    }
    for(int i=0; i<1024; ++i) for(int j=0; j<1001; ++j) dis[i][j]=1e9;
    dps(n, start, 0, end, traps, 0);
    answer = ans;
    
    return answer;
}
/*
노드 한번 방문시 1000
    노드 방문 갯수 1000 x 1024
    */