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))

2022.01.27

백준 10845 큐

# 10845 큐
import collections 
import sys

N = int(sys.stdin.readline())
queue = collections.deque()

for i in range(N):
    q = sys.stdin.readline().split()
    if q[0] == 'push':
        queue.append(int(q[1]))
    elif q[0] == 'pop':
        try:
            print(queue.popleft())
        except:
            print(-1)
    elif q[0] == 'size':
        print(len(queue))
    elif q[0] == 'empty':
        if queue:
            print(0)
        else:
            print(1)
    elif q[0] == 'front':
        if not queue:
            print(-1)
        else:
            print(queue[0])
    elif q[0] == 'back':
        if not queue:
            print(-1)
        else:
            print(queue[-1])

조건문만 잘 만들어내면 되는 문제라 그리 어렵지는 않았는데

시간 초과가 뜨길래 sys를 사용했다.

백준 4153 직각삼각형

# 4153 직각삼각형
while True:
    d = list(map(int, input().split()))
    if 0 in d:
        break
    a = max(d)
    d.remove(a)

    if d[0]**2 + d[1]**2 == a**2:
        print('right')
    else:
        print('wrong')

세 변 중 하나라도 0이 있으면 무한루프를 빠져나오게 만들고

직각삼각형 세 변의 공식에 따라 가장 큰 값만 구할 수 있으면 됐다.

백준 2775 부녀회장이 될 테야

#2775 부녀회장이 될테야

T = int(input())

for i in range(T):
    k = int(input()) # 층 수
    n = int(input()) # 호
    B = [[i for i in range(15)]]
    
    for j in range(1,k+1):
        B.append([])
        for _ in range(n+1):
            B[j].append(sum(B[j-1][:_+1]))
            
    print(B[k][n])

B[0]은 0층을 미리 넣어둔 것이고, 전체 리스트인 B는 반복문 안에 넣어줘

리스트를 반복할 때마다 초기화시켜주는 게 필요했다.

그다음으로는 층의 호수에 맞는 값을 하나하나 인덱싱에 맞춰 추가해주려고 했는데

그건 해결 못하고 append로 해결했다.

2022.01.10

백준 2178 미로 탐색

# 2178
from collections import deque

N, M = map(int, input().split())
arr = [list(map(int, input())) for i in range(N)]

def BFS(x,y):
    dx = [0,-1, 1, 0]
    dy = [1, 0, 0, -1]
    queue = deque()
    queue.append((x,y))
    
    while queue:   
        a, b = queue.popleft()
        for i in range(4):
            nx = a + dx[i]
            ny = b + dy[i]
            
            if 0<=nx<N and 0<=ny<M:
                if arr[nx][ny] == 1:
                    queue.append((nx,ny))
                    arr[nx][ny] = arr[a][b] + 1

BFS(0,0)
print(arr[N-1][M-1])

칸을 지나면 그다음 칸을 +1 해주는 아이디어로 풀었다.

방문처리를 안해서 중복 방문하기 때문에 다른 좌표들은 문제가 있지만

끝 좌표는 더이상 진행할 곳이 없어서 문제없다.

# 2178 방문처리 한 코드
from collections import deque

N, M = map(int, input().split())
arr = [list(map(int, input())) for i in range(N)]
visited = [[False]*M for i in range(N)]

def BFS(x,y):
    dx = [0,-1, 1, 0]
    dy = [1, 0, 0, -1]
    queue = deque()
    queue.append((x,y))
    
    while queue:   
        a, b = queue.popleft()
        for i in range(4):
            nx = a + dx[i]
            ny = b + dy[i]
            
            if 0<=nx<N and 0<=ny<M:
                if arr[nx][ny] == 1 and visited[nx][ny] == False:
                    queue.append((nx,ny))
                    visited[nx][ny] = True
                    arr[nx][ny] = arr[a][b] + 1

BFS(0,0)
print(arr[N-1][M-1])

방문처리 코드를 넣어도 시간이나 메모리에서 그다지 차이는 보이지 않았다.

F = list(input().lower()) # 문자를 소문자열로 받아옴
Q = list(set(F))          # 문자 갯수를 세기 위해서 중복 제거
cnt = 0                   # 가장 많은 문자 갯수 저장
R = []                    # 문자 갯수가 같은 문자 저장

# 가장 많은 문자의 갯수를 구하기 위한 반복문
for i in Q:               
  if F.count(i) > cnt:
    cnt = F.count(i)

# cnt와 중복값을 가진 문자를 R에 저장
for i in Q:
  if F.count(i) == cnt:
    R.append(i)
    
if len(list(set(R))) > 1:
  print('?')
else:
  print(R[0].upper())

맞추긴 했는데 메모리와 시간을 엄청 먹는다. 좀더 빠르게 푸는 방법은 없을까?

2022.01.07

백준 2667 단지 번호 붙이기

#2667 단지번호붙이기
from collections import deque

N = int(input())
arr = [list(map(int,input())) for i in range(N)]
visited = [[False]*N for i in range(N)]  # 한 번 들른 곳은 방문처리

dx = [-1, 0, 0, 1]    # 상하좌우의 좌표를 이용하기 위해서
dy = [0, 1, -1, 0]

R = []  # 단지 내 아파트 숫자를 저장하려는 리스트

def BFS(x,y):
    queue = deque()
    queue.append((x,y)) # (x,y)로 append하면 pop할 때 두 x,y를 한 번에 꺼낼 수 있다
    num = 0             # 단지 내 아파트 숫자 세기
    if arr[x][y] == 1 and visited[x][y] == False:
        num += 1
        visited[x][y] = True
        
    while queue:
        v,b = queue.popleft()
        
        for i in range(4):
            nx = v + dx[i]
            ny = b + dy[i]
            if 0<=nx<N and 0<=ny<N:
                if arr[nx][ny] == 1 and visited[nx][ny] == False:
                    queue.append((nx,ny))
                    visited[nx][ny] = True
                    num += 1
    return R.append(num)

for i in range(N):
    for j in range(N):  # 반복문 두개 돌려서 좌표 (0,0) 부터 (N-1,N-1)까지 확인
        if arr[i][j] == 1 and visited[i][j] == False:
            BFS(i,j)
            
print(len(R))
for i in sorted(R):
    print(i)

deque에 좌표(x,y)를 append 해서 한 번에 꺼내는 것을 몰랐다면 더욱 지저분한 코드가 되었을 것 같다.

return을 해주는 위치랑 nx,ny 범위 지정을 잘못했는데 못 찾아서 한참을 헤맸다.

DFS로 풀 때와 다른점은 좌표의 범위 제한을 while구문 안에 넣은 것과 visited를 사용한 점이다.

숙달되려면 멀었다. 더 많은 관련 문제를 풀어봐야지