반복문과 슬라이싱을 이용해서 남겨두어야 하는 최소 자리의 수들을 제외하고 가장 큰 수의 값과 인덱스를 이용하는 방법이다. 그러나 number 자체가 커지면 확인해야 하는 수의 크기도 커지게 되어 시간 초과가 발생한다.
def solution(number, k):
answer = ''
number = [int(i) for i in number]
return_len = len(number) - k
while return_len:
m = 0
idx = 0
for i in range(0,len(number)-return_len+1):
if number[i] > m:
m = number[i]
idx = i
if number[i] == 9:
break
number = number[idx+1:]
return_len-=1
answer+=str(m)
return answer
2. stack을 이용한 풀이 (정답)
stack을 이용해서 수를 담아놓고 만약 제거가 가능한 개수가 남아있다면
스택에 들어올 다음 수보다 작은 값들을 모두 팝해주는 방법으로 진행하였다.
스택 연산의 시간복잡도는 상수 이므로 최악의 경우에도 O(n)으로 연산을 수행 가능하다.
def solution(number, k):
answer = ''
number = [int(i) for i in number]
stack = []
for i in number:
if len(stack) == 0:
stack.append(i)
else:
if stack[-1] < i and k > 0:
while True:
if stack and stack[-1] < i and k>0:
stack.pop()
k-=1
else:
stack.append(i)
break
else:
stack.append(i)
stack = [str(i) for i in stack]
stack = stack[:-k] if k > 0 else stack
return ''.join(stack)
회고
stack과 queue를 적절하게 이용하는 방법을 찾아야할듯합니다. 그리디 문제를 만나면 사고가 제한되는 기분이라 이를 해결해야겠습니다.
풀이는 그래프를 돌면서 방문한 적이 없는 노드를 찾아 해당 노드를 시작점으로 bfs를 돌리는 방식으로 진행된다.
코드를 조금 나누어 설명한다.
1. Graph & visited 정의
그래프의 가로 세로가 모두 N으로 이루어지기 때문에 쉽게 만들어주었다.
graph = []
for _ in range(N):
graph.append(sys.stdin.readline().strip())
visited = [[0 for _ in range(N)] for _ in range(N)]
2. 반복문을 사용해 bfs함수가 있다고 가정하고 결과 모으기
bfs를 미리 정의하지 않고 반복문을 돌면서 시작점을 bfs함수에 넣는 로직을 먼저 생성해 주었다.
결과를 생각하면서 bfs함수에서 어떤 인자를 받아야 하고, 리턴은 어떻게 해야 하는지 생각할 수 있어 미리 진행했다.
answers = []
for row in range(N):
for j in range(N):
if graph[row][j] == '1' and visited[row][j]== 0:
c = bfs(row,j)
answers.append(c)
3. bfs함수 생성
코드가 길어짐에 따라서 bfs 구문을 함수의 형태로 빼내서 작성해 주었다.
이전에 방문한 기록이 있는지, 확인할 다음 노드가 그래프 안에 있는지, 다음 노드의 값이 1인지 확인하고 해당되는 경우에
큐에 다시 넣음과 동시에 count를 세주었다.
def bfs(s_r,s_c):
q = deque()
q.append([s_r,s_c])
visited[s_r][s_c] = 1
count = 1
while q:
r,c = q.popleft()
dr = [0,0,-1,1]
dc = [-1,1,0,0]
for i in range(4):
nr = r+dr[i]
nc = c+dc[i]
if 0<=nr<N and 0<=nc<N and graph[nr][nc] == '1' and visited[nr][nc] == 0:
count+=1
q.append([nr,nc])
visited[nr][nc] = 1
return count
전체 코드 및 주의사항
문제의 조건의 마지막에 오름차순으로 결괏값을 출력해야 한다는 문장이 있다. 주의
import sys
from collections import deque
N = int(sys.stdin.readline().strip())
graph = []
for _ in range(N):
graph.append(sys.stdin.readline().strip())
visited = [[0 for _ in range(N)] for _ in range(N)]
def bfs(s_r,s_c):
q = deque()
q.append([s_r,s_c])
visited[s_r][s_c] = 1
count = 1
while q:
r,c = q.popleft()
dr = [0,0,-1,1]
dc = [-1,1,0,0]
for i in range(4):
nr = r+dr[i]
nc = c+dc[i]
if 0<=nr<N and 0<=nc<N and graph[nr][nc] == '1' and visited[nr][nc] == 0:
count+=1
q.append([nr,nc])
visited[nr][nc] = 1
return count
answers = []
for row in range(N):
for j in range(N):
if graph[row][j] == '1' and visited[row][j]== 0:
c = bfs(row,j)
answers.append(c)
# print answer
print(len(answers))
answers.sort()
for a in answers:
print(a)
