기로에 서다

문제 https://programmers.co.kr/learn/courses/30/lessons/84021 코딩테스트 연습 - 3주차 [[1,1,0,0,1,0],[0,0,1,0,1,0],[0,1,1,0,0,1],[1,1,0,1,1,1],[1,0,0,0,1,0],[0,1,1,1,0,0]] [[1,0,0,1,1,0],[1,0,1,0,1,0],[0,1,1,0,1,1],[0,0,1,0,0,0],[1,1,0,1,1,0],[0,1,0,0,0,0]] 14 [[0,0,0],[1,1,0],[1,1,1]] [[1,1,1],[1,0,0],[0,0,0]] 0 programmers.co.kr 풀이 1. 우선 해야 하는 걸 간단하게 정리하자면 아래와 같습니다. 1. 게임 보드의 서로 인접한 빈 공간 좌표 집합들을 구합니다. 2...

문제 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 풀이 당시에 풀 때도 링크드리스트로 풀다가 삽질하고 set으로 방향을 틀었던 기억이 나는데 문제를 꼼꼼히 안읽으면 우왕좌왕 해매기 쉬운문제였던 것 같습니다. 다시 링크드리스트로 구현해봐야지,, 1. 주의 깊게 봐야하는 부분은 아래와 같습니다. ※ "이름"열에는 서로 다른 이름들이 중복없이 채워져 있다고 가정..

문제 https://programmers.co.kr/learn/courses/30/lessons/81302 코딩테스트 연습 - 거리두기 확인하기 [["POOOP", "OXXOX", "OPXPX", "OOXOX", "POXXP"], ["POOPX", "OXPXP", "PXXXO", "OXXXO", "OOOPP"], ["PXOPX", "OXOXP", "OXPOX", "OXXOP", "PXPOX"], ["OOOXX", "XOOOX", "OOOXX", "OXOOX", "OOOOO"], ["PXPXP", "XPXPX", "PXPXP", "XPXPX", "PXPXP"]] [1, 0, 1, 1, 1] programmers.co.kr 풀이 1. 5개의 대기실마다 검사를 해야하므로 하나의 대기실에 대해 검사하는 함수를 ..

문제 https://programmers.co.kr/learn/courses/30/lessons/81301 코딩테스트 연습 - 숫자 문자열과 영단어 네오와 프로도가 숫자놀이를 하고 있습니다. 네오가 프로도에게 숫자를 건넬 때 일부 자릿수를 영단어로 바꾼 카드를 건네주면 프로도는 원래 숫자를 찾는 게임입니다. 다음은 숫자의 일부 자 programmers.co.kr 풀이 1. 각 숫자에 해당하는 알파벳들을 map으로 저장해두고, s를 순회하며 찾은 숫자들을 관리합니다. 2. s를 다 돌고난 후, 찾은 숫자들에 자릿수들을 곱하여 원래 숫자를 찾을 수 있습니다. 코드 #include using namespace std; map m; void init(){ m["zero"] = 1; m["one"] = 2; m[..

문제 programmers.co.kr/learn/courses/30/lessons/76503 코딩테스트 연습 - 모두 0으로 만들기 각 점에 가중치가 부여된 트리가 주어집니다. 당신은 다음 연산을 통하여, 이 트리의 모든 점들의 가중치를 0으로 만들고자 합니다. 임의의 연결된 두 점을 골라서 한쪽은 1 증가시키고, 다른 한 programmers.co.kr 풀이 1. +, -하는 가중치가 같기에 모든 가중치의 합이 0이여야 결국 0으로 만들 수 있습니다. 따라서 0이 아니면 -1을 반환합니다. 2. 조금만 생각해본다면 연결된 두 점에 대해서 연산할 때, 리프부터 처리해서 루트로 올라와야 빠짐없이 0으로 만들 수 있습니다. 3. 트리임이 보장되었기에 0번노드를 루트로 잡고 dfs를 돌리는데 리프노드에선 연산..

문제 programmers.co.kr/learn/courses/30/lessons/76502 코딩테스트 연습 - 괄호 회전하기 programmers.co.kr 풀이 s를 왼쪽으로 회전시키는건 substr을 사용하여 해결할 수 있고, 회전한 문자열 s에 대해 괄호 쌍 여부 판별은 문자열 s에 대해 스택을 사용하여 구현할 수 있습니다. 시험중에 푼 코드이기에 괄호 처리 여부가 지저분하므로 추후에 정리해서 다시올리도록 하겠습니다.. 코드 #include using namespace std; const char o[] = { '(','[','{' }; const char c[] = { ')',']','}' }; bool can(string x) { vector st; for (char op : x) { int ..

문제 programmers.co.kr/learn/courses/30/lessons/76501 코딩테스트 연습 - 음양 더하기 어떤 정수들이 있습니다. 이 정수들의 절댓값을 차례대로 담은 정수 배열 absolutes와 이 정수들의 부호를 차례대로 담은 불리언 배열 signs가 매개변수로 주어집니다. 실제 정수들의 합을 구하여 re programmers.co.kr 풀이 문제에서 설명한대로 부호가 켜져있는 경우엔 양수, 꺼져있는 경우엔 음수로 각각 리턴 값에 더해주면 해결할 수 있습니다. 코드 #include using namespace std; int solution(vector absolutes, vector signs) { int answer = 0; for (int i = 0 ; i < signs.si..

문제 programmers.co.kr/learn/courses/30/lessons/72414 코딩테스트 연습 - 광고 삽입 시간을 나타내는 HH, H1, H2의 범위는 00~99, 분을 나타내는 MM, M1, M2의 범위는 00~59, 초를 나타내는 SS, S1, S2의 범위는 00~59까지 사용됩니다. 잘못된 시각은 입력으로 주어지지 않습니다. (예: 04:60:24, 11 programmers.co.kr 풀이 1. 시, 분, 초를 초로 변환한다면 배열을 사용해 구간의 누적 시간을 쉽게 관리할 수 있습니다. (v[i] = i ~ i +1초 누적시간) 2. logs를 순회하며 보는 재생시간의 시작 점부터 끝 점까지 일일이 체크하여 1초씩 더해준다면 시간 초과가 나기때문에 일단은 시작 점에 +1, 끝 점에..

문제 programmers.co.kr/learn/courses/30/lessons/72415 코딩테스트 연습 - 카드 짝 맞추기 [[1,0,0,3],[2,0,0,0],[0,0,0,2],[3,0,1,0]] 1 0 14 [[3,0,0,2],[0,0,1,0],[0,1,0,0],[2,0,0,3]] 0 1 16 programmers.co.kr 풀이 0. 어떤 종류의 카드를 제거한다고 할 때, 종류가 같은 카드 두 개를 찾으려고 매번 맵 전체를 순회하지않기 위해 카드의 종류별로 두 카드의 위치를 담아줍니다. [ line 86 ] 1. 모든 카드를 종류별로 제거해야하고 그 순서에 따라 움직이는 거리가 달라지기에 제거할 종류들의 순서를 next_permutation으로 구해줍니다. [ line 99 ~ 103 ] 2...

문제 programmers.co.kr/learn/courses/30/lessons/72413 코딩테스트 연습 - 합승 택시 요금 6 4 6 2 [[4, 1, 10], [3, 5, 24], [5, 6, 2], [3, 1, 41], [5, 1, 24], [4, 6, 50], [2, 4, 66], [2, 3, 22], [1, 6, 25]] 82 7 3 4 1 [[5, 7, 9], [4, 6, 4], [3, 6, 1], [3, 2, 3], [2, 1, 6]] 14 6 4 5 6 [[2,6,6], [6,3,7], [4,6,7], [6,5,11], [2,5,12], [5,3,20], [2,4 programmers.co.kr 풀이 1. N이 200이하로 작으므로 플로이드 와샬을 사용하여 $O(N^3)$내에 모든 정점..