최소, 최대

#10818
N = int(input())
arr = list(map(int, input().split()))
print(min(arr),max(arr))

위 코드가 훨씬 빠르다.

#10818
N = int(input())
arr = sorted(list(map(int, input().split())))
print(arr[0],arr[-1])

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

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

# 10809
alphabet = []
arr = [-1 for i in range(26)]
for i in range(97,123):
  alphabet.append(chr(i))
S = input()
for i in S:
  if arr[alphabet.index(i)] == -1:
    arr[alphabet.index(i)] = S.index(i)

for i in arr:
  print(i, end = ' ')

# 8958
T = int(input())

for i in range(T):
  R = 0              # 총 합
  P = 0              # 'O'이 나올 때마다 그 문제의 점수
  a = list(input())
  for j in a:
    if j == 'O':
      P += 1
      R = R+P 
    else:
      P = 0         # 'X'가 나오면 점수 초기화
  print(R)

# 3052
arr = []

for i in range(10):
  a = int(input())
  arr.append(a%42)

print(len(list(set(arr))))

# 2675
T = int(input())

for i in range(T):
  R, S = input().split()
  R = int(R)
  P = list(S)
  Q = ''
  for j in P:
    Q = Q+j*R
  print(Q)

print(, end ='')으로 풀면 되겠네하고 쉽다고 생각했다가 머리 쥐 나는 줄 알았다.

# 2439 
N = int(input())
for i in range(N):
  print(('*'*(i+1)).rjust(N))

출력할 때 오른쪽 정렬은 .rjust(출력자리수) 왼쪽 정렬은 .ljust(출력자리수)

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를 사용한 점이다.

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

2022.01.06

백준 2606 바이러스

## 2606
from collections import deque

N = int(input())
C = int(input())
arr = [[] for i in range(N+1)]        # N+1 해준 이유는 숫자 인덱싱을 맞추려고

for i in range(C):
    a, b = map(int,input().split())
    arr[a].append(b)
    arr[b].append(a)

visited = []        # 방문한 컴퓨터 번호
def BFS(x):
    queue = deque([x])
    visited.append(x)
    
    while queue:
        v = queue.popleft()
        for i in arr[v]:
            if i not in visited:
                queue.append(i)
                visited.append(i)
                
BFS(1)
print(len(visited) -1) # 1번 컴퓨터는 제외

queue는 while 문이 핵심 같다.popleft를 통해서 나온 수를 인덱스로 사용해서 큐에 다시 삽입하고

다시 반복을 통해서 queue를 공백으로 만드는 것이 재귀를 이용하는 DFS와의 차이처럼 느껴진다.