Tag: 프로그래머스

2022
0
Programming프로그래머스

프로그래머스 - 문자열 압축 Python

https://programmers.co.kr/learn/courses/30/lessons/60057 프로그래머스 - 문자열 압축 Cpp 프로그래머스 - 문자열 압축 Python 문제 풀이간단한 구현 문제다. 주어진 문자열을 substr 해서 문자열 비교를 통해 같은 문자열의 개수를 찾아내 압축된 문자열 형태로 만들어준 다음 압축된 문자열의 길이를 반환해주면 되는 문제다. 문제 전체 소스def solution(s): answer = '' if len(s) == 1: return len(s) for i in range(1, len(s)//2 + 1): sentence = '' count = 0 word = s[:i] for j in range(0, len(s), i): if s[j:j+i] == word: count += 1 else: if count > 1: sentence += (str(count) + word) else: sentence += (word) word = s[j:j+i] count = 1 if count > 1: sentence += (str(count) + word) else: sentence += (word) if len(answer) == 0: answer = sentence elif len(answer) > len(sentence): answer = sentence print(answer) return len(answer)

2021
0
Programming프로그래머스

프로그래머스 - 합승 택시 요금 (Cpp)

https://programmers.co.kr/learn/courses/30/lessons/72413 문제 풀이모든 간선의 weight가 음수가 아닌 값, 시작점 s에서 도착할 수 있는 거리의 최소 비용을 구하는 문제라 다익스트라를 이용해 문제를 해결할 수 있다. 시작점 s에서 시작해 x점까지 같이 이동하는 최소 비용 + x점에서 시작해 a점까지 이동하는 최소 비용 + x점에서 시작해 b점까지 이동하는 최소 비용 중에서 가장 값이 작은 값을 찾는 문제다.원리는 간단하지만 다익스트라에 대해 잘 알고 있어야 풀 수 있는 문제다. void dijkstra(int node) { for (int i = 1; i < 220; i++) { dist[node][i] = INF; } priority_queue<pair<int, int>> pq; pq.push(make_pair(0, node)); dist[node][node] = 0; while (!pq.empty()) { int nodeDist = -pq.top().first; int cntNode = pq.top().second; pq.pop(); if (dist[node][cntNode] != nodeDist) { continue; } for (pair<int, int> vertex : graph[cntNode]) { int nextWeight = nodeDist + vertex.second; int nextNode = vertex.first; if (nextWeight < dist[node][nextNode]) { dist[node][nextNode] = nextWeight; pq.push(make_pair(-nextWeight, nextNode)); } } }} 전체 소스 코드#include <bits/stdc++.h>using namespace std;const int INF = 987654321;long long dist[220][220];vector<vector<pair<int, int>>> graph;void dijkstra(int node) { for (int i = 1; i < 220; i++) { dist[node][i] = INF; } priority_queue<pair<int, int>> pq; pq.push(make_pair(0, node)); dist[node][node] = 0; while (!pq.empty()) { int nodeDist = -pq.top().first; int cntNode = pq.top().second; pq.pop(); if (dist[node][cntNode] != nodeDist) { continue; } for (pair<int, int> vertex : graph[cntNode]) { int nextWeight = nodeDist + vertex.second; int nextNode = vertex.first; if (nextWeight < dist[node][nextNode]) { dist[node][nextNode] = nextWeight; pq.push(make_pair(-nextWeight, nextNode)); } } }}int solution(int n, int s, int a, int b, vector<vector<int>> fares) { int answer = 0; graph = vector<vector<pair<int, int>>>(n + 1); for (vector<int> fare : fares) { int start = fare[0]; int end = fare[1]; int weight = fare[2]; graph[start].push_back(make_pair(end, weight)); graph[end].push_back(make_pair(start, weight)); } // dijkstra_start(s); for (int i = 1; i <= n; i++) { dijkstra(i); } long long minValue = INF; for (int i = 1; i <= n; i++) { if (minValue > dist[s][i] + dist[i][a] + dist[i][b]) { minValue = dist[s][i] + dist[i][a] + dist[i][b]; } } answer = minValue; return answer;}

0
Programming프로그래머스

프로그래머스 - 순위 검색 (JAVA)

https://programmers.co.kr/learn/courses/30/lessons/72412 문제 풀이이 문제는 그냥 문자열대 문자열로 부딪히게 되면 시간 초과가 날 수 밖에 없는 문제다. 선형적으로 풀면 info 배열의 최대 크기는 5만, query 배열의 최대 크기는 10만 이므로 최대 50억 연산을 하게 되므로 효율성 측면에서 문제가 생긴다.결국 이 문제는 어떤 방법을 이용해 검색할 것인가가 가장 큰 관건이 된다. 선형적인 탐색을 하는 방법이 아닌 O(logn)의 시간 복잡도를 갖는 자료구조 혹은 탐색 기법을 이용하는 방법으로 문제를 접근해야 한다. 동시에 만들 수 있는 문장의 경우의 수를 고려해줘야 한다. 복합적인 문제라 쉽지 않다. 처음에 각 문자열내 문자들을 파싱해서 map에다가 저장을 해야 하나?…. 그러면 탐색을 어떻게 해야하지?… 하면서 문제 접근을 못하다가 다른 분 풀이를 살짝 참고 했는데 문자열 자체를 map의 key값으로 넣는 것을 보고 힌트를 얻어 문제를 접근할 수 있었다. info 내 문자열을 정재해 띄어쓰기는 문장을 만들어준다. key로 정재된 문장을 value로는 같은 key를 갖는 문장에 대한 값들을 보관하기 위해 List형태로 넣어준다. info 내 문장들이 map으로 다 들어갔으면 Binary Search를 사용하기 위해 오름 차순으로 정렬 해준다. query 내 문자열을 정재해 준다. info에서 구분자는 띄어쓰기 였지만 query에서 구분자는 and와 띄어쓰기다. ‘-‘를 만나게 되면 만들 수 있는 문장의 모든 경우의 수를 만들어준다. 정재된 문자를 갖고 info에 값이 있는지 확인한다. 값이 있으면 List에서 query에서 요구하는 값 이상이 되는 사람 수를 찾는다.(Lower Bound) 쿼리가 여러개인 경우는 각각의 경우들을 모두 찾아서 더해준다. 찾은 결과를 answer에 넣어 반환한다. info 내 문자열을 정재하기public void infoToMap(String[] info) { for (int i = 0; i < info.length; i++) { String[] words = info[i].split(" "); StringBuilder sb = new StringBuilder(); int score = Integer.parseInt(words[words.length - 1]); for (int j = 0; j < words.length - 1; j++) { sb.append(words[j]); } String key = sb.toString(); infos.computeIfAbsent(key, k -> new ArrayList<>()).add(score); }} map 내 List값들을 오름차순으로 정렬하기infos.forEach((key, value) -> { value.sort(null);});

0
Programming프로그래머스

프로그래머스 - 메뉴 리뉴얼 (JAVA)

https://programmers.co.kr/learn/courses/30/lessons/72411 문제 풀이처음에 문자열 비교로 접근해 엄청 해멨다. 이 문제는 문자열 비교로 접근을 하는게 아니라 한 사람이 시킨 메뉴 코스를 이용해 만들 수 있는 경우의 수를 만들어 비교하는 문제다. 코스를 사전 순서로 저장할 수 있도록 주문을 정렬해준다. 한 손님이 주문한 단품 메뉴들로 만들 수 있는 모든 코스 조합을 만들어준다. 코스내 메뉴 개수에 따라 가장 많이 선택된 횟수를 저장해 놓는다. 코스를 선택할때 코스내 메뉴가 메뉴 개수에서 가장 많이 선택된 횟수와 같다면 넣어준다. 모든 코스를 만들어주는 함수public void findAllCourse(String order, String subOrder, int depth) { if (depth == order.length()) { if (subOrder.length() > 1) { if (map.containsKey(subOrder)) { int value = map.get(subOrder); map.put(subOrder, value + 1); } else { map.put(subOrder, 1); } } return; } findAllCourse(order, subOrder + order.charAt(depth), depth + 1); findAllCourse(order, subOrder, depth + 1);} 전체 소스import java.io.*;import java.util.*;class Solution { Map<String, Integer> map = new TreeMap<>(); public void findAllCourse(String order, String subOrder, int depth) { if (depth == order.length()) { if (subOrder.length() > 1) { if (map.containsKey(subOrder)) { int value = map.get(subOrder); map.put(subOrder, value + 1); } else { map.put(subOrder, 1); } } return; } findAllCourse(order, subOrder + order.charAt(depth), depth + 1); findAllCourse(order, subOrder, depth + 1); } public String[] solution(String[] orders, int[] course) { for (String order : orders) { // 문자열내 문자들을 사전 순서대로 정렬 char[] charArr = order.toCharArray(); Arrays.sort(charArr); String sortedOrder = new String(charArr); // 주문한 메뉴들로 만들 수 있는 모든 코스 조합을 만들어준다. findAllCourse(sortedOrder, "", 0); } int[] maxValues = new int[101]; ArrayList<String> result = new ArrayList<>(); map.forEach((key, value) -> maxValues[key.length()] = Math.max(maxValues[key.length()], value)); map.forEach((key, value) -> { if (value >= maxValues[key.length()] && value > 1) { for (int i = 0; i < course.length; i++) { if (course[i] == key.length()) { result.add(key); } } } }); String[] answer = new String[result.size()]; int index = 0; for (String s : result) { answer[index++] = s; } return answer; }}

0
Programming프로그래머스

프로그래머스 - 메뉴 리뉴얼 (Cpp)

https://programmers.co.kr/learn/courses/30/lessons/72411 문제 풀이처음에 문자열 비교로 접근해 엄청 해멨다. 이 문제는 문자열 비교로 접근을 하는게 아니라 한 사람이 시킨 메뉴 코스를 이용해 만들 수 있는 경우의 수를 만들어 비교하는 문제다. 코스를 사전 순서로 저장할 수 있도록 주문을 정렬해준다. 한 손님이 주문한 단품 메뉴들로 만들 수 있는 모든 코스 조합을 만들어준다. 코스내 메뉴 개수에 따라 가장 많이 선택된 횟수를 저장해 놓는다. 코스를 선택할때 코스내 메뉴가 메뉴 개수에서 가장 많이 선택된 횟수와 같다면 넣어준다. 모든 코스 조합을 만들어주는 함수void makeAllCourse(string subOrder, string order, int depth) { if (depth > order.size()) { return; } if (depth == order.size() && subOrder.size() > 1) { if (m.find(subOrder) == m.end()) { m[subOrder] = 1; } else { m[subOrder] += 1; } } // 현재 메뉴를 선택하고 다음 메뉴로 넘어간다. makeAllCourse(subOrder + order[depth], order, depth + 1); // 현재 메뉴를 선택하지 않고 다음 메뉴로 넘어간다. makeAllCourse(subOrder, order, depth + 1);} 전체 소스#include <bits/stdc++.h>using namespace std;map<string, int> m;int maxValues[100];void makeAllCourse(string subOrder, string order, int depth) { if (depth > order.size()) { return; } if (depth == order.size() && subOrder.size() > 1) { if (m.find(subOrder) == m.end()) { m[subOrder] = 1; } else { m[subOrder] += 1; } } makeAllCourse(subOrder + order[depth], order, depth + 1); makeAllCourse(subOrder, order, depth + 1);}vector<string> solution(vector<string> orders, vector<int> course) { vector<string> answer; for (int i = 0; i < orders.size(); i++) { sort(orders[i].begin(), orders[i].end()); makeAllCourse("", orders[i], 0); } for (auto iter = m.begin(); iter != m.end(); iter++) { int courseCount = iter->first.length(); maxValues[courseCount] = max(maxValues[courseCount], iter->second); } for (auto iter = m.begin(); iter != m.end(); iter++) { int courseCount = iter->first.length(); if (iter->second == maxValues[courseCount] && iter->second >= 2) { for (int i = 0; i < course.size(); i++) { if (courseCount == course[i]) { answer.push_back(iter->first); } } } } return answer;}

0
Programming프로그래머스

프로그래머스 - 신규 아이디 추천 (Python)

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/72410 프로그래머스 - 신규 아이디 추천 (Java) 프로그래머스 - 신규 아이디 추천 (Python) def solution(new_id): answer = '' lowerLine = new_id.lower() for i in lowerLine: if i.isalpha() or i.isdigit() or i in ['-', '_', '.']: answer += i while '..' in answer: answer = answer.replace('..', '.') if len(answer) > 1: if answer[0] == '.': answer = answer[1:] elif len(answer) == 1 and answer[0] == '.': answer = '' if len(answer) > 1: if answer[-1] == '.': answer = answer[:-1] elif len(answer) == 1 and answer[-1] == '.': answer = '' if len(answer) == 0: answer += 'a' if len(answer) > 15: answer = answer[:15] if answer[-1] == '.': answer = answer[:-1] while len(answer) <= 2: answer += answer[-1] return answer

0
Programming프로그래머스

프로그래머스 - 표 편집 (Cpp)

https://programmers.co.kr/learn/courses/30/lessons/81303 문제 해설자료구조 Set에 대한 확실한 이해가 있어야 해결할 수 있는 문제,Set의 다양한 함수를 사용할 수 있는 좋은 문제다. 전체 소스 코드#include <bits/stdc++.h>using namespace std;bool check[1000010];set<int> arr;stack<int> deletedData;int executeCmd(int point, string cmd) { char commond = cmd[0]; auto iter = arr.find(point); string str; int value; if (commond == 'U' || commond == 'D') { for (int i = 2; i < cmd.size(); i++) { str += cmd[i]; } value = stoi(str); } if (commond == 'U') { for (int i = 0; i < value; i++) { iter--; } } if (commond == 'D') { for (int i = 0; i < value; i++) { iter++; } } if (commond == 'C') { deletedData.push(*iter); iter = arr.erase(iter); if (iter == arr.end()) { iter--; } } if (commond == 'Z') { if (!deletedData.empty()) { int value = deletedData.top(); deletedData.pop(); arr.insert(value); } } return *iter;}void insertNumber(int n) { for (int i = 0; i < n; i++) { arr.insert(i); }}void scanSet() { for (auto iter = arr.begin(); iter != arr.end(); iter++) { int index = *iter; check[index] = true; }}string solution(int n, int k, vector<string> cmd) { string answer = ""; insertNumber(n); int point = k; for (int i = 0; i < cmd.size(); i++) { point = executeCmd(point, cmd[i]); } scanSet(); for (int i = 0; i < n; i++) { if (check[i]) { answer += 'O'; } else { answer += 'X'; } } return answer;}

0
Programming프로그래머스

프로그래머스 - 수식 최대화 (Cpp)

https://programmers.co.kr/learn/courses/30/lessons/67257 문제 해설경우의 수 문제이다. 모든 경우의 연산자 우선순위를 만들어 해당 연산자 우선순위를 이용해 연산을 진행하면 된다. 중위표기식으로 나타난 식을 후위 표기식으로 바꿔서 문제를 해결 했다. 경우의 수 만들기만들 수 있는 모든 연산자 우선순위를 만들어줘야 한다. DFS를 이용해 모든 경우의 수를 만들어 줬다. void makeAllCase(int depth) { if (depth == 3) { allCase.push_back(cntCase); } for (int i = 0; i < 3; i++) { int cntOper = operation[i]; if (check[i] == false) { check[i] = true; cntCase[depth] = cntOper; makeAllCase(depth + 1); check[i] = false; } }} 연산자 우선순위를 가반으로 한 연산 가장 높은 우선순위의 연산자가 들어왔을 때 Stack을 확인해 같은 먼저 들어온 같은 우선순위의 연산자가 있는지 확인한다. 같은 우선순위의 연산자가 Stack에 있는 경우 pop 해서 해당 연산을 진행한 후 지금 들어온 연산자를 push한다. 없는 경우에는 Stack에 push 한다. 두번째 우선 순위가 연산자가 들어온 경우 Stack을 확인해 우선순위가 같거나 큰 연산자가 없어질 때까지 연산을 진행한 후 pop 한다. Stack에 우선순위가 같거나 큰 연산자가 없을 경우에는 Stack에 push 한다. 세번째 우선 순위의 연산자가 들어온 경우 Stack을 확인해 우선순위가 같거나 큰 연산자가 없어질 때까지 연산을 진행한 후 pop 한다. Stack에 우선순위가 같거나 큰 연산자가 없을 경우에는 Stack에 push 한다.