알고리즘 공부

백준 12789번 문제는 큐와 스택 자료구조를 적절히 활용해야 되는 문제이다. 처음에 문제를 이해하는데 시간을 별로 걸리지 않았지만 구현하는데 있어서 고민을 많이 한 문제였다. 쉽게 생각했으면 금방 풀 문제였지만, 너무 어렵게 문제에 접근하여 구현하는데 힘든 문제였다. 문제 입력 & 출력 풀이 먼저 학생 수를 N 값으로 받아주고 순서를 StringTokenizer로 받아준다. 위의 예제를 보면 현재 학생들이 있는 줄은 Queue 자료 구조를 사용하여 맨 앞에 있는 학생부터 나올 수 있게 해주고, 대기 줄은 Stack 자료 구조를 사용한다. 여기서 핵심은 start를 1로 초기화 해주는 부분이다. 먼저 현재 줄을 while문을 통해서 반복해주는데 현재 줄에 남아 있는 학생이 없을때 까지 진행한다. 현재 줄..

백준 28278번 문제는 스택 자료구조를 이용한 문제이다. 문제 입력 & 출력 풀이 해당 문제는 스택 자료구조를 이해하고 있으면 쉽게 풀 수 있는 문제이다. 먼저 스택을 선언해주고 데이터를 저장해서 출력할 수 있는 StringBuilder를 선언해준다. 첫 번째 줄로 들어오는 명령어의 수를 정수로 받아주고, 숫자 1이 들어왔을 경우 그 다음으로 입력되는 값을 받아서 스택에 저장해야되기 때문에 StringTokenizer를 선언하여 데이터를 나눠줄 수 있게 해준다. 먼저 첫 번째 줄로 들어온 명령어의 수 만큼 반복문을 돌려서 명령어들을 한 줄씩 받아온다. 먼저 1번 명령어가 들어오면 다음으로 입력 받는 숫자를 스택에 push() 한다. 2번 명령어가 들어오면 스택이 비어있는지 확인하고 lastElement..

백준 9012번 문제는 스택 자료구조를 묻는 대표적인 괄호 문제이다. 문제 입력과 출력 풀이 먼저 테스트 케이스로 들어오는 정수를 받아주고 해당 값 만큼 반복문을 돌려서 괄호를 받아준다. check() 메서드를 통해 결과값을 StringBuilder에 추가하여 마지막으로 출력해준다. check() 메서드를 통해서 반복문을 돌리는데 먼저 입력으로 받은 test 문자열을 charAt을 활용하여 i 번째 문자를 뽑아준다. 그 후 뽑힌 i 번째 문자가 '(' 면 스택에 push()하고 해당 괄호가 아니면 pop()을 실행한다. 만약 '(' 데이터가 하나 들어오고 그 다음 ')' 데이터가 두 개 들어 온다면 처음 닫는 괄호 데이터가 들어왔을 때 스택을 pop() 해주기 때문에 스택은 비어있는 상태가 되고 다시 '..

백준 4949 문제는 단계별로 풀어보기 카테고리에서 스택, 큐에 있는 문제다. 문제 입력 & 출력 풀이 먼저 입력으로 주어지는 문자열을 받아야 한다. 입력의 조건으로 문장 마지막에는 "." 이 온다는 것을 통해 "."을 기준으로 문장을 구별할 수 있다. 마지막으로 check() 메서드를 통해 입력받은 문장이 "yes" 인지 아니면 "no" 인지 확인하여 StringBuilder에 추가해주고 출력하면 되는 문제이다. check() 메서드를 보면 먼저 문자열로 들어온 test를 charAt을 사용하여 i번째 해당하는 문자를 뽑아주고 해당 문자를 조건문을 통해서 판단한다. 만약 문자로 ')'가 들어 왔는데 스택에 데이터가 없거나 peek() 메서드를 사용했을 때 '('가 아닌 경우는 "no"를 출력해야 한다...

해당 문제는 스택 자료구조에 관한 문제다. 스택 자료구조를 이해하고 있으면 쉽게 풀 수 있는 문제다. 입력되는 숫자를 계속 스택에 삽입하다가 입력된 숫자가 0일 경우 스택에 있는 값을 pop()을 해주고 남아있는 값이 있으면 해당 값을 모두 더해서 출력해주면 된다.

2164번 문제는 Queue 자료구조를 이용한 문제이다. 큐 자료구조를 알고 있다면 쉽게 풀 수 있는 문제이다. 먼저 주어진 숫자 만큼 큐에 삽입을 시켜줘서 하나의 카드 세트를 만든다. while문을 통해 주어진 규칙에 맞게 첫 번째 카드는 뽑아서 버리고 그 다음 카드는 뽑아서 큐에 다시 삽입해준다. 큐에 카드가 한 장 남은 경우 while문을 빠져나오고 마지막 남은 한 장을 poll()를 사용하여 출력해주면 된다.

1748번 문제는 주어진 숫자를 1부터 N까지 나열 했을 때 자릿수가 어떻게 되는지 물어보는 문제다. 해당 문제를 풀면서 문제를 이해하는 것은 빨랐다. 예제를 하나 보면 15가 주어졌을 때 123456789101112131415가 되며 자릿수로 따지면 21이 된다. 이 문제에서 가장 중요한 부분은 그냥 자릿수를 물어본다는 것이다. 나는 그냥 단순하게 String으로 값을 받아 String.length를 출력하게 만들었다. 예제를 입력했을 때 원하는 값이 나왔지만 답을 제출했을 때 메모리 초과가 발생하였다. 여기서 내가 방심한 것은 시간 제한이 0.15초 였던 것과 주어진 데이터 N의 범위가 100,000,000으로 자바 기준으로 시간 복잡도가 O(n)일시 1초가 걸리는 문제였다. 위의 사진과 같이 처음에..