본문 바로가기

Probelm Solving/Programmers5

2021 카카오 채용연계형 인턴십 ① #3 표 편집 간단해 보이나 효율성을 통과하기 위해 배열 외의 자료구조를 선택해야 했음 set을 이용한 풀이도 가능하지만 fenwick tree로도 풀 수 있다해 풀어봤다. 은근히 이분탐색에서 헷갈렸던;; 어떤 L을 찾는지 명확히 해야 헷갈리지 않는다. 시험 볼 당시에는 set을 활용하려 했으나 iterator 활용을 잘 못해 실패했던 것 같다... fenwick tree와 이분탐색을 이용함. 더보기 #include #include #include using namespace std; int N; stack S; int fen[1000001]; void upd(int idx, bool add) { if (add) while (idx 2021. 8. 18.
2020 카카오 인턴십 문제 ② 2020 카카오 인턴십 #4 보석 쇼핑 map과 two pointer을 사용해 푸는 문제 i부터 j까지 구간에 모든 보석을 가지고 있는가를 판단할 때 map을 사용, 아니라면 j, 맞다면 i를 증가하여 왼쪽에서 오른쪽으로 이동하며 가장 짧은 구간을 구한다. 처음엔 구간 길이에 대한 이분탐색으로 접근했다. 시간초과 났음 더보기 비슷한 문제를 다른 코테에서 본 적 있다. 이 문제의 2차원 버전이었는데,,, 아쉽다 map M; vector solution(vector gems) { vector answer; int N=gems.size(); // Gems for(string g:gems){ auto iter=M.find(g); if(iter==M.end()) M.insert({g,0}); } int G=M.s.. 2021. 5. 10.
2019 카카오 개발자 겨울 인턴십 문제 ② 2019 카카오 개발자 겨울 인턴십 #4 징검다리 건너기 오래 고민하고 겨우 푼 다음 정확성 효율성 다 발리고 질문하기 참고해 이분탐색임을 깨달음...... 아효 이렇게 간단히 풀리는 것을 더보기 무려 스택을 이용해 풀어봤지만 효율성은 둘째치고 정확성이 해결되지 않앗음 흠 int l=1, r=INF; int mid=(l+r+1)>>1, cnt=0; while(l=mid) cnt=0; else { cnt++; if(cnt>=k) { ava=false; break; } } } if(ava) l=mid; else r=mid-1; mid=(l+r+1)>>1; } answer=mid; #5 호텔 방 배정 disjoint set으로 풀었는데 수의 범위때문에 hash한 번 해줬다. 처음엔 새로운 숫자에 대해 {인덱스.. 2021. 5. 5.
2020 카카오 인턴십 문제 ① 2020 카카오 인턴십 문제 #1 키패드 누르기 조건을 헷갈리지 않고 구현하면 됨 각 숫자의 위치를 저장해두고 문자열을 구했다. 더보기 /* 1 2 3 1,4,7 => L n=0일 때 주의 4 5 6 3,6,9 => R 7 8 9 else => rdist,ldist 계산, hand 고려 * 0 # */ string solution(vector numbers, string hand) { string answer = ""; int pos[12][2]; pos[0][0]=3, pos[0][1]=1; pos[10][0]=3, pos[10][1]=0; pos[11][0]=3, pos[11][1]=2; int num=1; for(int r=0;r tmp) ? answer : tmp; } return answer; .. 2021. 5. 2.
2019 카카오 개발자 겨울 인턴십 문제 ① 2019 카카오 개발자 겨울 인턴십 #1 크레인 인형뽑기 게임 스택 문제. 벡터로 구현했다. 더보기 #include #include using namespace std; int solution(vector board, vector moves) { int answer = 0; vector v;// as Stack int N = board.size(); for (int m : moves) { // Find position int idx = 0; while (idx < N && !board[idx][m-1]) idx++; // Pick Up & Get Answer if (idx < N) { int tar = board[idx][m-1]; board[idx][m-1] = 0; if (!v.empty() && t.. 2021. 4. 16.