Category: Develop

0

프로그래머스 - 순위 검색 (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

프로그래머스 - 메뉴 리뉴얼 (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

프로그래머스 - 메뉴 리뉴얼 (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

백준 2178 - 미로탐색

링크https://www.acmicpc.net/problem/2178 문제 풀이기본적인 BFS 문제다. 조건에 맞춰 값을 읽어온 후 탐색을 진행하면 원하는 값을 얻을 수 있다. 전체 소스import java.io.BufferedReader;import java.io.IOError;import java.io.IOException;import java.io.InputStreamReader;import java.util.LinkedList;import java.util.Queue;public class Main { public static int height, width; public static int[] dx = { 0, 0, 1, -1 }; public static int[] dy = { 1, -1, 0, 0 }; public static int[][] map; public static int bfs() { Queue<int[]> q = new LinkedList<>(); boolean check[][] = new boolean[height + 1][width + 1]; q.offer(new int[] { 0, 0 }); check[0][0] = true; int count = 0; while (!q.isEmpty()) { int qSize = q.size(); count++; while (qSize-- > 0) { int[] point = q.remove(); int cntY = point[0]; int cntX = point[1]; if (cntY == height - 1 && cntX == width - 1) { return count; } for (int i = 0; i < 4; i++) { int nY = cntY + dy[i]; int nX = cntX + dx[i]; if (0 <= nY && nY < height && 0 <= nX && nX < width) { if (check[nY][nX] == false && map[nY][nX] == 1) { check[nY][nX] = true; q.offer(new int[] { nY, nX }); } } } } } return count; } public static void main(String args[]) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String[] inputValues = br.readLine().split(" "); height = Integer.parseInt(inputValues[0]); width = Integer.parseInt(inputValues[1]); map = new int[height + 1][width + 1]; for (int h = 0; h < height; h++) { String inputValue = br.readLine(); for (int w = 0; w < width; w++) { // System.out.println(inputValue.charAt(w)); map[h][w] = inputValue.charAt(w) - '0'; } } int count = bfs(); System.out.println(count); br.close(); }}

0

프로그래머스 - 신규 아이디 추천 (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

프로그래머스 - 표 편집 (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

카프카 사용하기

카프카 명령어주키퍼 실행 ./bin/zookeeper-server-start.sh config/zookeeper.properties 카프카 실행 ./bin/kafka-server-start.sh config/server.properties 카프카 토픽관리토픽을 새로 생성하고 싶으면 kafka-topics 명령어에 --create 옵셩을 통해 새로운 토픽을 생성할 수 있습니다. ./bin/kafka-topics.sh \ --create \ --topic quickstart-events \ --bootstrap-server localhost:9092 카프카에 저장된 모든 토픽 정보를 보고 싶을 경우 --list 옵셩을 통해 확인할 수 있습니다.

0

백준 3015 - 단어 정렬

https://www.acmicpc.net/problem/1181 백준 3015 단어 정렬문제 풀이자료구조 Set을 사용하기 좋은 문제이다. 다만 Set에서 사용하는 정렬방식을 조건에 맞게 변형해줄 필요가 있다. 소스코드#include <bits/stdc++.h>using namespace std;set<pair<int, string>> s;int n;int main(void) { cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(false); cin >> n; while (n--) { string word; cin >> word; s.insert({word.length(), word}); } for (auto iter = s.begin(); iter != s.end(); iter++) { cout << iter->second << '\n'; } return 0;} 자바 소스 코드Comparator 인터페이스를 이용해 set의 정렬기준을 사용자가 정의한 정렬기준으로 변경할 수 있다. Comparator 인터페이스를 사용하게 되면 compare 메소드를 오버라이딩해 원하는 정렬 기준을 적용할 수 있다. import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.Comparator;import java.util.Set;import java.util.TreeSet;public class Main { public static void main(String args[]) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int count = Integer.parseInt(br.readLine()); Set<String> words = new TreeSet<String>(new Comparator<String>() { @Override public int compare(String o1, String o2) { if (o1.length() < o2.length()) { return -1; } else if (o1.length() > o2.length()) { return 1; } else { return o1.compareTo(o2); } } }); for (int countIdx = 0; countIdx < count; countIdx++) { String word = br.readLine(); words.add(word); } words.stream().forEach(x -> System.out.println(x)); }}

0

백준 12100 - 2048

https://www.acmicpc.net/problem/12100 백준 12100 - 2048문제 풀이보드를 상하좌우로 움직이면서 블록이 최대값이 나올 수 있는 경우를 찾는 문제이다. 한 보드를 상하좌우로 움직이고 원래데로 되돌린 후 다시 시도하기 위해 백트레킹 기법이 필요하다. 블록을 상하좌우중 한 방향으로 움직인다. 5번 움직이면 블록을 스캔해 최대값을 찾는다. 이전 단계로 되돌린 후 다른방향으로 움직이면서 최대값을 찾아본다. 문제 예외 처리 한번 합처진 블록은 연속적으로 합처질 수 없다. 합처지는 순서는 이동하려고 하는 쪽의 칸이 먼저 합쳐진다. 소스 코드#include <bits/stdc++.h>using namespace std;int maxValue = 0;int board[22][22];int boardSize = 0;void initBoard(int size) { for (int i = 0; i < size; i++) { for (int j = 0; j < size; j++) { cin >> board[i][j]; } }}void moveTop() { int check[22][22]; for (int col = 0; col < boardSize; col++) { for (int row = 0; row < boardSize; row++) { check[col][row] = false; } } for (int row = 0; row < boardSize; row++) { for (int col = 0; col < boardSize; col++) { int cntRow = row; int cntCol = col; if (board[cntRow][cntCol] == 0) { continue; } while (cntRow - 1 >= 0 && (board[cntRow - 1][cntCol] == board[cntRow][cntCol] || board[cntRow - 1][cntCol] == 0)) { if (board[cntRow - 1][cntCol] == board[cntRow][cntCol]) { if (check[cntRow - 1][cntCol] == false && check[cntRow][cntCol] == false) { board[cntRow - 1][cntCol] += board[cntRow][cntCol]; check[cntRow - 1][cntCol] = true; board[cntRow][cntCol] = 0; } else { break; } } else { swap(board[cntRow - 1][cntCol], board[cntRow][cntCol]); } cntRow--; } } }}void moveButton() { int check[22][22]; for (int col = 0; col < boardSize; col++) { for (int row = 0; row < boardSize; row++) { check[col][row] = false; } } for (int row = boardSize - 1; row >= 0; row--) { for (int col = 0; col < boardSize; col++) { int cntCol = col; int cntRow = row; if (board[cntRow][cntCol] == 0) { continue; } while (cntRow + 1 < boardSize && (board[cntRow + 1][cntCol] == board[cntRow][cntCol] || board[cntRow + 1][cntCol] == 0)) { if (board[cntRow + 1][cntCol] == board[cntRow][cntCol]) { if (check[cntRow + 1][cntCol] == false && check[cntRow][cntCol] == false) { board[cntRow + 1][cntCol] += board[cntRow][cntCol]; check[cntRow + 1][cntCol] = true; board[cntRow][cntCol] = 0; } else { break; } } else { swap(board[cntRow + 1][cntCol], board[cntRow][cntCol]); } cntRow++; } } }}void moveLeft() { int check[22][22]; for (int col = 0; col < boardSize; col++) { for (int row = 0; row < boardSize; row++) { check[col][row] = false; } } for (int col = 0; col < boardSize; col++) { for (int row = 0; row < boardSize; row++) { int cntCol = col; int cntRow = row; if (board[cntRow][cntCol] == 0) { continue; } while (cntCol - 1 >= 0 && (board[cntRow][cntCol - 1] == board[cntRow][cntCol] || board[cntRow][cntCol - 1] == 0)) { if (board[cntRow][cntCol - 1] == board[cntRow][cntCol]) { if (check[cntRow][cntCol - 1] == false && check[cntRow][cntCol] == false) { board[cntRow][cntCol - 1] += board[cntRow][cntCol]; check[cntRow][cntCol - 1] = true; board[cntRow][cntCol] = 0; } else { break; } } else { swap(board[cntRow][cntCol - 1], board[cntRow][cntCol]); } cntCol--; } } }}void moveRight() { int check[22][22]; for (int col = 0; col < boardSize; col++) { for (int row = 0; row < boardSize; row++) { check[col][row] = false; } } for (int col = boardSize - 1; col >= 0; col--) { for (int row = 0; row < boardSize; row++) { int cntRow = row; int cntCol = col; if (board[cntRow][cntCol] == 0) { continue; } while (cntCol + 1 < boardSize && (board[cntRow][cntCol + 1] == board[cntRow][cntCol] || board[cntRow][cntCol + 1] == 0)) { if (board[cntRow][cntCol + 1] == board[cntRow][cntCol]) { if (check[cntRow][cntCol + 1] == false && check[cntRow][cntCol] == false) { board[cntRow][cntCol + 1] += board[cntRow][cntCol]; check[cntRow][cntCol + 1] = true; board[cntRow][cntCol] = 0; } else { break; } } else { swap(board[cntRow][cntCol], board[cntRow][cntCol + 1]); } cntCol++; } } }}void returnBoard(int (*board)[22], int (*copy)[22]) { for (int i = 0; i < boardSize; i++) { for (int j = 0; j < boardSize; j++) { board[i][j] = copy[i][j]; } }}void moveBoard(int depth) { int copyBoard[22][22]; for (int i = 0; i < boardSize; i++) { for (int j = 0; j < boardSize; j++) { copyBoard[i][j] = board[i][j]; } } if (depth == 5) { for (int i = 0; i < boardSize; i++) { for (int j = 0; j < boardSize; j++) { if (board[i][j] > maxValue) { maxValue = board[i][j]; } } } return; } moveTop(); moveBoard(depth + 1); returnBoard(board, copyBoard); moveButton(); moveBoard(depth + 1); returnBoard(board, copyBoard); moveLeft(); moveBoard(depth + 1); returnBoard(board, copyBoard); moveRight(); moveBoard(depth + 1); returnBoard(board, copyBoard);}int main(void) { cin >> boardSize; initBoard(boardSize); moveBoard(0); cout << maxValue << '\n'; return 0;}

0

백준 2343 - 기타 레슨

백준 2343 - 기타 레슨https://www.acmicpc.net/problem/2343 문제 풀이탐색 범위는 (1~10억)이고 연산을 N번 해야 함으로 O(N) or O(NlogN)의 시간복잡도 내에 문제를 해결해야 한다. 탐색 시간을 줄이기 위해서 O(logN)시간 복잡도 내에 탐색을 끝낼 수 있는 이분탐색을 이용해 문제를 해결해야 한다. 이 문제의 함정은 조건 중 순서가 뒤바뀌면 안된다는 조껀이 있기 때문에 레슨이 들어온 순서를 sorting할 경우 틀리게 된다. begin을 1로 end를 들어온 값의 합을 준다. begin과 end 범위 내에서 이분 탐색을 진행한다. 이분탐색을 진행하면서 블루레이를 녹화할 수 있는 영상의 길이가 한 영상의 길이보다 작으면 begin을 움직인다. 블루레이에 녹화하는 갯수가 블루레이보다 총 갯수보다 작거나 같을 경우 end를 움직인다. 블루레이에 녹화하는 갯수가 블루레이보다 작을 경우 begin을 움직인다. 전체 소스#include <bits/stdc++.h>using namespace std;bool cmp(vector<int> arr, int mid, int M) { int sum = 0; int count = 1; for (int arrIndex = 0; arrIndex < arr.size(); arrIndex++) { int value = arr[arrIndex]; if (value > mid) { return true; } if (sum + value <= mid) { sum += value; } else { count += 1; sum = value; } } // 길이가 너무 짧다. begin을 늘려줘야 한다. return count > M;}int binarySearch(vector<int> arr, int N, int M) { int begin = 1; int end = 0; for (int arrIndex = 0; arrIndex < arr.size(); arrIndex++) { end += arr[arrIndex]; } while (begin <= end) { int mid = (begin + end) / 2; if (cmp(arr, mid, M)) { begin = mid + 1; } else { end = mid - 1; } } return begin;}int solution(vector<int> arr, int N, int M) { int result = 0; result = binarySearch(arr, N, M); return result;}int main(void) { int N, M; vector<int> arr; cin >> N >> M; arr = vector<int>(N); for (int i = 0; i < N; i++) { cin >> arr[i]; } cout << solution(arr, N, M) << '\n'; return 0;}

0

백준 1920 - 수 찾기

백준 1920 - 수 찾기문제 풀이범위 1~10만개의 숫자들 중에서 M개의 주어진 값이 존재하는지 확인하는 문제이다. 일반적인 탐색을 진행할 경우 O(N*N)의 시간복잡도를 갖게 되므로 O(logN)의 시간복잡도를 갖는 이분 탐색을 이용해 문제를 해결하도록 한다. 전체 소스#include <bits/stdc++.h>using namespace std;int binarySearch(vector<int>& arr, int value) { int begin = 0; int end = arr.size() - 1; while (begin <= end) { int mid = (begin + end) / 2; int midValue = arr[mid]; if (value == midValue) { return 1; } else if (value > midValue) { begin = mid + 1; } else { end = mid - 1; } } return 0;}vector<int> solution(vector<int> arr, vector<int> values) { vector<int> results; for (int valuesIndex = 0; valuesIndex < values.size(); valuesIndex++) { int result = binarySearch(arr, values[valuesIndex]); results.push_back(result); } return results;}int main(void) { int n, m; vector<int> arr; vector<int> values; cin >> n; arr = vector<int>(n); for (int i = 0; i < n; i++) { cin >> arr[i]; } sort(arr.begin(), arr.end()); cin >> m; values = vector<int>(m); for (int i = 0; i < m; i++) { cin >> values[i]; } vector<int> results = solution(arr, values); for (int value : results) { cout << value << '\n'; } return 0;}

0

백준 3015 - 오아시스 재결합

백준 3015 - 오아시스 재결합https://www.acmicpc.net/problem/1920 문제 해설입력되는 값이 총 50만개이다. 이 문제는 O(N) or O(NlogN)의 시간복잡도를 갖고 해결을 해야하는 문제이다. 현재 값을 이전 값과 비교해가면서 문제를 해결 하는 방식이다. 스택의 역할은 서로불 수 있는 값의 쌍을 저장하기 위한 역할을 한다. 스택내의 값은 점점 작은 값이 추가 되야 한다. 들어오는 값이 top보다 클 경우 들어오는 값보다 큰 값이 나타날 때까지 pop을 진행하면서 pop을 진행할 때 해당 인원수 만큼 값을 더해준다. 같은 값이 들어올 경우을 어떻게 해결하는 것이 이 문제의 어려운 점이다. 자료구조 pair를 이용한다. first에는 사람의 키를 second에는 같은 키인 사람의 수를 저장한다. 키가 같은 사람이 들어올 경우 같은 키를 갖는 사람만큼 값을 추가해주고 사람수를 + 1 해주고 해당 키를 다시 push해준다. 소스 코드#include <bits/stdc++.h>using namespace std;long long solution(vector<int> heights) { stack<pair<int, int>> st; long long result = 0; for (int heightsIndex = 0; heightsIndex < heights.size(); heightsIndex++) { int height = heights[heightsIndex]; while (!st.empty() && height > st.top().first) { result += st.top().second; st.pop(); } if (!st.empty()) { if (st.top().first == height) { pair<int, int> temp = st.top(); st.pop(); result += temp.second; if (!st.empty()) { result += 1; } st.push({height, temp.second + 1}); } else { result += 1; st.push({height, 1}); } } else { st.push({height, 1}); } } return result;}int main(void) { int numOfPeople; vector<int> heights; cin >> numOfPeople; for (int peopleIndex = 0; peopleIndex < numOfPeople; peopleIndex++) { int height; cin >> height; heights.push_back(height); } cout << solution(heights) << '\n'; return 0;}

0

백준 - 수학

백준 - 수학수학 문제 이름 링크 정리여부 비고 1085 직사각형에서 탈출 https://www.acmicpc.net/problem/1085 1644 소수의 연속합 https://www.acmicpc.net/problem/1644 1712 손익분기점 https://www.acmicpc.net/problem/1712 1722 순열의 순서 https://www.acmicpc.net/problem/1722 1978 알파벳 https://www.acmicpc.net/problem/1978 1990 소수인팬린드롬 https://www.acmicpc.net/problem/1990 2292 벌집 https://www.acmicpc.net/problem/2292 2839 설탈배달 https://www.acmicpc.net/problem/2839 2960 에라토스테네스의 체 https://www.acmicpc.net/problem/2960 10819 차이를 최대로 https://www.acmicpc.net/problem/10819 순열, next_permutation 10950 A+B - 3 https://www.acmicpc.net/problem/10950 10952 A+B - 5 https://www.acmicpc.net/problem/10952 11021 A+B - 7 https://www.acmicpc.net/problem/11021 11022 A+B - 8 https://www.acmicpc.net/problem/11022