기록하는, 성장하는

문제

아이디어

1. channel이 100이면 그냥 리턴한다. 
2. 모든 버튼이 다 고장 나면 +,- 로만 이동한다 
3-1. channel로 이동할 수 있는 버튼이 있으면 그 버튼을 누른다. 
3-2. 그 버튼이 없으면 제일 가까운 버튼을 찾아 누르고 3단계를 종료한다
4 3단계를 진행했는데 버튼의 개수가 channel의 개수보다 작으면 적절한 키를 찾아 나머지 자릿수를 채운다
4-1 만약 이미 선택한 버튼으로 내가 보고싶은 채널 이상이 만들어진다면 나머지 키는 현재 누를 수 있는 버튼의 제일 작은 값으로 채운다 
4-2 만약 이미 선택한 버튼으로 내가 보고싶은 채널 이하로 만들어진다면 나머지 키는 현재 누를 수 있는 버튼의 제일 큰 값으로 채운다 
5. 누를 버튼이 만들어졌으면 +나 - 개수를 센다. 이때 절댓값을 이용한다
6.+,-로만 이동하는 경우와 숫자버튼을 눌러 +-로 이동하는 경우 중 더 작은 값을 리턴한다

import sys
# from collections import deque
channel=input()
button=['0','1','2','3','4','5','6','7','8','9']
m=int(input())

#고장난 버튼 없음
if m==0:
  print(len(channel))
  sys.exit()

broken_set=set(input().split())
button=list(set(button)-broken_set)
now='100'

if channel==now:
  print(0)
  sys.exit()

# 모든 숫자 버튼이 다 고장남 
if not button:
  print(abs(int(channel)-int(now)))
  sys.exit()

press_num=[]

for c in list(channel):
  if c in button:
    press_num.append(c)
  else:
    min_diff=10
    replace_button=c
    for b in button:
      if min_diff>abs(int(c)-int(b)):
        replace_button=b
        min_diff=abs(int(c)-int(b))
    press_num.append(replace_button)
    break

if len(channel)>len(press_num):
  index=len(press_num)-1
  if int(press_num[index])>int(channel[index]):
    add_num=str(min(map(int,button)))
  else:
    add_num=str(max(map(int,button)))
    
  while len(channel)>len(press_num):
    press_num.append(add_num)

tmp=int(''.join(press_num))


print(min(abs(tmp-int(channel))+len(channel) ,abs(int(channel)-int(now))))

문제에 나와있는 예제는 다 맞는데 이 글에 있는 반례는 아직 해결 못했다. 

이후 추가하겠습니다 

https://www.acmicpc.net/problem/1260

from collections import deque

def dfs(graph,v,visited):
  visited[v]=True
  print(v, end=" ")
  for i in graph[v]:
    if not visited[i]:
      dfs(graph,i,visited)

def bfs(graph,v,visited):
  queue=deque([v])
  visited[v]=True
  while queue:
    node=queue.popleft()
    print(node,end=' ')
    for i in graph[node]:
      if not visited[i]:
        queue.append(i)
        visited[i]=True


n,m,v=map(int, input().split())
graph=[[] for _ in range(0,n+1)]

#양 방향의 간선
for _ in range(m):
  a,b=map(int, input().split())
  graph[a].append(b)
  graph[b].append(a)

#두 노드를 잇는 간선이 중복되서 들어올 수 있기 때문에 set()으로 중복제거
#숫자가 작은 노드를 먼저 선택해야 하므로 그래프를 정렬했다. 
for i in range(n+1):
  graph[i]=sorted(list(set(graph[i])))

print(graph)

visited=[False]*(n+1)
dfs(graph,v,visited)
print()
visited=[False]*(n+1)
bfs(graph,v,visited)

정석 코드 그대로 dfs는 재귀로 풀고 bfs는 큐로 풀면 된다. 

왜 이렇게 많이 틀렸냐 하면 

1. 오타를 낸 상태로 그대로 제출

2. 양 방향 간선임을 고려 안 하고 제출 

3. 같은 간선이 중복으로 들어오는 경우와 그 간선을 방문할 때 작은 숫자를 먼저 방문해야 하는 경우를 고려하지 못함 

이 세가지를 해결하니 무난하게 맞출 수 있었다. 꼼꼼히 하자 

문제 설명

풀이 

def solution(number, k):
    number=list(number)
    stack=[]
    stack.append(number.pop(0))
    
    while k>0:
        num=number.pop(0)
        if num<=stack[-1]:
            stack.append(num)
        else:
            while stack and stack[-1]<num and k>0:
                stack.pop()
                k-=1
            stack.append(num)
    return ''.join(stack+number)

스택을 하나 만들어 number를 숫자 앞에서 부터 하나씩 빼서 스택에 push 한다. 그리고 스택의 최상단의 값과 number에서 하나씩 뽑은 값을 비교해 스택의 최상단의 값이 작으면 제거한다. 이때 제거하는 수만큼 k에서 -1씩 하고 k개만큼 숫자를 빼면 종료한다. 

테스트 10은 시간 초과로 실패하고 테스트 12는 런타임 에러가 났다. 

테스트 12 런타임 에러 해결 : 만약 처음에 주어진 수가 87654321처럼 앞자리가 늘 큰 수면 위의 코드에서 런타임 에러가 난다. k가 감소하는 경우에 걸리지 않기 때문이다. 그러므로 k>0이고 number에 pop()할 거리가 남아있을 때까지만 while문을 돌리고 만약 while문 이후에서 k가 0보다 크다면 맨 뒷 수를 k개만큼 빼주면 된다 

수정된 코드

def solution(number, k):
    number=list(number)
    stack=[]
    stack.append(number.pop(0))
    
    while k>0 and number:
        num=number.pop(0)
        if num==9:
            stack.append(num)
            continue
        if num<=stack[-1]:
            stack.append(num)
        else:
            while stack and stack[-1]<num and k>0:
                stack.pop()
                k-=1    
            stack.append(num)
    stack=stack+number

    while k>0:
        stack.pop()
        k-=1

    return ''.join(stack)

테스트 10 해결 : 우선 구글링을 한 결과 테스트 10은 숫자가 9인 경우 바로 추가하고 다음 단계로 가야 한다고 했다. 위의 코드에도 그렇게 하도록 했는데 안된 걸 보면 내 코드에 군더더기가 좀 많았나 보다. 그래서 좀 더 고심해서 깔끔하게 코드를 손 봐주었다. 우선 마지막에 k가 0보다 클 경우 어차피 숫자 뒷부분을 잘라내줄 것이므로 차라리 number 전체를 순회하는 것이 더 나을 것이라고 생각되었다. 전체 while 문을 그냥 for문으로 변경하고 그에 맞게 내부 코드도 수정해 주었다. 

def solution(number, k):
    stack=[]

    for n in number:
        if n==9:
            stack.append(n)
            continue
        while stack and stack[-1]<n and k:
            stack.pop()
            k-=1    
        stack.append(n)
    
    while k:
        stack.pop()
        k-=1

    return ''.join(stack)

문제 설명

from collections import defaultdict

def solution(numbers):
    answer = ''
    numbers_dic=defaultdict(list)

    #맨 앞자리 수를 키로 갖는 딕셔너리
    for n in numbers:
        i=n
        while i>=10:
            i=i//10 
        numbers_dic[i].append(n)

    keys=sorted(numbers_dic.keys(),reverse=True)

    for k in keys:
        nums=[]
        for n in numbers_dic[k]:
            last_num=str(n%10)
            n_copy=str(n)
            while len(n_copy)<5:
                n_copy+=last_num
            nums.append((n,int(n_copy)))
        nums=sorted(nums,key=lambda x : x[1], reverse=True)
        for n in nums:
            answer+=str(n[0])
        
    return answer

n이 1000이하의 수 이므로 이를 푼다. 

실패한 이유 : 만약 [1,10,100,1000]의 경우 모두 마지막 숫자를 확장했을 때 1000으로 같다. 그러므로 sort 할 때 틀린다.

테스트 1,2,3,4,5,6,11 에서 오류가 났다. 

그러므로 nums를 정렬할 때 확장한 수의 결과가 같다면 제일 짧은 수를 먼저 정렬하는 방법을 추가해야 한다.

내가 생각했던 테스트 케이스를 통과했지만 위와 같은 테케는 통과하지 못했다. 

테스트 케이스 11번 [0,0,0,0] --> "0" 

:return 문을 수정해서 해결하였다. / 위의 코드를 좀 더 깔끔하게 작성하였다. 

from collections import defaultdict

def expand_num(n):
    n=int(str(n)+str((n%10))*(4-len(str(n))))
    return n

def solution(numbers):
    answer=''
    number_dic=defaultdict(list)

    for n in numbers:
        number_dic[str(n)[0]].append(n)
    for s in number_dic:
        number_dic[s]=sorted(number_dic[s],key=lambda x : (expand_num(x),-len(str(x))),reverse=True)

    for s in sorted(number_dic,reverse=True):
        answer+=''.join(map(str,number_dic[s]))

    return str(int(answer))

테스트 케이스 1~6 번 

[233,23] -> "23323"

끝 수를 늘릴 경우 둘다 2333,2333 이 되고 길이를 비교할 경우 더 짧은 23이 앞에 오게 되어 23233이 된다. 그러나 23323이 더 큰 수이다. 길이를 비교해 짧은 코드를 앞에 정렬하는 코드는 [1,10,100,1000]의 경우를 위해 추가된 코드이므로 두 케이스가 상반된다. 

차라리 처음부터 다시 생각해 보자면 

10,100 의 경우 앞 자릿수가 더 크기 때문에 길이가 짧은 수가 먼저 와야 맞고 

23,233의 경우 뒷자리가 더 크기 때문에 길이가 긴 수가 먼저 와야 맞다  

위의 것을 판별하는 함수를 따로 짜서 차라리 람다식의 두 번째 비교 인자로 줄까 했는데 한 자릿수의 숫자의 경우 애매했다 

def solution(numbers):
    numbers = list(map(str, numbers))
    numbers.sort(key=lambda x: x * 3, reverse=True)
    return str(int(''.join(numbers)))

위의 식은 다른분의 식을 참고한 식이다. 이런 식으로 str의 특성을 이용해서 풀이하면 간단하게 풀 수 있다. 

https://programmers.co.kr/learn/courses/30/lessons/42862

문제 설명

풀이 1 

여분의 옷을 가져온 학생이 옷을 잃어버린 경우를 먼저 제외한 후 옷이 없는 학생이 옷을 빌릴 수 있는지 점검하고 끝내 옷을 빌리지 못했을 경우 students 배열에서 제외했다. 

def solution(n, lost, reserve):
    students=set([i for i in range(1,n+1)])

    #여분의 옷을 가져온 학생이 잃어버린 경우
    lost=set(lost)-set(reserve)
    reserve=set(reserve)-set(lost)

    no_clothes=list(lost)
    for l in no_clothes:
        if l+1 in reserve:
            reserve.remove(l+1)
            lost.remove(l)
            continue
        
        if l-1 in reserve:
            reserve.remove(l-1)
            lost.remove(l)
            continue
        students.remove(l)
    return len(students)

테스트 1,2,3,5,6,9,10,12 오류 --> 여분의 옷을 가져온 학생이 잃어버린 경우가 담긴 테스트 케이스이다. 

풀이 2

def solution(n, lost, reserve):
    students=[i for i in range(1,n+1)]
    
    #여분의 옷을 가져온 학생이 잃어버린 경우
    lost_but_reserve=set(lost)&set(reserve)
    lost=list(set(lost)-lost_but_reserve)
    reserve=list(set(reserve)-lost_but_reserve)
    
    lost.sort()
    reserve.sort()

    for l in lost:
        if l-1 in reserve:
            reserve.remove(l-1)
            continue
        if l+1 in reserve:
            reserve.remove(l+1)
            continue
        students.remove(l)
    return len(students)

위의 코드에서 여분의 옷을 가져온 학생 코드를 수정하니깐 해결되었다. 즉 위의 코드의 경우 lost에서 이미 교집합을 제거해줬기 때문에 reserve에서 lost를 차집합 할 때 아무런 원소도 삭제되지 않아서 생긴 결과였다. 

통과

https://programmers.co.kr/learn/courses/30/lessons/42576

문제 설명

풀이

우선 간단히 생각해서 python의 list 내장함수인 remove를 이용했다 

def solution(participant, completion):
    for c in completion:
        participant.remove(c)
    return ''.join(participant)

정확성 테스트는 통과하지만 효율성 테스트에서 점수를 하나도 못 받았다. 해시를 이용해 시간 복잡도를 줄여야겠다.

from collections import defaultdict

def solution(participant, completion):
    answer=[]
    participant_dic=defaultdict(int)
    //동명이인을 고려하여 딕셔너리의 value로 명수를 넣었다.
    for p in participant:
        participant_dic[p]+=1
    for c in completion:
        participant_dic[c]-=1
    for p in participant_dic:
        if participant_dic[p]>0:
            answer.append(p)

    return ''.join(answer)

https://wiki.python.org/moin/TimeComplexity

위 문서를 참조하면 파이썬 문서에 시간복잡도가 명시되어 있다. 아래 그림과 같이 list.remove를 사용하면 평균 O(n)의 시간이 소요된다. 그러므로 dic를 사용해서 시간 복잡도를 O(n)으로 줄이면 효율성 테스트를 통과할 수 있다.

(추가) 문제 오류 

생각해보니 동명이인이 3명인 경우에 그 중 한명만 통과했을 경우가 테스트 케이스에 없는 것 같다. 예를들어 

participant: [leo,leo,leo] completion : [leo] 인 경우에는 위의 코드가 오류가 난다 

그러므로

from collections import defaultdict

def solution(participant, completion):
    answer=[]
    participant_dic=defaultdict(int)
    for p in participant:
        participant_dic[p]+=1
    for c in completion:
        participant_dic[c]-=1

    for p in participant_dic:
        if participant_dic[p]>0:
            for _ in range(0,participant_dic[p]):
                answer.append(p)

    return ' '.join(answer)

위의 코드와 같이 participant_dic의 value값 만큼 answer 에 추가해야 상황에 더 적합한 코드이다.