Category: Beakjoon

2022
0
ProgrammingBeakjoon

백준 1197 - 최소 스패닝 트리 (Cpp)

링크 https://www.acmicpc.net/problem/1197 전체 소스 코드#include <algorithm>#include <iostream>#include <string>#include <vector>#define endl '\n';using namespace std;int find(int node, vector<int>& v) { if (node == v[node]) { return node; } return v[node] = find(v[node], v);}void merge(int a, int b, vector<int>& v) { if (a != b) { v[a] = b; }}int main(void) { int vertex, edge; int totalWeight = 0; cin >> vertex >> edge; vector<pair<int, pair<int, int>>> edges = vector<pair<int, pair<int, int>>>(vertex + 1); vector<int> v = vector<int>(vertex + 1); for (int i = 0; i < v.size(); i++) { v[i] = i; } for (int i = 0; i < edge; i++) { int from, to, weight; cin >> from >> to >> weight; edges.push_back({weight, {from, to}}); } sort(edges.begin(), edges.end()); for (auto we : edges) { int weight = we.first; pair<int, int> e = we.second; int from = e.first; int to = e.second; int setA = find(from, v); int setB = find(to, v); if (setA != setB) { totalWeight += weight; merge(setA, setB, v); } } cout << totalWeight << endl; return 0;}

0
ProgrammingBeakjoon

백준 15650 - N 과 M (2) - 순열

백준 15650 - N 과 M (2) - 순열 Post not found: algorithm/baekjoon/경우의수/15649-N과M-cpp Post not found: algorithm/baekjoon/경우의수/15650-N과M-cpp 링크https://www.acmicpc.net/problem/2606 문제 풀이 주어진 N 개에서 M 개를 뽑는 경우의 수를 다루는 조합 문제 백트레킹 을 이용해 만들 수 있는 모든 경우의 수를 만들어 줬다. 다만, 조합은 순서와 상관 없이 뽑은 상태가 같으면 같은 Case 로 분류가 된다. 때문에 현재 뽑은 위치(idx) 에서 앞에 있는 것들만 뽑게 하면 같은 경우의 수가 나오는 것을 방지할 수 있다. 전체 소스 코드#include <iostream>#include <vector>#define endl '\n'using namespace std;vector<int> v;vector<bool> check;// idx : 수열 탐색 현재 시작 위치를 알려주기 위한 변수// depth : 재귀 문이 몇번 호출 됐는지 확인하기 위한 변수// n : 수열 탐색의 마지막 위치를 확인하기 위한 값// m : 재귀 문을 최대 호출할 수 있는 횟수void nCr(int idx, int depth, int n, int m) { if (depth == m) { for (int value : v) { cout << value << " "; } cout << endl; return; } for (int i = idx; i < n; i++) { if (check[i] == true) { continue; } check[i] = true; v[depth] = i + 1; nCr(i + 1, depth + 1, n, m); check[i] = false; }}int main(void) { cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(false); int n, m; cin >> n >> m; v = vector<int>(m); check = vector<bool>(n); nCr(0, 0, n, m); return 0;}

0
ProgrammingBeakjoon

백준 15649 - N 과 M (1) - 순열

백준 15649 - N 과 M (1) Post not found: algorithm/baekjoon/경우의수/15649-N과M-cpp Post not found: algorithm/baekjoon/경우의수/15650-N과M-cpp 링크https://www.acmicpc.net/problem/2606 문제 풀이 주어진 N 개에서 M 개를 뽑아 나열하는 순열 문제. 백트래킹 을 이용해 만들 수 있는 모든 수열의 경우의 수 를 만들어 준다. check 를 이용해 똑같은 숫자를 여러 번 뽑는 중복 행위를 판단하고 v 배열을 통해 한 수열이 만들어지면 출력하도록 한다. v : 뽑은 숫자를 저장하기 위한 배열 check : 해당 숫자가 뽑혔는지 판단하기 위한 배열 전체 소스 코드

0
ProgrammingBeakjoon

백준 1012 - 유기농 배추 (Python)

백준 1012 - 유기농 배추 (Python)링크https://www.acmicpc.net/problem/2606 전체 소스 코드def bfs(y, x): q = [] q.append([y, x]) check[y][x] = True while q: cntY, cntX = q.pop() for i in range(4): ny = cntY + dy[i] nx = cntX + dx[i] if 0 > ny or ny >= col or 0 > nx or nx >= row: continue if check[ny][nx] == False and field[ny][nx] == 1: q.append([ny, nx]) check[ny][nx] = Truetest_case = int(input())row = 0col = 0k = 0field = []check = []dy = [1, -1, 0, 0]dx = [0, 0, 1, -1]for t in range(test_case): row, col, k = map(int, input().split()) field = [[0] * row for _ in range(col)] check = [[False] * row for _ in range(col)] count = 0 for i in range(k): x, y = map(int, input().split()) field[y][x] = 1 for i in range(col): for j in range(row): if check[i][j] == False and field[i][j] == 1: count += 1 bfs(i, j) print(count)

0
ProgrammingBeakjoon

백준 2606 - 바이러스 (Python)

백준 2606 - 바이러스 (Python)링크https://www.acmicpc.net/problem/2606 전체 소스 코드def bfs(start_node): q = [] q.append(start_node) check[start_node] = True count = 0 while q: node = q.pop(0) for i in range(1, node_num+1): if check[i] == False and field[node][i] == 1: q.append(i) count += 1 check[i] = True return countnode_num = int(input())line_num = int(input())field = [[0]*(node_num+1)for i in range(node_num+1)]check = [False]*(node_num+1)for i in range(line_num): a, b = map(int, input().split()) field[a][b] = 1 field[b][a] = 1print(bfs(1))

0
ProgrammingBeakjoon

백준 2606 - 단지번호 붙이기 (Python)

백준 2667 - 단지번호 붙이기 (Python)링크https://www.acmicpc.net/problem/2667 전체 소스 코드def bfs(y, x): q = [] q.append([y, x]) check[y][x] = True count = 0 while len(q) > 0: count += 1 cntY = q[0][0] cntX = q[0][1] q.pop(0) for i in range(4): ny = cntY + dy[i] nx = cntX + dx[i] if 0 > ny or ny >= n or 0 > nx or nx >= n: continue if check[ny][nx] == False and field[ny][nx] != 0: check[ny][nx] = True q.append([ny, nx]) values.append(count)dy = [1, -1, 0, 0]dx = [0, 0, 1, -1]n = int(input())color = 0values = []check = [[False] * n for i in range(n)]field = [[0] * n for i in range(n)]for i in range(n): line = input() for j in range(len(line)): field[i][j] = int(line[j])for i in range(n): for j in range(n): if check[i][j] == False and field[i][j] != 0: color += 1 bfs(i, j)values.sort()print(color)for i in values: print(i)

0
ProgrammingBeakjoon

백준 13460 - 구슬 탈출 2

https://www.acmicpc.net/problem/13460 백준 13460 - 구슬 탈출 2 백준 13460 - 구슬 탈출 2문제스타트링크에서 판매하는 어린이용 장난감 중에서 가장 인기가 많은 제품은 구슬 탈출이다. 구슬 탈출은 직사각형 보드에 빨간 구슬과 파란 구슬을 하나씩 넣은 다음, 빨간 구슬을 구멍을 통해 빼내는 게임이다. 보드의 세로 크기는 N, 가로 크기는 M이고, 편의상 1×1크기의 칸으로 나누어져 있다. 가장 바깥 행과 열은 모두 막혀져 있고, 보드에는 구멍이 하나 있다. 빨간 구슬과 파란 구슬의 크기는 보드에서 1×1크기의 칸을 가득 채우는 사이즈이고, 각각 하나씩 들어가 있다. 게임의 목표는 빨간 구슬을 구멍을 통해서 빼내는 것이다. 이때, 파란 구슬이 구멍에 들어가면 안 된다. 이때, 구슬을 손으로 건드릴 수는 없고, 중력을 이용해서 이리 저리 굴려야 한다. 왼쪽으로 기울이기, 오른쪽으로 기울이기, 위쪽으로 기울이기, 아래쪽으로 기울이기와 같은 네 가지 동작이 가능하다. 각각의 동작에서 공은 동시에 움직인다. 빨간 구슬이 구멍에 빠지면 성공이지만, 파란 구슬이 구멍에 빠지면 실패이다. 빨간 구슬과 파란 구슬이 동시에 구멍에 빠져도 실패이다. 빨간 구슬과 파란 구슬은 동시에 같은 칸에 있을 수 없다. 또, 빨간 구슬과 파란 구슬의 크기는 한 칸을 모두 차지한다. 기울이는 동작을 그만하는 것은 더 이상 구슬이 움직이지 않을 때 까지이다. 보드의 상태가 주어졌을 때, 최소 몇 번 만에 빨간 구슬을 구멍을 통해 빼낼 수 있는지 구하는 프로그램을 작성하시오.

2021
0
ProgrammingBeakjoon

백준 14592 - 연구소

백준 14592 - 연구소https://www.acmicpc.net/problem/14592 문제풀이해당 문제에서는 3가지 입력 N, M, 지도 모양이 주어진다. N : 세로 크기 M : 가로 크기 지도 정보 지도 내 상태는 3가지 상태가 존재한다. 0 : 빈칸 1 : 벽 2 : 바이러스 알고리즘 실행계획은 다음과 같이 진행한다. 벽을 세운다. 바이러스 확산 시킨다. 바이러스 영역을 확인한다.

0
ProgrammingBeakjoon

백준 1158 - 요세푸스 문제

백준 1158 - 요세푸스 문제https://www.acmicpc.net/problem/1158 문제 풀이해당 문제에서는 두가지 입력 N, K가 주어진다. N : 사람 수 K : 원에서 사람이 제거되는 간격 N, K의 최대 5000 이므로, 최대 O(N^2)의 시간복잡도내에서 문제를 해결해야 한다. 전체 소스 코드import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String[] arguments = br.readLine().split(" "); int N, K; N = Integer.parseInt(arguments[0]); K = Integer.parseInt(arguments[1]); List<Integer> list = new ArrayList<>(); for (int i = 0; i < N; i++) { list.add(i + 1); } int index = 0; StringBuilder sb = new StringBuilder(); sb.append("<"); // 사람을 간격에 맞게 하나씩 제거해준다. while (list.size() > 1) { index += K - 1; index %= list.size(); int removedValue = list.remove(index); sb.append(Integer.toString(removedValue)); sb.append(", "); } // 마지막 숫자를 제거한다. index += K - 1; index %= list.size(); int removedValue = list.remove(index); sb.append(Integer.toString(removedValue)); sb.append(">"); System.out.println(sb.toString()); br.close(); }}

0
ProgrammingBeakjoon

백준 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
ProgrammingBeakjoon

백준 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
ProgrammingBeakjoon

백준 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
ProgrammingBeakjoon

백준 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
ProgrammingBeakjoon

백준 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
ProgrammingBeakjoon

백준 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;}