hyeonae

풀이 답답해서 결국 풀이를 찾아봤다. 그냥 가장 작은 숫자부터 지워주면 되는 줄 알았는데, 덱 또는 스택과 그리디 알고리즘을 함께 사용해야 하는 문제였다. 첫번째 숫자부터 차례대로 덱에 넣어주면서 지금 숫자가 덱에 있는 숫자보다 더 큰 지 검사한다. 만약 덱에 있는 숫자보다 더 크다면 덱에 저장된 작은 숫자들을 모두 pop해 지워주고, 지운 개수만큼 K를 하나씩 감소한다. 만약 지운 개수가 적어 K가 남아있다면 (N-K) 개 만큼 덱의 앞에서부터 출력해주면 된다. 코드 #include #include using namespace std; int N, K; string input; deque d; void init() { cin.tie(0); cout.tie(0); ios_base::sync_with_st..

풀이 기술 3가지를 보면 카드 더미의 가장 위와 가장 아래에서 카드를 빼고 있다. 그래서 양 끝에서 push와 pop이 가능한 덱(deq) 자료구조를 사용해 문제를 풀었다. 미리 1, 2, ... , N으로 정렬된 덱을 만들고, 수열 A에서 반복문을 돌며 기술 1, 2, 3을 정반대로 수행하면 된다. 덱을 사용해야 한다는 점만 안다면 어렵지 않은 문제였다. 코드 #include #include #define MAX 1000001 using namespace std; int N; int A[MAX]; deque d, answer; void init() { cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(false); } int main() { int temp1, ..

풀이 주어진 N개의 문장으로 마지막 문장을 만들 수 있는지 출력하면 된다. 단, 조건은 N개의 문장과 같은 순서로 단어가 나열되어야 한다. 첫 번째 단어가 가장 먼저 나타나야 하므로, 자료구조 중에서 선입선출의 특징을 갖고 있는 큐를 사용하였다. 입력 받은 문자열을 ' '을 기준으로 나눠 큐에 저장한 다음, 마지막 문장에서 큐의 순서대로 단어가 나타나는지 확인하면 된다. string 변수를 다루다보니 여러 라이브러리를 사용했는데, 특히 c++에서는 string 변수에 대한 split() 메소드가 없어서 직접 만들어 사용하였다. queue split(string input, char delimiter) { queue answer; stringstream ss(input); string temp; while..

풀이 문제 제목을 '안 쉬운 거'로 바꿔야 한다. 힌트를 보면 이것 역시 스택 문제라는 걸 알 수 있다. 현재 입력된 빌딩 고도보다 더 높은 빌딩들을 스택에서 제거하고 결과값을 하나씩 증가하면 된다. 입력된 빌딩과 같은 고도의 빌딩이 이미 스택에 있다면, 같은 빌딩이라는 뜻이기 때문에 스택에 push할 필요가 없다. 마지막으로 반복문이 끝난 후에 스택에 남아있는 빌딩 개수만큼 결과값을 증가시키도록 한다. 코드 #include #include using namespace std; typedef struct point { int x; int y; }; void init() { cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(false); } int n, x, y, ..

풀이 예제를 보면 알겠지만 N개의 행렬이 주어지고, N개의 행렬곱셈식이 잇달아 주어진다. 각 행렬곱셈식마다 몇번의 연산이 수행되는지 출력하면 되는 문제이다. () 안의 식을 먼저 연산해야 하기 때문에 자료구조 중에서 스택을 사용하였다. 입력으로 '(' 이 들어오면 무시하고, 알파벳만 스택에 push하도록 한다. 그러다 ')'을 만나면 스택에서 두 개의 알파벳을 꺼내 곱하면 된다. 행렬이 이름(A, B, C, ...) , x, y라는 3개의 특징을 갖고 있기 때문에 matrix라는 구조체를 만들어주었고, 알파벳으로 검색하기 쉽도록 map에 저장하였다. 코드 #include #include #include using namespace std; typedef struct matrix { int x; int y..

풀이 욱제부터 시작해 일렬 횡대로 서 있는 전우들에게 차례로 수류탄이 넘어간 다음, 마지막 전우가 수류탄을 무사히 받아야한다. 반복문 안에서 수류탄을 받은 사람의 위치 좌표와 사거리를 더해 다음 사람이 수류탄을 받을 수 있는 사정 거리 안에 있는지 확인하면 된다. 코드 #include #define MAX 30000 using namespace std; void init() { cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0); } int N; int arr[MAX]; int result = 1; int main() { int length; int max_length = 0; cin >> N; for (int i = 0; i > a..