문제풀이/프로그래머스

[프로그래머스 문제풀이] 배달 문제풀이

문제를 풀 때 Dijkstra 을 풀면 된다. 음수를 표현 #include #include #include using namespace std; int INF = 10000000; vector map[51]; int result[51]; void dijkstra(int start){ result[start] = 0; //짧은거리를 표현하기 위해 priority_queue 사용 priority_queue pq; pq.push(make_pair(start, 0)); while(!pq. empty()){ int n = pq.top().first; int d = -pq.top().second; pq.pop(); //result[n]이 distance면 패스 if(result[n]

[프로그래머스 문제풀이] 더 맵게 문제풀이

우선순위 큐를 생각하자,, 우선운위큐의 존재만 안다면 쉽게 풀 수 있는 문제였다. vector로 풀었더니 효율성 test를 아예 통과하지 못한다. 우선순위큐 사용 방법 다시 생각하기 #include #include #include using namespace std; int solution(vector scoville, int K) { int answer = 0; priority_queue pq; for(int i=0;i

[프로그래머스] 다음 큰 숫자 문제풀이

bitset 의 존재만 알고 자세히 다루진 못했는데 이 문제를 풀면서 bitset에대해 더 알게 되었다. 다른문제풀이를 보니 계속 2로 나누어서 1의 개수를 세는 문제풀이도 있었고 , biset 의 함수중에 count 라는 함수를 써서 엄청 짧게 푼 문제풀이도 있었다. 많이 알 수록 간단해 지는것 같다. #include #include #include using namespace std; int solution(int n) { int answer = 0; bitset bit(n); string s1 = bit.to_string(); int ones=0; for(int i=0;i

[C++]2020 KAKAO BLIND RECRUITMENT 2번문제

이 문제는 국어문제가 더 비슷한것 같다 문제만 이해한다면 풀수있을것이다 딱히 중요하게 사용한 것들은 없는거 같다 #include using namespace std; bool check(string str){//올바른 괄호 문자열인가 ? int open=0; int close=0; for(int i=0;i

[C++]2020 KAKAO BLIND RECRUITMENT 1번문제

딱히 어려운 개념은 없고 문제만 똑바로 읽으면 풀 수 있는 문제였다. 테스트케이스 5번이 자꾸 오류가 났는데 테스트케이스의 string 길이가 1이였다... 하나만 유독 이상할 땐 특이한 케이스를 생각해보자 #include #include using namespace std; int solution(string s) { int answer = 10000000; if(s.length()==1)answer=1; else{ for(int i=1;i

프로그래머스 타겟 넘버 문제풀이

문제를 보고 DFS 를 이용하여 풀려고 했으나 또 순서를 생각해서 풀려고 하여 헷갈렸다. 내가 아니라 컴퓨터가 돌리게 하자 문제는 간단하였다. dfs 함수에서 numbers 에 있는 숫자들을 더하기 , 빼기 연산을 했을때 연산횟수가 cnt 와 같아질때 그 값들이 target 과 같았을 때 answer 을 1을 더해주면 된다. #include #include int answer=0; using namespace std; void dfs(vectornumbers,int tg, int sum, int cnt){ if(cnt==numbers.size()){ if(sum==tg)answer++; return; } dfs(numbers, tg, sum + numbers[cnt], cnt + 1); dfs(numbe..

프로그래머스 전화번호 목록 문제 풀이

처음 문제를 보았을 때 제일 먼저 생각한것이 phone_book 안에 있는 요소들을 하나씩 비교해서 첫 번째 요소가 다른 요소들의 접두사가 된다면 비교를 끝내고 false 를 return 하고 끝이라고만 생각했다 문제를 풀면서 몇가지 문제들이 있었는데 내가 생각하지 못한 부분은 첫 번째 요소의 size가 요소들중 제일 짧은 요소가 아니란 점 answer 를 true 로 두었을 때 첫 번째 요소만 돌고 끝날 수 있다. 이를 해결하기 위해 첫 번째 요소가 제일 짧은 요소가 되게 sort 함수를 이용 하였고 check 를 사용하여 첫 번째 요소만 돌고 끝내지 않게 하였다. 다른 사람의 풀이를 보았을때 substr를 이용할 수 있었으면 훨씬 빠르고 간결하게 풀 수 있었을 것 같다. 다음 부턴 string을 비교..