본문 바로가기
반응형

[알고리즘 + 자료구조]/[프로그래머스]82

프로그래머스 거리두기 확인하기 카카오 채용연계형 인턴십 문제이다. 2021년 당시에는 풀지도 못한 문제였는데. 2년이 지난 지금, 20분만에 풀었다. 나는 BFS를 이용해 풀었는데, depth를 계산하다가 맨헤튼 거리가 2가 넘어가는 순간 실패로 책정했다. #include #include #include #include // 20 using namespace std; bool visit[5][5]; int mx[4] = {0, 0, -1, 1}; int my[4] = {1, -1, 0, 0}; bool bfs(vector& place, int sx, int sy) { queue que; que.push({{sx, sy}, 0}); visit[sx][sy] = true; while(!que.empty()) { int x = que.fr.. 2023. 10. 9.
프로그래머스 후보키 C++ 이번 문제는 카카오 blind 코딩테스트 문제이다. 오랜만에, 풀이하는데 정말 오랜 시간이 걸린 문제였다 ㅜ..ㅜ 문제의 핵심은 두가지이다. 1. 유일성 각 col을 뽑은 값이 tuple 내에서 유일해야한다 2. 최소성 각 col을 뽑은 것이 부분집합으로 존재하지 않는, 최소가 되어야 한다. 우선 내 처음 풀이는 일반적으로 내가 주로 사용하는 dfs 코드 방식의 풀이었다. 처음에는 맞추지조차 못했는데, 그 이유는 두가지였다. 1. 먼저 일반적인 dfs 과정에서 0 1 2 3 4 를 순회한다고 보면 0 1 2 3 4 를 당연히 제일 먼저 순회하게 된다. 근데 난 여기서 이게 유일성이 된다면 곧바로 후보키에 넣었지만 이후에 탐색될 2 3 이나 2 4가 후보키라면, 0 1 2 3 4 는 후보키가 되어선 안된다.. 2023. 10. 5.
프로그래머스 문자열 압축 C++ 카카오 블라인드 문제 중 하나이다. 한시간 정도 소요되었다. 처음에 map을 이용해서 카운팅한뒤에 누적합을 이용했는데 aabbaccc -> 3a2b3c 라는 결과가 나왔는데 aabbaccc -> 2a2ba3c 이 정답이다. 이 접근은 잘못된 접근이다. 이 문제는 주어진 대로의 구현으로만 진행해도 문제를 해결할 수 있다. 정답을 풀고 찾아보니 다른 사람들의 풀이와도 비슷했다. 참고로, 자를 단위의 최대는 주어진 문자열 길이의 /2 까지만 해주면 된다! #include #include #define MIN(a, b) ((a < b) ? a : b) using namespace std; int solution(string s) { int len = s.length(); int answer = len; // i.. 2023. 10. 4.
프로그래머스 순위 검색 C++ 어려웠다.. 다른 사람의 풀이를 참고해서 공부한 뒤에 풀었다. 어떤 분은 비트마스킹으로 풀기도 했다. 쩔더라. 다시 한 번, 까먹을까봐 메모해놓는 부분은 lower_bound()는 iterator를 리턴한다는점. lower_bound()는 이상 이니까, 문제에서 필요한 이상 과도 매칭이 잘 된다. #include #include #include #include #include using namespace std; vector solution(vector info, vector query) { vector answer; map scores; string ta[4][2] = { {"-", ""}, {"-", ""}, {"-", ""}, {"-", ""} }; for(auto i : info) { string.. 2023. 10. 2.
반응형

티스토리툴바