본문 바로가기

Stack13

[엘리스 알고리즘 코드 챌린지 시즌 2] 예선 3일 [Python] 풀이입력받은 문자열 S에 대해 압축을 해제하는 문제다.압축된 문자열은 K(Q)의 형식으로 주어지며 이를 해제할 경우 Q를 K번 반복한다는 의미다.스택과, 재귀 중 스택으로 푸는 방법이 익숙해 스택을 사용해 풀이했다. K(K(Q)K(Q))와 같은 예외를 고려해 문자열의 역순으로 진행했다.정작 제공된 테스트케이스에는 이와 같은 예외가 없었다.우선 ')' 인 경우에는 그냥 stack에 집어넣자.그 다음에는 Q에 해당하는 수들이 들어올 것이다.만약 stack의 마지막 요소가 ')'가 아니라면 Q의 길이를 저장하는 방식이므로 주어진 수( num )를 넣거나 더해주자.탐색을 계속 진행해 '(' 가 나온다면 스택에 넣은 Q의 길이를 뽑아 K와 곱해준 후 다시 스택에 넣어주면 된다.이 과정에서 중복계산과 스택에 남아있.. 2024. 7. 11.
[백준 02800] 괄호 제거 [Python] 문제어떤 수식이 주어졌을 때, 괄호를 제거해서 나올 수 있는 서로 다른 식의 개수를 계산하는 프로그램을 작성하시오.이 수식은 괄호가 올바르게 쳐져 있다. 예를 들면, 1+2, (3+4), (3+4*(5+6))와 같은 식은 괄호가 서로 쌍이 맞으므로 올바른 식이다.하지만, 1+(2*3, ((2+3)*4 와 같은 식은 쌍이 맞지 않는 괄호가 있으므로 올바른 식이 아니다.괄호를 제거할 때는, 항상 쌍이 되는 괄호끼리 제거해야 한다.예를들어 (2+(2*2)+2)에서 괄호를 제거하면, (2+2*2+2), 2+(2*2)+2, 2+2*2+2를 만들 수 있다. 하지만, (2+2*2)+2와 2+(2*2+2)는 만들 수 없다. 그 이유는 쌍이 되지 않는 괄호를 제거했기 때문이다.어떤 식을 여러 쌍의 괄호가 감쌀 수 있다... 2024. 3. 22.
[백준 17952] 과제는 끝나지 않아! [Java] 문제 성애는 이번 학기에 전공을 정말 많이 듣는다. 이로 인해 거의 매일을 과제를 하면서 보내고 있다. 그런데도 과제가 줄어들 기미가 보이지 않는데, 바로 분단위로 과제가 추가되고 있기 때문이다. 다행히 과제 제출 기한은 학기가 끝날 때까지이다. 너무나도 많은 과제를 하다가 미쳐버린 성애는 아래와 같은 규칙으로 과제를 해 나가고 있다. 과제는 가장 최근에 나온 순서대로 한다. 또한 과제를 받으면 바로 시작한다. 과제를 하던 도중 새로운 과제가 나온다면, 하던 과제를 중단하고 새로운 과제를 진행한다. 새로운 과제가 끝났다면, 이전에 하던 과제를 이전에 하던 부분부터 이어서 한다. (성애는 기억력이 좋기 때문에 아무리 긴 시간이 지나도 본인이 하던 부분을 기억할 수 있다.) 성애는 과제를 받자마자 이 과제가.. 2024. 1. 4.
[백준 01662] 압축 [Java] 문제 압축되지 않은 문자열 S가 주어졌을 때, 이 문자열중 어떤 부분 문자열은 K(Q)와 같이 압축 할 수 있다. K는 한자리 정수이고, Q는 0자리 이상의 문자열이다. 이 Q라는 문자열이 K번 반복된다는 뜻이다. 압축된 문자열이 주어졌을 때, 이 문자열을 다시 압축을 푸는 프로그램을 작성하시오. 입력 첫째 줄에 압축된 문자열 S가 들어온다. S의 길이는 최대 50이다. 문자열은 (, ), 0-9사이의 숫자로만 들어온다. 출력 첫째 줄에 압축되지 않은 문자열의 길이를 출력한다. 이 값은 2,147,473,647 보다 작거나 같다. 풀이 문자열 압축 문제이기 때문에, 문제에서 주어진 압축해제 방식으로 가장 안쪽 압축부터 풀어주면 된다. 때문에 가장 안쪽 압축이 나올 때 까지 stack에 push만 해주며 .. 2024. 1. 3.
[백준 04889] 안정적인 문자열 [Java] 문제 여는 괄호와 닫는 괄호만으로 이루어진 문자열이 주어진다. 여기서 안정적인 문자열을 만들기 위한 최소 연산의 수를 구하려고 한다. 안정적인 문자열의 정의란 다음과 같다. 빈 문자열은 안정적이다. S가 안정적이라면, {S}도 안정적인 문자열이다. S와 T가 안정적이라면, ST(두 문자열의 연결)도 안정적이다. {}, {}{}, {{}{}}는 안정적인 문자열이지만, }{, {{}{, {}{는 안정적인 문자열이 아니다. 문자열에 행할 수 있는 연산은 여는 괄호를 닫는 괄호로 바꾸거나, 닫는 괄호를 여는 괄호로 바꾸는 것 2가지이다. 입력 입력은 여러 개의 데이터 세트로 이루어져 있다. 각 데이터 세트는 한 줄로 이루어져 있다. 줄에는 여는 괄호와 닫는 괄호만으로 이루어진 문자열이 주어진다. 문자열의 길이가.. 2024. 1. 2.
[백준 16120] PPAP [Java] 문제 bryan은 PPAP를 좋아한다. bryan은 어떻게 하면 사람들에게 PPAP를 전파할 수 있을까 고민하던 중 PPAP 문자열이라는 것을 고안하게 되었다. PPAP 문자열은 문자열 P에서 시작하여, 문자열 내의 P를 PPAP로 바꾸는 과정을 반복하여 만들 수 있는 문자열로 정의된다. 정확하게는 다음과 같이 정의된다. P는 PPAP 문자열이다. PPAP 문자열에서 P 하나를 PPAP로 바꾼 문자열은 PPAP 문자열이다. 예를 들어 PPAP는 PPAP 문자열이다. 또한, PPAP의 두 번째 P를 PPAP로 바꾼 PPPAPAP 역시 PPAP 문자열이다. 문자열이 주어졌을 때, 이 문자열이 PPAP 문자열인지 아닌지를 알려주는 프로그램을 작성하여라. 입력 첫 번째 줄에 문자열이 주어진다. 문자열은 대문자 .. 2024. 1. 1.

티스토리툴바