4963 - 섬의 개수
BFS
8방향
visited 사용 안하는 방법 = BFS 탐색으로 들어간 섬을 0으로 바꿔준다.
BFS call 할 때마다 섬의 개수를 1개씩 늘린다 (count += 1)
from collections import deque
import sys
input = sys.stdin.readline
dx = [0, 0, -1, 1, 1, -1, 1, -1]
dy = [1, -1, 0, 0, -1, -1, 1, 1]
ans = []
def bfs(v):
q = deque()
q.append(v)
while q:
v = q.popleft()
for dir in range(8):
ni, nj = v[0]+dx[dir], v[1]+dy[dir]
if 0 <= ni < h and 0 <= nj < w and graph[ni][nj] == 1:
graph[ni][nj] = 0
q.append([ni, nj])
while True:
w, h = map(int, input().split())
count = 0
if w == h == 0:
break
graph = []
for _ in range(h):
graph.append(list(map(int, input().split())))
for i in range(h):
for j in range(w):
if graph[i][j] == 1:
bfs([i, j])
count += 1
ans.append(count)
print(*ans, sep='\n')
3518 - 공백왕 빈칸
https://www.acmicpc.net/problem/3518
포기
17609 - 회문
회문 0
유사회문 1
일반문 2
문자열 입력
a b b a
0 1 2 3
짝수면 (0+3) / 2 => 1
홀수면 (0+2) / 2 => 1
탐색 기본 rst = 0
조건 추가
s u m m u u s
"유사 펠린드롬" => 어떤 문자를 제거해야 되는지 알아야 함.
x a b b a
a b b a x
대칭...양쪽 끝에서 하나씩 보는 거 말고
대칭을 확인하는 다른 방법
..
[펠린드롬 함수]
양쪽에서 확인하면서 온다
만약에 다르다 ex. x, a = str[0] str[4]
그러면 이거 임시로 저장하고 다음거 본다.
그 다음 두 개 중에 x나 a 중 대칭이 되는 것이 있을 것
대칭이 안되는 걸 뺀다 ex. 다음이 a, b = str[1] str[3]
+1 (유사 후보)
왜냐, 유사 펠린드롬은 한 문자 삭제하면 대칭이 됨
i와 -(i+1)가 달라
둘 다 자기 자신을 뺀 나머지 문자가 펠린드롬인지 검사
(자기자신을 제외하고 부분문자열을 합친다.)
ex. str[i]빼기 = str[:i] + str[i+1:]
나머지 문자가 펠린드롬이면 유사펠린드롬이고
아니면 일반문이다.
import sys
input = sys.stdin.readline
def is_pd(arr):
for i in range(len(arr)):
if arr[i] != arr[-i-1]:
return False
return True
t = int(input())
for _ in range(t):
rst = 0
str = list(input().rstrip())
check = len(str) // 2
if is_pd(str): # 바로 펠린드롬이면 0
rst = 0
else: # 아니면 유사 혹은 일반문
for i in range(check):
if str[i] != str[-(i+1)]:
outI1 = str[:i]+str[i+1:]
outI2 = str[:-(i+1)]+str[-i:]
if is_pd(outI1) or is_pd(outI2): # 유사펠린드롬이야
rst = 1
else: # 안되네? = 일반문
rst = 2
print(rst)
1차코드, 시간초과 문제
투포인터를 사용하지 않아서 틀렸다.
투포인터의 개념을 모른다.
공부시작.
파이썬에서는 left, right로 리스트를 옮겨다니면 되는 것 같다.
모든 경우를 테스트하면 O(N^2)이지만
투 포인터를 사용하면 O(N)이 된다.
투 포인터 적용하면
left, right에서 하나씩 줄면서 탐색.
다만, 두 문자가 다를 때 로직이 다름.
이미 지나온 문자는 "다르다"에서 검사 안됨 = 이미 펠린드롬 대칭이다.
그러면 left빼면 left + 1: right,
right 빼면 left:right+1
까지만 검사하면 된다.
두 포인터가 최대로 움직여도 2N이므로
시간복잡도는 O(N)
import sys
input = sys.stdin.readline
def is_pd(arr, left, right):
while left < right:
if arr[left] != arr[right]:
return False
left += 1
right -= 1
return True
t = int(input())
for _ in range(t):
rst = 0
str = list(input().rstrip())
left, right = 0, len(str)-1
while left < right:
if str[left] != str[right]:
if is_pd(str, left+1, right) or is_pd(str, left, right-1):
print(1)
else:
print(2)
break
left += 1
right -= 1
else:
print(0)
1259 - 팰린드롬수
날먹하기
import sys
input = sys.stdin.readline
def is_pd(arr, left, right):
while left < right:
if arr[left] != arr[right]:
return False
left += 1
right -= 1
return True
while True:
A = list(map(int, input().rstrip()))
if A[0] == 0 and len(A) == 1:
break
left, right = 0, len(A)-1
if is_pd(A, left, right):
print('yes')
else:
print('no')
2609 - 최대공약수와 최소공배수
10000이하의 자연수
맞긴한데 지저분함
내코드)
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
# 약수 찾기
s = min(n, m)
a1 = []
a2 = []
for i in range(1, s+1):
tmp1 = n / i
tmp2 = m / i
if int(tmp1) == tmp1:
a1.append(i)
a1.append(int(tmp1))
if int(tmp2) == tmp2:
a2.append(i)
a2.append(int(tmp2))
ans = []
for item in a1:
if item in a2:
ans.append(item)
S = max(ans)
print(S)
rst = (n*m)//S
print(rst)
다른풀이) 예전에 GCD 많이 풀었는데 다 까먹음.
최대공약수 - i 탐색을 range(min(a,b), 0, -1)로 줄여나감. 둘 다 동시에 나눠질 때 (나머지 연산이 0) 출력하고 종료
최소공배수 - for문을 최소로 돌리는 범위 : range(max(a,b), (a*b)+1), i가 a와 b로 동시에 나눠지면 출력하고 종료.
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
# 최대공약수
for i in range(min(n, m), 0, -1):
if n % i == 0 and m % i == 0:
print(i)
break
# 최소공배수
for i in range(max(n, m), n*m + 1):
if i % n == 0 and i % m == 0:
print(i)
break
모르는대로 마구잡이로 푼 내 코드는 정말로 지저분 그 자체다. ㅠ
