728x90
반응형
문제 바로가기
문제:
0으로 시작하지 않는 정수 N이 주어진다. 이때, M을 정수 N의 자릿수라고 했을 때, 다음과 같은 연산을 K번 수행한다.
1 ≤ i < j ≤ M인 i와 j를 고른다. 그 다음, i번 위치의 숫자와 j번 위치의 숫자를 바꾼다. 이때, 바꾼 수가 0으로 시작하면 안 된다.
위의 연산을 K번 했을 때, 나올 수 있는 수의 최댓값을 구하는 프로그램을 작성하시오.
입력:
0으로 시작하지 않는 정수 N이 주어진다. 이때, M을 정수 N의 자릿수라고 했을 때, 다음과 같은 연산을 K번 수행한다. 1 ≤ i < j ≤ M인 i와 j를 고른다. 그 다음, i번 위치의 숫자와 j번 위치의 숫자를 바꾼다. 이때, 바꾼 수가 0으로 시작하면 안 된다. 위의 연산을 K번 했을 때, 나올 수 있는 수의 최댓값을 구하는 프로그램을 작성하시오.
출력:
첫째 줄에 문제에 주어진 연산을 K번 했을 때, 만들 수 있는 가장 큰 수를 출력한다. 만약 연산을 K번 할 수 없으면 -1을 출력한다.
풀이:
첫 시도는
그리디하게 생각했다.
첫 번째 숫자부터 시작해서 가장 큰 숫자와 교환을 해주는경우이다,
근데 만약 1553 처림 큰 숫자가 2개인 경우에는 1에 가까운 5를 가져오기때문에 k의 값이 많아지면 잘 되지않는다.
그래서 인덱스값까지 알고 있는상태에서 인덱스가 가장 큰 값에서 숫자를 가져온다.
하지만 틀린다. 이유는 10000 같은 숫자들일때 교환을 하지 않는다. 좀만 건들면 맞을거 같기는 한데 일단 제꼈다.
틀린 코드 :
import sys
n, k = map(int, sys.stdin.readline().split())
numbers = list(enumerate(map(int, str(n))))
flag = False
m = len(numbers)
if m == 1 or (m == 2 and numbers[1][1] == 0):
print(-1)
exit()
# 결국에 자기보다 큰 숫자중 가장 큰것과 바꾸면 됨
def dfs(node, depth):
print(numbers)
if depth == k:
return [str(i[1]) for i in numbers]
max_num = numbers[node]
for idx, number in numbers[node + 1:]:
if number >= max_num[1] and idx > max_num[0]:
max_num = [idx, number]
numbers[node], numbers[max_num[0]] = max_num, numbers[node]
return dfs(node + 1, depth + 1)
result = dfs(0, 0)
if flag:
result[-1], result[-2] = result[-2], result[-1]
print("".join(result))
맞는 코드
BFS로 죽여줬다.
import sys
from collections import deque
sys.stdin = open('/Users/song/Desktop/Python/Python/h.txt', 'r')
n, k = map(int, sys.stdin.readline().split())
numbers = list(map(int, str(n)))
m = len(numbers)
if m == 1 or (m == 2 and numbers[1] == 0):
print(-1)
exit()
# BFS를 사용하여 탐색
def bfs():
queue = deque([(numbers, 0)])
visited = set()
visited.add((tuple(numbers), 0))
max_result = -1
while queue:
current, depth = queue.popleft()
if depth == k: # K번 교환 완료 시
max_result = max(max_result, int("".join(map(str, current))))
continue
for i in range(m):
for j in range(i + 1, m):
if i == 0 and current[j] == 0:
continue
# 교환
next_state = current[:]
next_state[i], next_state[j] = next_state[j], next_state[i]
if (tuple(next_state), depth + 1) not in visited:
visited.add((tuple(next_state), depth + 1))
queue.append((next_state, depth + 1))
return max_result
result = bfs()
print(result)
반응형
댓글