분류 전체보기
-
[프로그래머스] 뉴스클러스터링문제 풀이 2020. 6. 2. 21:53
풀이)unordered_map 을 사용해서 푼 문제이다. 풀이과정은 이러하다.1. 문자열 str1과 str2 각자 2글자씩 잘라서 원소를 만든다. (이 때, 2글자 중 영문자가 아닌 숫자, 기호 등이 오면 그 경우는 넘어간다.영문자는 대문자로 통일시켜놓는다.)2. 만들어진 원소들을 key로 생각하고, map을 통해 다중집합내에 같은 원소가 몇 개 저장되는 지 알아둔다.3. 문자열 str1의 원소들을 둘러보며, str2에서 만든 원소와 같을 경우 둘 중 원소의 개수가 적은 것은 교집합에 넣는다. 그러면, 교집합의 수를 구할 수 있다. 합집합의 경우, 전체 원소의 수 - 교집합 원소의 수 = 합집합 원소 수 임을 이용해서, 합집합도 구할 수 있다. 코드)#include #include #include usi..
-
[프로그래머스] 점프와 순간이동문제 풀이 2020. 6. 2. 13:42
문제 설명OO 연구소는 한 번에 K 칸을 앞으로 점프하거나, (현재까지 온 거리) x 2 에 해당하는 위치로 순간이동을 할 수 있는 특수한 기능을 가진 아이언 슈트를 개발하여 판매하고 있습니다. 이 아이언 슈트는 건전지로 작동되는데, 순간이동을 하면 건전지 사용량이 줄지 않지만, 앞으로 K 칸을 점프하면 K 만큼의 건전지 사용량이 듭니다. 그러므로 아이언 슈트를 착용하고 이동할 때는 순간 이동을 하는 것이 더 효율적입니다. 아이언 슈트 구매자는 아이언 슈트를 착용하고 거리가 N 만큼 떨어져 있는 장소로 가려고 합니다. 단, 건전지 사용량을 줄이기 위해 점프로 이동하는 것은 최소로 하려고 합니다. 아이언 슈트 구매자가 이동하려는 거리 N이 주어졌을 때, 사용해야 하는 건전지 사용량의 최솟값을 return하..
-
[프로그래머스] 단체사진 찍기문제 풀이 2020. 6. 1. 16:42
풀이)순열을 이용해 모든 경우를 확인한 경우다. 풀이과정1. {A,C,F,J,M,N,R,T} 집합을 순열로 나올 수 있는 경우를 본다.2. 그 경우를 모든 조건과 비교하여, 참이 나올 경우 answer의 값을 하나 증가시켜준다. 조건 중 하나라도 위배되면 다음 순열로 넘어간다. 순열을 algorithm header의 next_permutation()함수를 이용해 주었다. 코드)#include #include #include using namespace std; // 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요. int solution(int n, vector data) { int answer = 0; vector ch = {'A','C','F','J','M','N','R','T'};..
-
[프로그래머스] 보행자 천국문제 풀이 2020. 6. 1. 00:25
문제 설명보행자 천국카카오내비 개발자인 제이지는 시내 중심가의 경로 탐색 알고리즘 개발 업무를 담당하고 있다. 최근 들어 보행자가 자유롭고 편리하게 걸을 수 있도록 보행자 중심의 교통 체계가 도입되면서 도심의 일부 구역은 자동차 통행이 금지되고, 일부 교차로에서는 보행자 안전을 위해 좌회전이나 우회전이 금지되기도 했다. 복잡해진 도로 환경으로 인해 기존의 경로 탐색 알고리즘을 보완해야 할 필요가 생겼다.도시 중심가의 지도는 m × n 크기의 격자 모양 배열 city_map으로 주어진다. 자동차는 오른쪽 또는 아래 방향으로 한 칸씩 이동 가능하다.city_map[i][j]에는 도로의 상황을 나타내는 값이 저장되어 있다.0인 경우에는 자동차가 자유롭게 지나갈 수 있다.1인 경우에는 자동차 통행이 금지되어 지..
-
[프로그래머스] 최고의 집합문제 풀이 2020. 5. 31. 15:53
문제 설명자연수 n 개로 이루어진 중복 집합(multi set, 편의상 이후에는 집합으로 통칭) 중에 다음 두 조건을 만족하는 집합을 최고의 집합이라고 합니다.각 원소의 합이 S가 되는 수의 집합위 조건을 만족하면서 각 원소의 곱 이 최대가 되는 집합예를 들어서 자연수 2개로 이루어진 집합 중 합이 9가 되는 집합은 다음과 같이 4개가 있습니다. { 1, 8 }, { 2, 7 }, { 3, 6 }, { 4, 5 } 그중 각 원소의 곱이 최대인 { 4, 5 }가 최고의 집합입니다.집합의 원소의 개수 n과 모든 원소들의 합 s가 매개변수로 주어질 때, 최고의 집합을 return 하는 solution 함수를 완성해주세요.제한사항최고의 집합은 오름차순으로 정렬된 1차원 배열(list, vector) 로 retu..
-
[프로그래머스] 불량 사용자문제 풀이 2020. 5. 30. 19:05
문제 설명개발팀 내에서 이벤트 개발을 담당하고 있는 무지는 최근 진행된 카카오이모티콘 이벤트에 비정상적인 방법으로 당첨을 시도한 응모자들을 발견하였습니다. 이런 응모자들을 따로 모아 불량 사용자라는 이름으로 목록을 만들어서 당첨 처리 시 제외하도록 이벤트 당첨자 담당자인 프로도 에게 전달하려고 합니다. 이 때 개인정보 보호을 위해 사용자 아이디 중 일부 문자를 '*' 문자로 가려서 전달했습니다. 가리고자 하는 문자 하나에 '*' 문자 하나를 사용하였고 아이디 당 최소 하나 이상의 '*' 문자를 사용하였습니다. 무지와 프로도는 불량 사용자 목록에 매핑된 응모자 아이디를 제재 아이디 라고 부르기로 하였습니다.예를 들어, 이벤트에 응모한 전체 사용자 아이디 목록이 다음과 같다면응모자 아이디frodofradic..
-
[프로그래머스] 길 찾기 게임문제 풀이 2020. 5. 30. 16:15
풀이)이진탐색트리를 구현하면 되는 문제이다. 풀이과정은 이러하다. 1. 각 node의 번호를 좌표 옆에 삽입시켜 준다. (탐색 시 노드 번호를 출력하기 위해서)2. 각 node들을 좌표순으로 정렬해준다. (원래 이진탐색트리는 삽입 순서에 따라 트리모양이 달라지지만, 이 문제에서는 (x,y)좌표 순으로 노드들이 이진트리를 구성하기 때문에 삽입순서가 중요하지 않다.좌표가 중요하다. y좌표가 높은 순, y좌표가 같다면 x좌표가 작은 순으로 나열한다.)3. 각 노드들로 이진탐색트리를 만들어 순회 경로를 출력한다. 전위순회는 나 자신 -> 왼쪽자식 ->오른쪽 자식 순이고 후위순회는 왼쪽자식 ->오른쪽자식 ->나 자신 순이다. 코드)#include #include #include #include using name..
-
[프로그래머스] 방문길이문제 풀이 2020. 5. 30. 00:08
문제 설명게임 캐릭터를 4가지 명령어를 통해 움직이려 합니다. 명령어는 다음과 같습니다.U: 위쪽으로 한 칸 가기D: 아래쪽으로 한 칸 가기R: 오른쪽으로 한 칸 가기L: 왼쪽으로 한 칸 가기캐릭터는 좌표평면의 (0, 0) 위치에서 시작합니다. 좌표평면의 경계는 왼쪽 위(-5, 5), 왼쪽 아래(-5, -5), 오른쪽 위(5, 5), 오른쪽 아래(5, -5)로 이루어져 있습니다.예를 들어, ULURRDLLU로 명령했다면1번 명령어부터 7번 명령어까지 다음과 같이 움직입니다.8번 명령어부터 9번 명령어까지 다음과 같이 움직입니다.이때, 우리는 게임 캐릭터가 지나간 길 중 캐릭터가 처음 걸어본 길의 길이를 구하려고 합니다. 예를 들어 위의 예시에서 게임 캐릭터가 움직인 길이는 9이지만, 캐릭터가 처음 걸어본..