728x90
반응형

괄호 

한국어   
시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB 198277 93323 67093 45.928%

문제

괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 부른다. 한 쌍의 괄호 기호로 된 “( )” 문자열은 기본 VPS 이라고 부른다. 만일 x 가 VPS 라면 이것을 하나의 괄호에 넣은 새로운 문자열 “(x)”도 VPS 가 된다. 그리고 두 VPS x 와 y를 접합(concatenation)시킨 새로운 문자열 xy도 VPS 가 된다. 예를 들어 “(())()”와 “((()))” 는 VPS 이지만 “(()(”, “(())()))” , 그리고 “(()” 는 모두 VPS 가 아닌 문자열이다. 

여러분은 입력으로 주어진 괄호 문자열이 VPS 인지 아닌지를 판단해서 그 결과를 YES 와 NO 로 나타내어야 한다. 

입력

입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 주어진다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 괄호 문자열이 한 줄에 주어진다. 하나의 괄호 문자열의 길이는 2 이상 50 이하이다. 

출력

출력은 표준 출력을 사용한다. 만일 입력 괄호 문자열이 올바른 괄호 문자열(VPS)이면 “YES”, 아니면 “NO”를 한 줄에 하나씩 차례대로 출력해야 한다. 

예제 입력 1 복사

6
(())())
(((()())()
(()())((()))
((()()(()))(((())))()
()()()()(()()())()
(()((())()(

예제 출력 1 복사

NO
NO
YES
NO
YES
NO

 

스택을 활용

'('가 있으면 ')'도 있어야 한다.

만약 '(' 가 입력되면 스택에 그냥 집어 넣는다

')' 가 입력됐을 때

스택이 비어있다면, ( 없이 )가 입력 된거기 때문에 바로 "NO" 출력 후 다음으로

스택이 비어있지 않다면 '(' 일 것이기 때문에 '(' 를 빼 준다.

 

모든 과정이 끝났을 때

스택에 뭔가 남아있다면 '(' 가 남아 있을 것이다.

남아 있다면 "NO" 출력

남아 있지 않다면 (짝이 다 맞다면) "YES" 출력



import sys



n = int(sys.stdin.readline())

for _ in range(n):
    stack = []
    s = input()
    for i in s:
       
        if i=='(':
            stack.append(i)
        else:
            if stack:
                stack.pop()
            else:
                print("NO")
                break
    else:
        if stack:
            print("NO")
        else:
            print("YES")          
반응형
저작자표시

'백준 단계별로 풀어보기 > 스택, 큐 덱 단계' 카테고리의 다른 글

백준 10773 제로 파이썬  (1) 2024.02.18
728x90
반응형

제로 

한국어   

시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 256 MB 88769 60133 49075 68.019%

문제

나코더 기장 재민이는 동아리 회식을 준비하기 위해서 장부를 관리하는 중이다.

재현이는 재민이를 도와서 돈을 관리하는 중인데, 애석하게도 항상 정신없는 재현이는 돈을 실수로 잘못 부르는 사고를 치기 일쑤였다.

재현이는 잘못된 수를 부를 때마다 0을 외쳐서, 가장 최근에 재민이가 쓴 수를 지우게 시킨다.

재민이는 이렇게 모든 수를 받아 적은 후 그 수의 합을 알고 싶어 한다. 재민이를 도와주자!

입력

첫 번째 줄에 정수 K가 주어진다. (1 ≤ K ≤ 100,000)

이후 K개의 줄에 정수가 1개씩 주어진다. 정수는 0에서 1,000,000 사이의 값을 가지며, 정수가 "0" 일 경우에는 가장 최근에 쓴 수를 지우고, 아닐 경우 해당 수를 쓴다.

정수가 "0"일 경우에 지울 수 있는 수가 있음을 보장할 수 있다.

출력

재민이가 최종적으로 적어 낸 수의 합을 출력한다. 최종적으로 적어낸 수의 합은 231-1보다 작거나 같은 정수이다.

예제 입력 1 복사

4
3
0
4
0

예제 출력 1 복사

0


입력을 받는다

0이 아니면 append

0이면 스택에 append 하지 않고 pop

 

stack의 총합만 출력한다

import sys

stack=[]

k = int(sys.stdin.readline())

for _ in range(k):
    n = int(sys.stdin.readline())
    if n == 0:
        stack.pop()
    else:
        stack.append(n)

print(sum(stack))
반응형
저작자표시

'백준 단계별로 풀어보기 > 스택, 큐 덱 단계' 카테고리의 다른 글

백준 9012 괄호 파이썬  (0) 2024.02.18
728x90
반응형

인사성 밝은 곰곰이 

 
시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB 14261 6369 5395 46.787%

문제

 

알고리즘 입문방 오픈 채팅방에서는 새로운 분들이 입장을 할 때마다 곰곰티콘을 사용해 인사를 한다. 이를 본 문자열 킬러 임스는 채팅방의 기록을 수집해 그 중 곰곰티콘이 사용된 횟수를 구해 보기로 했다.

ENTER는 새로운 사람이 채팅방에 입장했음을 나타낸다. 그 외는 채팅을 입력한 유저의 닉네임을 나타낸다. 닉네임은 숫자 또는 영문 대소문자로 구성되어 있다.

새로운 사람이 입장한 이후 처음 채팅을 입력하는 사람은 반드시 곰곰티콘으로 인사를 한다. 그 외의 기록은 곰곰티콘을 쓰지 않은 평범한 채팅 기록이다.

채팅 기록 중 곰곰티콘이 사용된 횟수를 구해보자!

입력

첫 번째 줄에는 채팅방의 기록 수를 나타내는 정수 � 이 주어진다. (1≤�≤100000)

두 번째 줄부터 � 개의 줄에 걸쳐 새로운 사람의 입장을 나타내는 ENTER, 혹은 채팅을 입력한 유저의 닉네임이 문자열로 주어진다. (문자열길이1≤문자열 길이≤20)

첫 번째 주어지는 문자열은 무조건 ENTER이다.

출력

채팅 기록 중 곰곰티콘이 사용된 횟수를 출력하시오.

예제 입력 1 복사

9
ENTER
pjshwa
chansol
chogahui05
lms0806
pichulia
r4pidstart
swoon
tony9402

예제 출력 1 복사

8


정리하자면

'ENTER' 가 입력되고나서 중복되지 않은 닉네임의 개수를 세면 된다.

'ENTER' 가 다시  입력되면 중복리스트를 제거한다.

 

파이썬에서 중복을 제거하는 가장 쉬운 방법이 set 을 사용하는 것이라고 한다.

n= int(input())

cnt = 0
mem = set()
for _ in range(n):
    i = input()
    if i == 'ENTER':
        mem.clear()
    else :
        if i not in mem:
            cnt+=1
        mem.add(i)
print(cnt)

 

입력 받은 n번 동안

i를 입력 받는데,

i 가 'ENTER'면 set을 초기화한다.

i가 닉네임이면 cnt+=1 연산하고, set에 추가한다. 중복은 자동으로 걸러져서 따로 생각할 필요가 없다

 

반응형
저작자표시
728x90
반응형

칸토어 집합 

한국어   
시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB 13045 5981 4882 45.124%

문제

칸토어 집합은 0과 1사이의 실수로 이루어진 집합으로, 구간 [0, 1]에서 시작해서 각 구간을 3등분하여 가운데 구간을 반복적으로 제외하는 방식으로 만든다.

전체 집합이 유한이라고 가정하고, 다음과 같은 과정을 통해서 칸토어 집합의 근사를 만들어보자.

1. -가 3N개 있는 문자열에서 시작한다.

2. 문자열을 3등분 한 뒤, 가운데 문자열을 공백으로 바꾼다. 이렇게 하면, 선(문자열) 2개가 남는다.

3. 이제 각 선(문자열)을 3등분 하고, 가운데 문자열을 공백으로 바꾼다. 이 과정은 모든 선의 길이가 1일때 까지 계속 한다.

예를 들어, N=3인 경우, 길이가 27인 문자열로 시작한다.

---------------------------

여기서 가운데 문자열을 공백으로 바꾼다.

---------         ---------

남은 두 선의 가운데 문자열을 공백으로 바꾼다.

---   ---         ---   ---

한번 더

- -   - -         - -   - -

모든 선의 길이가 1이면 멈춘다. N이 주어졌을 때, 마지막 과정이 끝난 후 결과를 출력하는 프로그램을 작성하시오.

입력

입력을 여러 줄로 이루어져 있다. 각 줄에 N이 주어진다. 파일의 끝에서 입력을 멈춘다. N은 0보다 크거나 같고, 12보다 작거나 같은 정수이다.

출력

입력으로 주어진 N에 대해서, 해당하는 칸토어 집합의 근사를 출력한다.

 

1. 재귀 카테고리이기 때문에 재귀함수로 만들어야 겠다는 생각

2. 3^n 개를 먼저 그리고 나서 지워나가는게 편하겠다고 생각

3. 입력이 끝나면 프로그램이 자동으로 멈춰야하니까 while True : try except 문 써야겠다

 

def space(start, n)

start : 지우기 시작하는 위치

n : 입력받은 N에 대해 3^n을 한 값, 즉 실제 '-'의 개수

 

 n에 따라서 '-' 를 지워나가는 함수

n==3^0 이면 건드릴 거 없음 ('-' 1개 출력)

n == 3^1 부터,

start+n//3 부터 start+(n//3)*2 까지 공백으로 만들어야 함 = 가운데 구멍 뚫기

그리고 start ~ start+n//3 부분과, start +(n//3)*2  ~ 끝 부분에 대해서 같은 과정을 반복해야함

 

def space(start, n):
    if n==1:
        return
    for i in range(start+n//3, start+(n//3)*2):
        result[i] = ' '
    space(start, n//3)
    space(start+n//3*2, n//3)

 


def space(start, n):
    if n==1:
        return
    for i in range(start+n//3, start+(n//3)*2):
        result[i] = ' '
    space(start, n//3)
    space(start+n//3*2, n//3)

import sys

while True:
    try:
        N = int(sys.stdin.readline())
        result=['-']*(3**N)
        space(0, 3**N)
        print(''.join(result))

    except:
        break
반응형
저작자표시

'백준 단계별로 풀어보기 > 재귀' 카테고리의 다른 글

백준 10870 피보나치 수 5  (0) 2022.09.20
백주 10872 팩토리얼  (0) 2022.09.20

+ Recent posts

티스토리툴바