[백준] 1874 스택 수열
2023. 1. 12. 19:14
Algorithm Study
문제 설명 https://www.acmicpc.net/problem/1874 1874번: 스택 수열 1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다. www.acmicpc.net 1부터 n까지의 수를 오름차순으로 스택에 넣었다가 뽑아 늘어놓으면서, 주어진 수열과 같게 만들 수 있을지 구하기 문제 풀이법 수를 넣었다 뽑을 stack, 주어진 수열을 담을 vector, 연산 과정을 넣어줄 vector가 필요하다 우선 주어진 수에 맞게 while문을 돌도록 한다. 단, while문을 한..
[백준] 10773 제로
2023. 1. 12. 18:41
Algorithm Study
문제 설명 https://www.acmicpc.net/problem/10773 10773번: 제로 첫 번째 줄에 정수 K가 주어진다. (1 ≤ K ≤ 100,000) 이후 K개의 줄에 정수가 1개씩 주어진다. 정수는 0에서 1,000,000 사이의 값을 가지며, 정수가 "0" 일 경우에는 가장 최근에 쓴 수를 지우고, 아닐 경 www.acmicpc.net 문제 풀이법 일단 k개의 수를 입력 받은 후 stack을 선언하여 입력 받은 수가 0이 아닐때는 stack에 push 해준다 문제에서 입력받은 수가 0일 경우 지울 수가 있음을 보장할 수 있다고 하였으므로, 입력 받은 수가 0이면 pop을 해준다 소스 코드 #include #include using namespace std; int main() { in..
[백준] 10828 스택
2023. 1. 12. 18:24
Algorithm Study
문제 설명 https://www.acmicpc.net/problem/10828 10828번: 스택 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net 정수를 저장하는 스택을 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램 만들기 push X : 정수 X를 스택에 넣기 pop : 스택에서 가장 위에 있는 정수를 뺴고, 그 수를 출력하기. 만약 스택에 들어있는 정수가 없는 경우에는 -1 출력 size : 스택에 들어있는 정수의 개수를 출력 empty : 스택이 비어있으면 1, 아니면 0 출력 top : 스택의 ..
[프로그래머스] 1단계 - 크기가 작은 부분 문자열
2023. 1. 11. 19:43
Algorithm Study
문제 설명 https://school.programmers.co.kr/learn/courses/30/lessons/147355 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 숫자로 이루어진 문자열 t와 p가 주어질 때, t에서 p와 길이가 같은 부분 문자열 중에서, 이 부분 문자열이 나타내는 수가 p가 나타내는 수보다 작거나 같은 것이 나오는 횟수를 구하기 문제 풀이법 처음에는 stoi, stol로만 풀었다가 제출시 code dump가 떠서 하나씩 비교하려고 했다 그렇게 되면 좀 더 복잡해져서 포기하려던 찰나, stoll에 대해서 발견하였다 long는 안..
[프로그래머스] 1단계 - 실패율
2023. 1. 11. 18:32
Algorithm Study
문제 설명 https://school.programmers.co.kr/learn/courses/30/lessons/42889 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 전체 스테이지의 개수 N, 게임을 이용하는 사용자가 현재 멈춰있는 스테이지의 번호가 담긴 배열 stages가 매개 변수로 주어질 때, 실패율이 높은 스테이지부터 내림차순으로 스테이지의 번호가 담겨있는 배열을 return하기 문제 풀이법 단순 구현이기에 문제에서 설명하는대로 잘 구현하면 된다 여기서 몇가지 주의 해야할 점이 있는데 N + 1의 스테이지에 도달한 사람은 N번째 스테이지까지 ..
[프로그래머스] 1단계 - 소수 찾기
2023. 1. 11. 17:06
Algorithm Study
문제 설명 https://school.programmers.co.kr/learn/courses/30/lessons/12921 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr n까지의 소수의 개수 구하기 문제 풀이법 소수를 찾는 문제들은 그냥 for문을 냅다 돌려버리면 찾을 수는 있지만 시간 초과가 나기 때문에 에라토스테네스의 체를 이용하면 시간초과 없이 효율적으로 풀 수 있다 에라토스테네스의 체란? 소수는 1과 자기자신만으로만 나눠지는 수이기 때문에, 어떤 숫자의 배수일 수는 없다 따라서 for문을 돌면서 배수인 수를 제거하면서 소수만 남겨두는 방법이다 우..
[프로그래머스] 1단계 - 폰켓몬
2023. 1. 10. 23:42
Algorithm Study
문제 설명 https://school.programmers.co.kr/learn/courses/30/lessons/1845 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이법 중복되는 수를 피하면 되는터라, 처음에는 정렬을 하고 중복되는 수를 무시하는 방법을 선택하려 했다 하지만 너무 비효율적인것 같았고 찾아보니 set이라는 컨테이너가 있었다 set은 노드 기반 컨테이너이며 균형 이진으로 구현되어있으며, key라 불리는 원소들의 집합으로 이루어진 컨테이너이다 중요한 것은 key값은 중복이 허용되지 않고, 삽입 시 원소는 자동 정렬이다 그러기에 se..
[백준] 1158 요세푸스 문제
2023. 1. 10. 20:29
Algorithm Study
문제 설명 https://www.acmicpc.net/problem/1158 1158번: 요세푸스 문제 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000) www.acmicpc.net 1번부터 n번까지 n명의 사람이 원을 이루며 앉아있을 때, 순서대로 k번째 사람을 제거 원에서 사람들이 제거 되는 순서를 요세푸스 순열이라고 하는데, 이 순열을 구하기 문제 풀이법 queue를 쓰면 금방 풀린다 우선 1번부터 n번까지의 사람을 queue에 넣어놓고, queue가 empty가 되지 않을때까지 while문을 반복한다 while문에서는 k번째의 사람을 구하기 위해서, k -1 번째의 사람은 pop한 뒤, 다시 뒤에 push 한다 k번째 사람은 pop을 한 후, 출력하..
[백준] 5397 키로거
2023. 1. 10. 20:21
Algorithm Study
문제 설명 https://www.acmicpc.net/problem/5397 5397번: 키로거 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 한줄로 이루어져 있고, 강산이가 입력한 순서대로 길이가 L인 문자열이 주어진다. (1 ≤ L ≤ 1,000,000) 강산이가 백스페이스를 입 www.acmicpc.net 비밀번호 창에서 입력한 키가 주어졌을 때, 비밀번호 구하기 이때 알파벳 대문자, 소문자, 숫자, 백스페이스, 화살표만 입력 화살표는 로 입력되며, 커서를 옮기는 역할 백스페이스는 -로 입력되며 커서의 바로 앞에 글자가 존재한다면 그 글자를 지우는 역할 문제 풀이법 백준 1406 에디터와 굉장히 유사한 문제이다 다양한 위치에서의 삽입/삭제를 위해 list를 사용한다 커서의 위치는 ..
[백준] 1406 에디터
2023. 1. 10. 19:52
Algorithm Study
문제 설명 https://www.acmicpc.net/problem/1406 1406번: 에디터 첫째 줄에는 초기에 편집기에 입력되어 있는 문자열이 주어진다. 이 문자열은 길이가 N이고, 영어 소문자로만 이루어져 있으며, 길이는 100,000을 넘지 않는다. 둘째 줄에는 입력할 명령어의 개수 www.acmicpc.net 초기에 편집기에 있는 문자열이 주어지고, 명령어가 주어지면 해당 명령어에 맞게 수행 한 후의 문자열을 구하기 문제 풀이법 처음에는 vector로 풀었다 예제에 있는 답은 맞았지만 5% 즈음부터 시간초과로 실패하고 말았다 vector가 아닌 list로 풀어야 시간초과가 안난다고 한다 그 이유는 vector는 연속적인 배열이기에 중간에 요소가 하나 제거된다면, 당겨야 하는 상황이 발생한다고 ..