PS(Problem Solving)/C++

문제 링크 https://www.acmicpc.net/problem/2493 문제 정보 입력 첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 이상 100,000,000 이하의 정수이다. 출력 첫째 줄에 주어진 탑들의 순서대로 각각의 탑들에서 발사한 레이저 신호를 수신한 탑들의 번호를 하나의 빈칸을 사이에 두고 출력한다. 만약 레이저 신호를 수신하는 탑이 존재하지 않으면 0을 출력한다. 풀이 이 문제도 어려운 문제여서 해결하는데 힘들었다. 현재 입력하는 탑의 높이가 기존 스택의 탑의 높이보다 크거나 작을때를 잘 생각해주면 된다. 만약 스택의 top이 현..

문제 링크 https://www.acmicpc.net/problem/1874 문제 정보 입력 첫 줄에 n (1 ≤ n ≤ 100,000)이 주어진다. 둘째 줄부터 n개의 줄에는 수열을 이루는 1이상 n이하의 정수가 하나씩 순서대로 주어진다. 물론 같은 정수가 두 번 나오는 일은 없다. 출력 입력된 수열을 만들기 위해 필요한 연산을 한 줄에 한 개씩 출력한다. push연산은 +로, pop 연산은 -로 표현하도록 한다. 불가능한 경우 NO를 출력한다. 풀이 굉장히 해결하기 어려운 문제였다. 예제 1번을 보고 문제를 이해해보자. 8 4 3 6 8 7 5 2 1 을 입력했다고 하자. 따라서 처음에 4를 수열에 넣어야 한다. 그 과정은 아래와 같다. 1 2 3 4를 스택에 push 한다. 스택에서 4를 pop 해..

문제 링크 https://www.acmicpc.net/problem/10773 문제 정보 입력 첫 번째 줄에 정수 K가 주어진다. (1 ≤ K ≤ 100,000) 이후 K개의 줄에 정수가 1개씩 주어진다. 정수는 0에서 1,000,000 사이의 값을 가지며, 정수가 "0" 일 경우에는 가장 최근에 쓴 수를 지우고, 아닐 경우 해당 수를 쓴다. 정수가 "0"일 경우에 지울 수 있는 수가 있음을 보장할 수 있다. 출력 재민이가 최종적으로 적어 낸 수의 합을 출력한다. 최종적으로 적어낸 수의 합은 231-1보다 작거나 같은 정수이다. 풀이 정수가 0인 경우에 가장 최근에 쓴 수를 지워야 하는 문제다. 스택은 LIFO 구조를 가지고 있으므로 스택을 이용하면 해결 할 수 있다는 것을 알 수 있다. 소스 코드 #i..

문제 링크 https://www.acmicpc.net/problem/10828 문제 정보 입력 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 않은 명령이 주어지는 경우는 없다. 출력 출력해야하는 명령이 주어질 때마다, 한 줄에 하나씩 출력한다. 풀이 STL Stack을 이해하면 쉽게 해결 할 수 있다! 소스 코드 #include using namespace std; int main(void) { ios::sync_with_stdio(0); cin.tie(0); int n; cin >> n; stack S; while (n--) { stri..

문제 링크 https://www.acmicpc.net/problem/1158 문제 정보 입력 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000) 출력 예제와 같이 요세푸스 순열을 출력한다. 풀이 STL List의 erase 함수가 그 다음 원소의 위치를 반환한다는 것을 기억하고 있으면 해결 할 수 있는 문제다! 소스 코드 #include using namespace std; int main(void) { ios::sync_with_stdio(0); cin.tie(0); int n; // 초기 인원수. 1 ~ n명 int k; // 제거할 차례 cin >> n >> k; list L; for (int i = 1; i

문제 링크 https://www.acmicpc.net/problem/5397 문제 정보 입력 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 한줄로 이루어져 있고, 강산이가 입력한 순서대로 길이가 L인 문자열이 주어진다. (1 ≤ L ≤ 1,000,000) 강산이가 백스페이스를 입력했다면, '-'가 주어진다. 이때 커서의 바로 앞에 글자가 존재한다면, 그 글자를 지운다. 화살표의 입력은 ''로 주어진다. 이때는 커서의 위치를 움직일 수 있다면, 왼쪽 또는 오른쪽으로 1만큼 움직인다. 나머지 문자는 비밀번호의 일부이다. 물론, 나중에 백스페이스를 통해서 지울 수는 있다. 만약 커서의 위치가 줄의 마지막이 아니라면, 커서 및 커서 오른쪽에 있는 모든 문자는 오른쪽으로 한 칸 이동한다. 출력 ..

문제 링크 https://www.acmicpc.net/problem/1406 문제 정보 입력 첫째 줄에는 초기에 편집기에 입력되어 있는 문자열이 주어진다. 이 문자열은 길이가 N이고, 영어 소문자로만 이루어져 있으며, 길이는 100,000을 넘지 않는다. 둘째 줄에는 입력할 명령어의 개수를 나타내는 정수 M(1 ≤ M ≤ 500,000)이 주어진다. 셋째 줄부터 M개의 줄에 걸쳐 입력할 명령어가 순서대로 주어진다. 명령어는 위의 네 가지 중 하나의 형태로만 주어진다. 출력 첫째 줄에 모든 명령어를 수행하고 난 후 편집기에 입력되어 있는 문자열을 출력한다. 풀이 연결 리스트로 해결 할 수 있는 문제다. 연결 리스트는 커서를 이용하는 문제가 주로 나온다. 따라서 메모장 같은 문제들을 풀이할 때 용이하게 사용..

문제 링크 https://www.acmicpc.net/problem/3273 문제 정보 입력 첫째 줄에 수열의 크기 n이 주어진다. 다음 줄에는 수열에 포함되는 수가 주어진다. 셋째 줄에는 x가 주어진다. (1 ≤ n ≤ 100000, 1 ≤ x ≤ 2000000) 출력 문제의 조건을 만족하는 쌍의 개수를 출력한다. 풀이 굉장히 간단하게 접근했던 문제인데 시간 초과가 나서 풀 수 없었던 문제였다. 아래는 잘못된 소스 코드이다! // 잘못된 소스 코드! /* #include using namespace std; int number[100002]; int main(void) { ios::sync_with_stdio(0); cin.tie(0); int n; cin >> n; for (int i = 0; i <..