문제https://www.acmicpc.net/problem/9935 풀이스택에 저장되어 있는 데이터에 대한 인덱스 접근을 해야 하는 문제이다. 필자는 Stack에 get(인덱스) 연산이 되는 것을 이 문제를 풀면서 알게 되었다. 스택에서 인덱스 접근이 왜 될까? 그 이유는 Stack은 Vector 기반으로 되어 있어 존재한다. 풀이 방식은 간단하다.1. 문자열에 있는 문자를 스택에 넣는다.2. 폭발하는 문자열의 끝 문자와 스택의 peek() 맨 위의 문자가 같으면서, 폭발하는 문자열 길이 이상만큼 스택에 문자가 저장되어 있다면, 시작 인덱스를 구하고, 스택의 문자와 폭발하는 문자열을 비교해 문자열이 폭발할 수 있는지(flag) 기록한다.3. 폭발하는 문자열이면 스택에서 폭발하는 문자열 길이만큼 뺀다. ..
Problem Solving
문제https://www.acmicpc.net/problem/1038 풀이감소하는 수에서 몇번 째인지 구하는 문제이다. 접근 방식은 이러하다.숫자를 1씩 감소하면서 자신의 숫자보다 작은 숫자들을 붙이고 재귀적인 호출을 해서 모든 감소하는 수를 리스트에 담고, N번째를 출력한다. 단, 리스트 크기보다 n + 1보다 작다면 그것은 존재하지 않는 것이다. 9876543210을 생각해보면 int의 범위를 벗어나므로, long으로 해야한다. 필자는 이 문제에 대한 시간복잡도를 생각할때, 10!인 값으로 생각했고, 10!의 개수가 들어있는 리스트를 오름차순 정렬을 해야해서 1억 연산에 간신히 들어오겠네 라는 착각을 했다. 하지만, 리스트에 담기는 숫자들의 개수는 1023개이다. 그 이유는 이러했다. 결국 감소하는 ..
문제https://www.acmicpc.net/problem/1011 풀이시작지점과 도착지점이 도달할때, 반드시 1광년으로 해야한다고 했고, 공간 이동 장치 횟수의 최솟값을 도출해야한다. 거리 - (광년이동)1 - (1)2 - (1 1)3 - (1 1 1)4 - (1 2 1)5 - (1 2 1 1)6 - (1 2 2 1)...9 - (1 2 3 2 1)...12 - (1 2 3 3 2 1)...16 - (1 2 3 4 3 2 1)...20 - (1 2 3 4 4 3 2 1) 그러면 거리에 따른 이제 공간 이동 장치 작동 횟수를 보도록 하겠다. 개수는 작동 횟수에 해당하는 종류의 개수를 뜻한다. 예를 들어, 3 ~ 4에 해당하는 거리(거리 개수)는 3번 작동(작동 횟수)해야하며, 3번 작동해야하는 거리의 ..
