문제 풀이
-
[프로그래머스] 단체사진 찍기문제 풀이 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이지만, 캐릭터가 처음 걸어본..
-
[프로그래머스] 외벽 점검문제 풀이 2020. 5. 29. 15:47
풀이)모든 경우를 다 확인해주면 되는 문제이다. 풀이과정은 이러하다.1. 원형탐색이여서, 주어진 weak배열을 두배로 늘린 배열을 하나 선언해준다. 거리계산을 원할하게 하기 위해서인데, 만일 weak = {1,5,6,10} , n =12이면 two_weak = {1,5,6,10,1+12,5+12,6+12,10+12} = {1,5,6,10,13,17,18,22} 이런식으로 저장해준다. 그러면, 10에서부터 출발해도 거리 계산하기 쉽다. 10 -> 1 : 10 -> 13까지니깐 거리 3 10 -> 5 : 10 -> 17까지니깐 거리 7 ** 시계방향만 고려한다. 모든 취약 지점에서의 경우를 다 봐줄 것이기에 반시계 방향은 생각해줄 필요 없다. 2. 각 취약 지점위치에서 친구들이 출발한다고 생각해, 각 위치마..
-
[프로그래머스] 다음 가장 큰 수문제 풀이 2020. 5. 28. 23:13
풀이)뭔가 공식이 있을까 싶어 여러 방법을 다해보다가 결국 n보다 큰 수들을 2진수로 변환해 탐색해나갔다. n+1부터 2진수로 바꾼 뒤 비트1의 개수를 센다 -> 비트1의 개수가 n과 같다면 stop하고 수를 반환. 코드)#include #include using namespace std; int change(int val){ //숫자를 이진수로 바꿔서 bit 1의 개수를 return int cnt =0; while(val>0){ if(val%2 == 1){ cnt++; } val /= 2; } return cnt; } int solution(int n) { int i = n+1; n = change(n); while(change(i) != n){ i++; } return i; } + 다른 분의 코드를 ..