분류 전체보기
-
[프로그래머스] 외벽 점검문제 풀이 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; } + 다른 분의 코드를 ..
-
bitset 사용법잡다한 지식 2020. 5. 28. 23:02
bitset STL- 원하는 비트를 사용하기 위해 쓰는 STL이다.- 고정된 크기의 비트 배열을 뜻한다.- #include 을 해야 사용가능- 사용법①bitset 이름 => 선언방법 ex) bitset bit; //20개 비트 수를 가지는 bit변수②이름.set() => 전체비트를 1로 바꿈③이름.reset() => 전체비트를 0으로 바꿈④이름.set(n,true/false) => n+1번째 비트를 1또는 0으로 바꿈⑤이름.size() => bitset의 크기반환⑥이름.flip(n) => n+1 번째 비트를 반전시킴⑦이름.to_string() => 전체비트를 string으로 바꿔준다.⑧이름.all() => 모든 비트가 1이면 true반환⑨이름.any() => 비트 중에서 1인 비트가 있으면 true 반환..
-
[프로그래머스] 기둥과 보문제 풀이 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랑 같은 문자열이..