Algorithm/프로그래머스

[프로그래머스] level2 전화번호 목록 (C++)

C++에서 map을 사용한 해시로 쉽게 풀 수 있다. 나는 보자마자 트라이를 쓰는 문제 같았다. 해시를 떠올리지 못했다. 해시로 푸는 방법은 아래 블로그 참고 [Programmers] 전화번호 목록 간단한 문자열 문제입니다. 백준에서 골드 4정도의 완전히 동일한 문제가 있습니다. 동일한 문제이지만, 이... blog.naver.com 트라이의 특징은 문자열의 종료 위치를 표시해준다는 점이다. 따라서 주어진 배열을 먼저 길이 순으로 오름차순 정렬하고, 길이가 같은 경우에는 문자열의 값에 따라 오름차순 정렬한다. 이렇게 먼저 정렬해주면 뒤에 나오는 문자열이 그보다 앞에 나오는 문자열의 접두사인 경우를 배제할 수 있다. 그렇게 트라이로 풀 수 있는 조건이 성립하게 된다. 트라이에 문자를 하나씩 넣으면서 트라이..

[프로그래머스] level2 단체사진 찍기 (C++)

2017 카카오코드 본선 사람이 8명 뿐이다. 모든 사람을 줄세우는데 O(8!) 만큼의 시간이 걸릴 것이다. 따라서 백트래킹으로 모든 경우를 탐색해도 시간내에 충분히 풀린다. 백트래킹 부분 void sorting(int cnt, int &answer, vector &data, map &m){ if(cnt == 8){ if(is_valid(data, m)){ answer++; } return; } for(int i = 0; i < 8; i++){ if(visited[i]) continue; visited[i] = cnt+1; sorting(cnt+1, answer, data, m); visited[i] = 0; } } 중요한 부분은 visited배열의 정의이다. visited배열의 인덱스는 사람의 번호이다..

[프로그래머스] level2 빛의 경로 사이클 (C++)

월간 코드 챌린지 시즌 3 그림만 보면 무시무시하지만 실제 풀이는 그렇지 않다. 하나의 격자에 빛을 쏘면 내부에서 사이클을 이룬다. 내부에서 퍼지는 게 아니라 하나의 길로 쭉 들어간다고 생각해서 바로 dfs로 풀었다. bool cache[501][501][4]; cache 배열이 중요하다 cache[r][c][dir] r, c 의 격자에 dir 방향으로 들어온 적이 있는지를 체크하는 배열이다. 나는 dir 방향으로 들어온 적이 있다면 반드시 그 경우에 해당하는 사이클이 존재한다고 생각했다. 적어도 위 예제만 봐도 모든 경로를 다 탐색한다. 만약 다른 예제가 오더라도 아직 방문하지 않은 경로를 시작점으로 탐색을 하는데, 이미 탐색한 다른 경로를 건드릴일이 절대로 없다는 것이다. bool &ret = cac..

[프로그래머스] level2 튜플 (C++)

2019 카카오 겨울 인턴십 배열이 주어지고, 튜플을 만드는 방법을 문제에서 친절히 알려줬다. 원소의 개수가 n개이고, 중복되는 원소가 없는 튜플 (a1, a2, a3, ..., an)이 주어질 때(단, a1, a2, ..., an은 자연수), 이는 다음과 같이 집합 기호 '{', '}'를 이용해 표현할 수 있습니다. {{a1}, {a1, a2}, {a1, a2, a3}, {a1, a2, a3, a4}, ... {a1, a2, a3, a4, ..., an}} 예를 들어 튜플이 (2, 1, 3, 4)인 경우 이는 {{2}, {2, 1}, {2, 1, 3}, {2, 1, 3, 4}} 문제에서 원하는 답은 튜플을 분석해서 원래의 배열을 구하라는 것이다. 문제는 튜플이 문자열로 주어진다는 것이다.. 나는 C++..

[프로그래머스] level2 행렬 테두리 회전하기 (C++)

2021 Dev 매칭-벡엔드 2차원 좌표에서 직사각형을 정하고, 테두리를 시계방향으로 회전시키는것을 구현하는 문제이다. 완전히 구현력을 요구하는 문제이다. 삼성 A형 기출문제와 느낌이 비슷했다. 직사각형과 회전시킬 영역이 주어진다. 나는 회전을 위해서는 4개의 꼭짓점만 알면 된다고 생각했다. 그래서 주어지는 queries배열에서 4개의 꼭짓점을 추출하고, 되돌아오는 것 까지 생각해서 총 5개의 점을 vertex 벡터에 입력했다. for(auto &q: queries){ vector vertex; vertex.push_back({q[0], q[1]}); vertex.push_back({q[0], q[3]}); vertex.push_back({q[2], q[3]}); vertex.push_back({q[2]..

[프로그래머스] level2 메뉴 리뉴얼 (C++)

2021 카카오 블라인드 채용 문제를 읽어봤는데 요구사항을 한 번에 이해하지 못했다. 카카오 문제 특징인 것 같다. 지문이 너무 길다.. 그래서 처음 풀때는 시간내에 풀지 못하고 풀이만 어렴풋이 생각해둔채로 넘겼었다. 다시 풀기위해서 차분하게 풀이를 머릿속에 모두 정리하고 코딩에 들어갔다. 개인적으로 깔끔하게 풀린것같아서 마음에 드는 코드이다. 먼저 orders로 들어온 string을 오름차순 정렬하기 위해서 char로 모두 분해한 다음에 알파벳 순으로 정렬해서 2차원 벡터 형태로 만들어줬다. vector norders; for(auto str: orders){ vector temp; for(int i = 0; i < str.size(); i++){ temp.push_back(str[i..

[프로그래머스] level2 수식 최대화 (C++)

풀이 주어진 표현식을 숫자와 연산자로 나눈 후 각각 다른 배열에 넣어준다. 기본적인 백트래킹을 사용해 '*+-'로 구성된 연산자의 순서를 정해준다. 백트래킹의 마지막 부분에 도달해 연산자의 순서가 정해지면 표현식을 순서대로 계산한다. 현재 표현식의 연산자(forj)와 우선순위에 따른 연산자(fori)가 동일한 경우에 값을 계산해서 적절한 위치에 값을 갱신해준다. 그리고 사용한 연산자와 숫자는 erase메서드를 사용해서 지워준다. 여기서 주의할 점은 벡터를 for문으로 순회하는 도중에 원소가 지워지면 인덱스에 문제가 생길 수 있다. 따라서 현재 인덱스를 지워진 원소의 개수만큼 빼줘야 한다. 계산된 값을 비교하면서 최댓값을 저장해둔다. #include #include #include using namespa..

[프로그래머스] level2 거리두기 확인하기

단순 bfs, dfs 문제이다. 최대 2칸까지 이동할 수 있다. 다음 칸이 'X'인 경우 이동하지 않는다. 다음 칸이 'P'인 경우 거리두기가 지켜지지 않은 것이므로 false를 반환한다. bfs로 풀면 queue의 각 원소가 현재 몇 칸 움직인 상태인지 저장해두는 작업이 필요해서 queue를 구성하는 struct를 새로 구현하게 되었다. #include #include #include #include #define pii pair using namespace std; struct Info{ pii now; int cnt; }; int dr[4] = {0, 0, 1, -1}; int dc[4] = {1, -1, 0, 0}; int Map[6][6]; bool check(int r, int c){ queu..

[프로그래머스] level2 뉴스 클러스터링

나는 문제를 잘못읽어서 2시간 넘게 삽질했다. 두 글자씩 끊어서 다중 집합을 만든다. 이때 집합에 특수 기호나 숫자가 들어있을 경우 그 쌍은 버린다. 이 조건을 잘못 읽었다. 어떻게 잘못 읽었냐면 주어진 문자열에서 특수 기호나 숫자를 먼저 모두 지워버리고, 특수 기호나 숫자가 없는 쌍을 만드는 걸로 착각했다. 당연히 특수 기호나 숫자를 먼저 지워버리면 제대로된 값이 나오지 않을 것이다. ex) 예제 2, 3번 풀이 입력 받은 문자열을 모두 대문자로 바꿔준다. 문자열을 2개씩 끊어서 새로운 배열에 넣어준다. 이때 2개의 문자 중 특수 기호나 숫자가 있으면 배열에 넣지 않고 넘어간다. 배열의 길이는 최대 999 * 999 = 약 100만 이다. 따라서 N^2 풀이가 가능하다고 생각했다. 2개의 배열을 가지고..