백준 9012 괄호

# 9012 괄호

N = int(input())
for i in range(N):
    R = list(input())
    if R[0] == ')' or R[-1] == '(':
        print('NO')
    else:
        num = 0
        for j in R:
            if j == '(' and num >= 0:
                num += 1
            else:
                num -= 1
        if num == 0:
            print('YES')
        else:
            print('NO')

먼저 입력으로 받아오는 괄호의 맨 앞과 맨 뒤가 틀리면 바로 'NO'를 반환해준다.

양끝 값이 정상으로 되어있다면 그 안의 괄호 순서의 값을 구해서 답을 출력한다.

num이라는 변수에 0을 할당해 생성해주고

'(' 괄호는 먼저 나와야 하는 괄호이므로 num이 0 이상일 때만 카운트한다.

'(' 괄호가 나오기 전에 ')' 괄호가 나왔다면

num이 마이너스 숫자가 되어서 'NO'를 출력하게 된다.

2022.02.15

백준 1904 타일 01

#1904

N = int(input())
dp = [0]*(N+1)

if N == 1:
    print(1)
elif N == 2:
    print(2)
else:
    dp[1] = 1
    dp[2] = 2
    for i in range(3,N+1):
        dp[i] = (dp[i-2] + dp[i-1])%15746
    print(dp[N])

점화식 자체는 피보나치수열과 같다.

거기에 문제에서 주어진 메모리 초과를 해결해주기 위해서

문제풀이 과정에서 나머지를 구해주면 된다

2022.02.09

#10989 수 정렬하기 3
import sys

N = int(input())
num = [0] * 10001
for i in range(N):
    num[int(sys.stdin.readline())] += 1

for i in range(10001):
    for j in range(num[i]):
        print(i)

주어진 수의 범위가 10,000까지니까 10,001개가 0으로 담긴 리스트를 만든다.

그리고 입력받는 숫자를 인덱스로 삼아서 그 숫자가 등장할 때마다 + 1을 해준다.

다음으로 누적된 숫자만큼 인덱스를 출력해주면 된다.

정렬하기라 간단한 문제인줄 알았는데 메모리 초과를 해결하는데 한참 걸렸다...

그다음은 시간 초과를 해결해야 했네...

2022.02.08 요세푸스 문제

#11866 요세푸스 문제
from collections import deque

N, K = map(int, input().split())
arr = deque()
for i in range(1,N+1):
    arr.append(i)
result = []

for i in range(N):
    for j in range(K-1):
        arr.append(arr.popleft())
    result.append(arr.popleft())

print('<', end = '')
print(*result,sep=', ',end='')
print('>')

수학적으로 풀어 보려다가 큐로 풀면 될 것 같아서 큐로 풀었다.

입력받은 K-1개만큼 리스트의 뒤로 보내주고 K번째 것만 새로운 리스트인 result에 담아준다.

그리고 result를 출력해주면 끝

2022.02.08 나이순 정렬

# 10814 나이순 정렬

N = int(input())
arr = []
for i in range(N):
    a, b = input().split()
    a = int(a)
    arr.append([a,b])
arr.sort(key = lambda x : x[0])

for i in arr:
    print(*i)

정렬해주는데 sort에 key값으로 람다를 써주는 게 키 포인트 같다.

람다를 사용해 arr의 숫자만 정렬해주는 것...

2022.02.08

백준 1874 스택수열

# 1874 스택수열
import sys

n = int(input())
stack = []
result = []
s = 0
for i in range(1,n+1):
    a = int(sys.stdin.readline())
    stack.append(a)
    if s - a < 0:
        for j in range(abs(s-a)):
            result.append('+')
        result.append('-')
        s = a
    else:
        if s - a > 1 and (s - 1) not in stack:
            result.append('NO')
            break
        else:
            result.append('-')
            s = max(a,s)
if 'NO' in result:
    print('NO')
else:
    for i in result:
        print(i)

입력받는 값을 저장하는 stack 리스트와 기호를 저장하는 result 리스트를 생성하고

s의 값을 변경해주면서 그 차이를 통해 result에 기호를 저장해줬다.

성공이라고 돼있어서 아 전에 풀어본 문제구나 하고 봤더니

전혀 기억이 안 나고 마치 새로운 문제를 보는 것 같았다.

어찌어찌 풀기는 했지만 시간 초과가 떠서 pypy3로 채점을 했다.

2022.02.07

백준 2164 카드 2

#2164 카드2

N = int(input())
arr = [i for i in range(1,N+1)]

while len(arr) != 1:
    s = arr[1]
    del arr[0]
    arr.append(s)
    del arr[1]

print(arr[0])

#2164 카드2
from collections import deque

N = int(input())
queue = deque()
for i in range(1,N+1):
    queue.append(i)
    
while len(queue) != 1:
    queue.popleft()
    queue.append(queue.popleft())

print(queue[0])

처음에 위 코드로 풀었다가 시간 초과가 떴다.

시간 복잡도는 while문 처음 시작할 때까지는 같은 거 같은데

무엇에서 차이나는 걸까

2022.02.01

백준 11650 좌표 정렬

#11650 좌표 정렬
import sys
N = int(sys.stdin.readline())
arr = []
for i in range(N):
    arr.append( list(map(int, sys.stdin.readline().split())))
    
arr.sort()
for i in range(N):
    print(*arr[i])

아무래도 주어지는 숫자가 크다 보니 sys를 사용하는 게 시간적 측면에서 유리하다.

2차원 평면에 주어진 좌표를 정렬하는 문제이므로 

2차원 배열을 준비해주고 주어진 N만큼 리스트에 입력받는다.

그리고 sorted를 사용하지않고 sort를 사용해 정렬해 프린트해준다.

#11650 좌표 정렬
import sys
N = int(sys.stdin.readline())
arr = []
for i in range(N):
    arr.append( list(map(int, sys.stdin.readline().split())))
    
for i in sorted(arr):
    print(*i)

글을 작성 중에 sorted가 더 빠를 거 같아서 살짝 고쳐봤더니 

미세하게 더 빠르긴 했다.

이항 계수

# 11050 이항 계수
N, K = map(int, input().split())
n = 1
k = 1
z = N-K

for i in range(1,N+1):
    n = n*i
for i in range(1,K+1):
    k = k*i
for i in range(1,z):
    z = z*i

if K == 0 or N == K:
    print(1)
else:
    print(n//(k*z))

# 10250 ACM 호텔

T = int(input())
for i in range(T):
    H, W, N = map(int, input().split())
    A = N//H
    B = N%H 
    if B == 0:
        if A > 9:
            print(H,A, sep = '')
        else:
            print(H,0,A, sep = '')
    else:
        if A > 8:
            print(B,A + 1 , sep = '')
        else:
            print(B,0,A + 1, sep = '')

1의 자릿수일 경우 0을 넣어주는 것과 1층을 해결해주는 게 좀 포인트였다.