위 링크에서 자료구조 알고리즘 문제를 풀고 풀이를 기록하는 게시글입니다.
12. 자료구조
문제
(❌ 표시는 혼자 못푼 문제)
1. 1620번 나는야 포켓몬 마스터 이다솜 (실버4) 문제링크
2. 2164번 카드2 (실버4) 문제링크
문제 해석
N장의 카드에 1~N 번호가 적혀있음
1번 카드가 젤 위, N번카드가 젤 아래 순서로 놓여있음
카드가 한장 남을 때까지 아래 과정을 반복
1. 제일 위 카드를 바닥에 버림
2. 제일 위 카드를 제일 아래에 있는 카드 밑으로 옮김
N이 주어졌을 때, 제일 마지막에 남게 되는 카드를 구하자.
제한: 2초 128MB
입력
첫째 줄에 정수 N(1 ≤ N ≤ 500,000)이 주어진다.
출력
첫째 줄에 남게 되는 카드의 번호를 출력한다.
코드
큐 문제212ms
from collections import deque
N = int(input())
if N == 1:
print(1)
else:
dp = deque([i for i in range(1,N+1)])
while True:
dp.popleft()
if len(dp) == 1:
print(dp.popleft())
break
b = dp.popleft()
dp.append(b)3. 3986번 좋은 단어 (실버4) 문제링크
문제 해석
보고서에 모든 글자가 A와 B로 바꼈다.
그 보고서에서 좋은 단어나 세보기로함.
단어 위로 아치형 곡선을 그어 같은 글자끼리 쌍을 짓기로 함. A는 A끼리, B는 B끼리
선끼리 교차하지 않으면서 각 글자를 정확히 한 개의 다른 위치에 있는 같은 글자와 짝지을 수 있다면 그 단어는 좋은단어다.
좋은단어개수를 세어보
제한: 1초 256MB
입력
첫째 줄에 단어의 수 N이 주어진다. (1 ≤ N ≤ 100)
다음 N개 줄에는 A와 B로만 이루어진 단어가 한 줄에 하나씩 주어진다. 단어의 길이는 2와 100,000사이이며, 모든 단어 길이의 합은 1,000,000을 넘지 않는다.
출력
첫째 줄에 좋은 단어의 수를 출력한다.
코드
하나씩 문자를 스택에 넣는데 Top에 있는 원소와 같으면 넣지않고 pop한다.
같이 붙어있는것을 없앴을 때 남아있는 것이 없다면 좋은 글자인 것이다.
136ms
N = int(input())
count = 0
for _ in range(N):
s = input()
mylist = []
for i in s:
if len(mylist) == 0:
mylist.append(i)
else:
if mylist[-1] == i:
mylist.pop()
else:
mylist.append(i)
if len(mylist)==0:
count+=1
print(count)4. 9012번 괄호 (실버4) 문제링크
문제 해석
(와 ) 만으로 구성되어있는 문자열이있다.
괄호쌍이 맞는 문자열인지 판단해서 결과를 YES와 NO로 출력
제한: 1초 128MB
입력
입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 주어진다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 괄호 문자열이 한 줄에 주어진다. 하나의 괄호 문자열의 길이는 2 이상 50 이하이다.
출력
출력은 표준 출력을 사용한다. 만일 입력 괄호 문자열이 올바른 괄호 문자열(VPS)이면 “YES”, 아니면 “NO”를 한 줄에 하나씩 차례대로 출력해야 한다.
코드
위 문제와 동일한 스택문제이다.
52ms
N = int(input())
for _ in range(N):
s = input()
check = True
mylist = []
for i in s:
if i == '(':
mylist.append(i)
else:
if len(mylist) == 0:
check = False
break
mylist.pop()
if check and len(mylist) == 0:
print("YES")
else:
print("NO")5. 4949번 균형잡힌 세상 (실버4) 문제링크
문제 해석
문자열 에서 괄호들의 균형이 잘 맞춰져있는지 판단해보자.
괄호종류: [ ] , ( )
제한: 1초 512MB
입력
각 문자열은 마지막 글자를 제외하고 영문 알파벳, 공백, 소괄호("( )"), 대괄호("[ ]")로 이루어져 있으며, 온점(".")으로 끝나고, 길이는 100글자보다 작거나 같다.
입력의 종료조건으로 맨 마지막에 온점 하나(".")가 들어온다.
출력
각 줄마다 해당 문자열이 균형을 이루고 있으면 "yes"를, 아니면 "no"를 출력한다.
코드
위의 문제가 대문자 YES,NO 출력이었어서 계속 대문자출력해서 오류났었다 ㅠ 이문제는 소문자 yes,no출력이다.
그리고 마지막 종료조건으로 . 하나가 들어온다는 점을 유의해야한다!
80ms
import sys
while True:
s = sys.stdin.readline().rstrip()
if s == "." :
break
check = True
myList = []
for i in s:
if i == '(' or i == '[':
myList.append(i)
elif i == ')' or i == ']':
if len(myList) == 0:
check = False
break
if i == ')':
if myList[-1] == '(':
myList.pop()
else:
check = False
break
else:
if myList[-1] == '[':
myList.pop()
else:
check = False
break
if check and len(myList) == 0:
print("yes")
else:
print("no")❌ 6. 9375번 패션왕 신해빈 (실버3) 문제링크
문제 해석
한번 입었던 옷들의 조합을 다시 입지 않는다.
혜빈이는 알몸이 아닌상태로 며칠동안 밖에 돌아다닐 수 있을까? (하나라도입으면 알몸아닌거임)
제한: 1초 128MB
입력
첫째 줄에 테스트 케이스가 주어진다. 테스트 케이스는 최대 100이다.
- 각 테스트 케이스의 첫째 줄에는 해빈이가 가진 의상의 수 n(0 ≤ n ≤ 30)이 주어진다.
- 다음 n개에는 해빈이가 가진 의상의 이름과 의상의 종류가 공백으로 구분되어 주어진다. 같은 종류의 의상은 하나만 입을 수 있다.
모든 문자열은 1이상 20이하의 알파벳 소문자로 이루어져있으며 같은 이름을 가진 의상은 존재하지 않는다.
출력
각 테스트 케이스에 대해 해빈이가 알몸이 아닌 상태로 의상을 입을 수 있는 경우를 출력하시오.
참고링크: https://hongcoding.tistory.com/60
코드
경우의수를 구할줄 알아야하는 문제였다.
(같은 종류의 옷, 안입는 것 중에 하나를 선택 하는 경우) 각 경우를 곱해서 아예안입는경우를 빼준다.
84ms
from collections import Counter
N = int(input())
for _ in range(N):
K = int(input())
arr = []
for _ in range(K):
S = input().split()
arr.append(S[1])
res = 1
count = Counter(arr)
for i in count.items():
res *= (i[1]+1)
print(res-1)
추가문제
'알고리즘 문제풀이' 카테고리의 다른 글
| 분할정복 문제 및 풀이 (Python) (0) | 2023.12.04 |
|---|---|
| 백트래킹 문제 및 풀이 (Python) (0) | 2023.12.04 |
| 문자열 문제 및 풀이 (Python) (0) | 2023.12.04 |
| 이진탐색(Binary Search) 문제 및 풀이 (Python) (0) | 2023.12.04 |
| 구현 문제 및 풀이 (Python) (0) | 2023.12.04 |