문제 풀이
-
[프로그래머스] 스티커 모으기(2)문제 풀이 2020. 10. 2. 17:56
스티커 모으기(2) 문제) https://programmers.co.kr/learn/courses/30/lessons/12971 풀이)dp를 이용해서 풀어야 하는 문제다 점화식dp[i] = i번째 스티커를 뗄 경우, 지금까지 얻을 수 있었던 점수의 최대값 dp[i] = max(dp[i-2] + sticker[i], dp[i-1]) //i번째 스티커를 뗄 경우, i-2번째 스티커를 뜯어낸 후 합쳐왔던 점수에 i번째 스티커 점수 합침 i번째 스티커를 떼지 않을 경우, i-1번째 스티커를 뜯어낸 후 합쳐왔던 점수 가져옴 * 주의점 *원형으로 연결되어 있기에, 첫번째 스티커를 뜯어낼 경우 마지막 스티커를 뜯지 못한다.이를 위해 첫번째 스티커를 뜯었을 경우와 아닐 경우를 나눠서 계산해본다. 코드)include #..
-
[프로그래머스] JadenCase 문자열 만들기문제 풀이 2020. 10. 1. 16:47
JadenCase 문자열 만들기 문제) https://programmers.co.kr/learn/courses/30/lessons/12951 풀이)A의 아스키 코드가 65, a의 아스키 코드가 97 임을 이용해서 소문자↔대문자를 바꿔줬는데 12345678910111213141516171819202122232425262728293031#include #include using namespace std; string solution(string s) { string answer = ""; //A 65 a 97 if(s[0] >= 'a' && s[0] = 'a' && s[i] = 'A' && s[i]
-
[프로그래머스] 쿠키 구입문제 풀이 2020. 9. 30. 17:37
쿠키구입 문제) https://programmers.co.kr/learn/courses/30/lessons/49995 풀이)투포인터를 이용해서 푼 문제이다. 과정1. for문을 통해 인덱스 0 ~ cookie.size() - 2 까지 차례로 시작 인덱스 start 로 정한다. 1.1. 시작인덱스 start + 1 을 마지막 인덱스 end 로 둔다. 1.2. (0 ~ 시작 인덱스 start) / (마지막 인덱스 end ~ cookie.size() - 1) 범위로 나눠 start와 end 두 인덱스 포인터를 이동시키며 두 쿠기 구간의 합을 비교한다. *start 포인터는 왼쪽으로 이동, end 포인터는 오른쪽으로 이동한다. *오른쪽 구간의 합이 크면, 왼쪽 구간을 늘린다 = start 포인터를 한칸 왼쪽으로..
-
[프로그래머스] 보석 쇼핑문제 풀이 2020. 9. 28. 15:22
보석 쇼핑 풀이)처음에는인덱스 0부터 ~ 모든 보석을 포함하는 마지막 인덱스를 찾고, 그 안에서 구간을 줄여나가면서 풀었더니틀렸던 문제다.예외 존재) ["DIA","EM","EM","RUB","DIA"] 일경우 answer = [3, 5] output = [1, 4] 가 나옴 그렇다고 2중 포문을 사용해서 구간을 찾기에는 보석 배열이 100,000 크기까지 될 수 있으므로 시간초과가 생긴다. => 투포인터 방법을 사용해서 풀어야 하는 문제이다. unordered_map, 투 포인터 사용 풀이법 1. 먼저 보석의 총 개수를 unordered_map을 이용해서 구한다. 2. left, right 두 개의 인덱스 포인터를 이용해서 가장 짧은 구간을 찾는다. -> left와 right 인덱스를 조건을 생각하며 ..
-
[프로그래머스] 수식 최대화문제 풀이 2020. 9. 26. 18:42
수식 최대화 문제)https://programmers.co.kr/learn/courses/30/lessons/67257 풀이)next_permutation으로 연산자의 우선순위를 바꿔주면서 푼 문제이다. #include #include #include using namespace std; bool cardi[3];// + - * long long solution(string expression) { long long answer = 0; vector number; vector oper; string s; for (int i = 0; i
-
[프로그래머스] 경주로 건설문제 풀이 2020. 9. 25. 18:01
경주로 건설 문제) https://programmers.co.kr/learn/courses/30/lessons/67259 풀이)헤매다가 질문글을 보고 오류를 찾은 문제이다. 참고 질문글) https://programmers.co.kr/questions/12180 PQ와 DP를 이용하고, 새로운 비용이 작거나 같을 경우만 무조건 업데이트 시키면서 이동가능하게 했었는데이동 방향에 따라 비용의 대소가 역전되는 경우가 있었다. 그래서 DP를 이용할 때 방향까지 저장해서 풀었다. int dp[i][j][k] = (i,j)위치에 k방향으로 도달했을 때까지 든 최소 비용 과정1. 비용을 Memoization할 배열을 모두 나올 수 없는 최대 비용으로 초기화.( INF = 987654321 )2. 처음 출발할 칸 즉,..
-
[프로그래머스] 동굴 탐험문제 풀이 2020. 9. 24. 15:46
동굴 탐험 문제) https://programmers.co.kr/learn/courses/30/lessons/67260 풀이) 처음에 dfs(방 탐색시 이용), before[]배열(이전에 꼭 방문해야하는 방 번호 저장), parent[]배열(트리 상에서 자식보다 먼저 방문해야하는 방 번호 저장) 을 이용해서 풀어보았지만 효율성면에서 떨어져서 다르게 풀어야했다. 효율성을 통과하지 못한 코드) 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667#include #include #include #include #include using na..