1. 문제 풀이 이 문제는 주어진 수열에서 각 원소에 대해 오른쪽에 위치한 값들 중에서 처음으로 등장하는 자신보다 큰 수를 찾는 문제입니다. 만약 끝까지 가도 자신보다 큰 수가 존재하지 않으면 결과는 -1이 됩니다. 최종적으로 모든 원소에 대한 오큰수를 구해 하나의 새로운 수열을 완성해야 합니다. 이를 효율적으로 처리하기 위해 스택을 사용했습니다. 스택에는 아직 오큰수를 찾지 못한 원소들을 값과 인덱스 쌍으로 관리합니다. 수열을 앞에서부터 하나씩 읽어올 때마다 스택의 top에 있는 원소와 비교하여 현재 값이 더 크다면 그 값은 스택 top 원소의 오큰수가 됩니다. 따라서 스택에서 원소를 꺼내 그 인덱스 위치에 현재 값을 기록합니다. 이 과정을 스택 top이 현재 값보다 작지 않을 때까지 반복합니다. 그..
전체 글
1. 문제 풀이 이 문제는 일렬로 세워진 N개의 빌딩에 대해, 각 빌딩 관리인이 오른쪽에 있는 빌딩 중에서 자기보다 낮은 빌딩들만 연속해서 볼 수 있는 개수를 구한 뒤 총합을 계산하는 문제입니다. 자기보다 높거나 같은 빌딩이 등장하면 그 이후는 전혀 보이지 않는다는 것이 핵심 조건입니다. 이 문제를 풀기 위해 스택을 사용했습니다. 스택에는 현재까지 등장한 빌딩들 중 오른쪽을 바라볼 때 아직 시야를 가리지 않는 빌딩들의 높이만을 유지합니다. 각 빌딩의 높이를 입력받을 때마다 스택의 top과 비교하여 입력받은 빌딩의 높이보다 작거나 같은 빌딩들은 이후에 등장하는 빌딩의 옥상을 볼 수 없으므로 모두 제거합니다. 이후 스택에 남아있는 빌딩들은 현재 빌딩을 볼 수 있으니 그 크기를 A에 더합니다. 마지막으로 ..
1. 문제 풀이 pair 를 사용한 스택을 통해 각 탑의 높이와 그 탑의 인덱스를 함께 저장하며 각 탑이 어떤 탑에서 수신 신호를 받을 수 있는지를 계산하는 방식을 사용했습니다. 문제에서 주어지는 탑의 최대 높이보다 더 큰 값인 MX를 선언하여 {MX, 0}을 스택에 넣어 둡니다. 이는 모든 탑이 적어도 하나의 비교 대상을 가지도록 해 스택이 비는 상황을 방지하기 위한 장치입니다. 각 탑의 높이를 입력받을 때마다 현재 탑보다 높이가 낮거나 같은 탑들은 신호를 전달할 수 없으므로 스택에서 제거합니다. 이후 스택의 최상단에 남아 있는 탑이 바로 현재 탑의 신호를 수신할 수 있는 탑이 됩니다. 해당 탑의 인덱스를 출력한 다음, 현재 탑도 이후 탑들의 수신 대상이 될 수 있으므로 스택에 삽입합니다. 이 과정을 ..
1. 문제풀이 엄청 잘 알려진 문제입니다. 저는 연결리스트를 사용해서 풀이했습니다. c++에서 제공하는 list를 사용하였는데 얘는 선형 자료구조이기 때문에 원형 구현을 위해 추가적인 작업이 필요합니다. 2. 코드#include using namespace std;typedef long long ll; typedef unsigned long long ull; typedef pair pi; typedef pair pl;typedef tuple ti; typedef tuple tl; typedef vector vi; typedef vector vl;typedef vector vpi; typedef vector vpl; typedef vector vti; typedef vector vtl;typedef ve..
1. 문제 풀이문자열의 길이가 최대 1,000,000이면서 배열 중간에서의 삭제, 삽입 빈도가 빈번하므로 연결리스트를 사용하여 풀이하는 것이 정해라고 판단했습니다. 문제에서 주어지는 화살표와 백스페이스, 알파벳 대소문자를 연결리스트의 이터레이터를 사용하여 적절하게 구현하면 됩니다.2. 코드#include using namespace std;typedef long long ll; typedef unsigned long long ull; typedef pair pi; typedef pair pl;typedef tuple ti; typedef tuple tl; typedef vector vi; typedef vector vl;typedef vector vpi; typedef vector vpl; typedef..
1. 문제 풀이 방 번호 N을 문자열로 입력받습니다. 0부터 9까지 각 숫자의 빈도수를 저장할 배열 A를 준비하고 문자열을 순회하면서 해당 숫자에 해당하는 배열 인덱스를 증가시킵니다. 단 숫자 '6'은 '9'로 통합하여 A[9]에 저장합니다. 두 숫자를 서로 대체 가능하므로 필요한 세트 수는 A[9] / 2 + (A[9] & 1)로 계산할 수 있습니다. 9를 제외한 나머지 숫자 중 가장 많이 필요한 개수와 비교하여 최대값이 전체 세트의 최소 개수가 됩니다. 2. 코드#include using namespace std;typedef long long ll; typedef unsigned long long ull; typedef pair pi; typedef pair pl;typedef tuple ti; t..
1. 문제 풀이 세 자연수 A, B, C가 주어졌을 때, 이들의 곱을 구한 뒤 그 결과값을 문자열 S로 변환합니다.그 다음 문자열 S를 for문으로 순회하면서 각 자리 숫자가 몇 번 등장하는지를 세어야 합니다.이를 위해 길이가 10인 정수 배열 A[10](또는 vector(10))을 준비하고 각 문자를 숫자로 변환하여 다음과 같이 빈도수를 기록합니다.A[c - '0']++;이 구문은 문자 c가 가리키는 숫자의 인덱스에 해당하는 배열 값을 1 증가시킵니다. 모든 문자를 순회한 후 각 숫자(0 ~ 9)가 등장한 횟수를 출력하면 됩니다. 2. 코드#include using namespace std;typedef long long ll; typedef unsigned long long ull; typedef p..
1. 문제 풀이문제의 유형은 최소 신장 트리입니다. 단순 최소 신장 트리를 구하는 것만 아니라 간선을 삭제한다던가 반복적으로 간선의 총합을 구해야 하는 등 조건들이 붙었지만 성능 개선 없이 문제에서 요구하는 바를 구현할 수 있다면 AC를 받을 수 있습니다. MST를 구하기 위해서 Union-Find를 사용하였습니다. 이 알고리즘을 부르는 이름이 있었는데 몇 달 PS를 관두었더니 이름을 까먹었습니다. 크루스칼이었던거 같은데 맞나요? 2. 코드#include using namespace std;typedef long long ll; typedef unsigned long long ull; typedef pair pi; typedef pair pl;typedef tuple ti; typedef tuple tl..