문제 풀이
-
[프로그래머스] 기둥과 보문제 풀이 2020. 5. 28. 21:10
풀이)한가지 조건을 간과해서 오래 걸렸던 문제이다. 조건같은 좌표상에 기둥과 보가 둘 다 있을 수 있다. -> 따라서 좌표상에 있는 구조물을 표시하기 위해 삼중 배열 사용했다. int visited[102][102][2]; // visited[x][y][0] : (x,y)좌표일때 기둥이 지어진지 여부, visited[x][y][1] : (x,y)좌표일 때 보가 지어진지 여부 // visited[x][y][0] = 1 : (x,y)좌표에 기둥이 지어져 있다 라는 뜻이다. 설치 조건은 주어진 조건을 생각하여 작성했으나, 제거할때의 조건은 일일히 구현하기가 까다로웠다.그래서 그냥 제거를 먼저 해본 뒤 나머지 구조물들이 설치 조건을 만족하는 지 일일히 확인해보았다. 기둥이나 보 제거 -> 나머지 구조물 확인 -..
-
[프로그래머스] 폰켓몬문제 풀이 2020. 5. 28. 16:53
풀이)어려운 문제는 아니였지만 풀이 방법이 여러가지가 있어 남겨본다. 나같은 경우는 vector를 정렬해서, 중복되는 원소들을 지우는 코드를 사용했는데다른 분들은 unordered_map, unordered_set을 사용했다. vector의 unique함수 사용 코드)#include #include using namespace std; int solution(vector nums) { int count = nums.size()/2; sort(nums.begin(),nums.end()); nums.erase(unique(nums.begin(),nums.end()),nums.end()); return count
-
[프로그래머스] 튜플문제 풀이 2020. 5. 27. 18:26
풀이)주의할 점은 튜플의 집합 내의 원소 순서가 달라질 수 있다는 점이다.따라서, 원소의 수가 적은 집합부터 원소를 확인해야 할 필요가 있는 문제이다. 그래서 문자열을 집합대로 자른 뒤 길이 별로 정렬한 뒤 원소를 확인해줬다.나같은 경우는 {}안에 것을 모두 함께 뭉쳤다.(,도 포함해서)중복되는 원소는 bool visited[100001]을 통해서 확인해줬다. 코드)#include #include #include #include using namespace std; bool visited[100001];//중볻되는 원소 체크 bool cmp(const string &a, const string &b){ return a.length()
-
[프로그래머스] 자물쇠와 열쇠문제 풀이 2020. 5. 27. 16:03
풀이)완전탐색문제이다.key는 회전과 상하좌우 이동이 가능하다. 키가 자물쇠에 맞는지만 확인하면 되니깐, 회전은 오른쪽 회전만 다루도록 하겠다.키의 이동이 관건인데,이는 키가 자물쇠의 끝에서부터 걸쳐서 확인해보는 방법으로 해결하면 된다.열쇠의 가장 오른쪽 아랫부분과 자물쇠의 가장 위쪽 부분을 맞추는 경우부터열쇠의 가장 왼쪽 윗부분과 자물쇠의 가장 오른쪽 아래 부분을 맞추는 경우까지를 모두 해준다.lock의 크기 N + (key의 크기 M - 1)*2 범위를 map이라고 칭하겠다.키를 이동시키면서 그 때의 키가 걸쳐있는 범위의 map 값을 변화시킨다.map map 값이 0이면 -> 열쇠의 돌기와 자물쇠의 홈이 일치안함 , 2이면 -> 열쇠의 돌기와 자물쇠의 돌기가 일치해버림이므로, 0과 2가 나오면 그 경..
-
[프로그래머스] 문자열 압축문제 풀이 2020. 5. 26. 20:38
풀이)완전탐색문제이다.문자열을 앞에서부터 길이 1 ~ 문자열의 절반길이 +1 까지 자른 뒤, (묶는 단위가 절반이 넘으면 당연히 같을 수 없으므로)자른 문자열이 뒤에 있는지 확인해준 문제이다. 예시의 aabbacc로 설명하자면aabbaccc먼저 길이 1로 자른다.a -> a랑 같은 문자열이 있는 지 확인, 바로 뒤에 있음 -> 또 있는지 확인, 없어서 stopb -> b랑 같은 문자열이 있는 지 확인, 바로 뒤에 있음 -> 또 있는지 확인, 없어서 stopa -> a랑 같은 문자열이 있는 지 확인, 없음 stopc -> c와 같은 문자열이 있는 지 확인, 바로 뒤에 있음 -> 또 있는지 확인, 있음 -> 문자열 길이 끝나서 stop즉 2a2ba3c 그 다음 길이 2로 자른다aa -> aa랑 같은 문자열이..
-
[프로그래머스] 카카오 프렌즈 컬러링북문제 풀이 2020. 5. 26. 19:35
풀이)bfs를 가지고 쉽게 풀 수 있는 문제이다.모든 영역 좌표을 살피며, 색깔이 0이 아니고 이전에 방문하지 않았던 곳(좌표)이면 bfs를 호출하여 같은 컬러를 가지고 있는 영역을 방문 표시 해주면 된다. 코드)#include #include #include using namespace std; bool visited[100][100]; int dy[4] = {-1,1,0,0}; int dx[4] = {0,0,-1,1}; int bfs(int a,int b,int m,int n,vectorpicture){ queue qu; qu.push({a,b}); visited[a][b] = true; int cnt = 1; int color = picture[a][b]; //cout
-
[프로그래머스] 종이접기문제 풀이 2020. 5. 26. 00:37
풀이)규칙이 존재하는 문제다.중간값은 항상 0이고, i번째 접는 횟수라면 ( i - 1 접는 상태 값 + 중간 0 + i -1 접는 상태 대칭되는 값)이다. 아래 예시를 보면 더 이해가 쉬울 것이다. 중간값 0을 빨간색으로 뒀을때1번 접으면 : 02번 접으면 : 0 0 13번 접으면 : 0 0 1 0 0 1 14번 접으면 : 0 0 1 0 0 1 1 0 0 0 1 1 0 1 1 -> 2번째 값이 0 0 1일때 3번째 값은 0 0 1 + 0 + 0 1 1 코드) #include #include using namespace std; vector solution(int n) { vector answer; for(int i = 0 ; i = 0 ; j--) { //이전값과 대칭되는 값 answer.push_ba..
-
[프로그래머스] 스킬트리문제 풀이 2020. 5. 25. 23:08
문제 설명선행 스킬이란 어떤 스킬을 배우기 전에 먼저 배워야 하는 스킬을 뜻합니다.예를 들어 선행 스킬 순서가 스파크 → 라이트닝 볼트 → 썬더일때, 썬더를 배우려면 먼저 라이트닝 볼트를 배워야 하고, 라이트닝 볼트를 배우려면 먼저 스파크를 배워야 합니다.위 순서에 없는 다른 스킬(힐링 등)은 순서에 상관없이 배울 수 있습니다. 따라서 스파크 → 힐링 → 라이트닝 볼트 → 썬더와 같은 스킬트리는 가능하지만, 썬더 → 스파크나 라이트닝 볼트 → 스파크 → 힐링 → 썬더와 같은 스킬트리는 불가능합니다.선행 스킬 순서 skill과 유저들이 만든 스킬트리1를 담은 배열 skill_trees가 매개변수로 주어질 때, 가능한 스킬트리 개수를 return 하는 solution 함수를 작성해주세요.제한 조건스킬은 알파..