알고리즘 문제 썸네일형 리스트형 2018 카카오 블라인드 코딩 테스트 1차 길 찾기 게임 root의 y값은 가장 크다. 이후의 root의 왼쪽, 오른쪽 자식은 차례대로 y값이 감소한다. 자식 삽입은 자식의 x값이 root의 x보다 큰지 작은지로 판단하면 된다. 테스트 케이스 6, 7번 런타임 에러가 나는 경우가 있는데 python에선 stack overflow를 방지하기 위해 재귀 횟수에 제한을 둔다. 횟수 제한 확인은 파이썬 콘솔 상에서 아래 코드를 입력하면 된다. 제한은 1000번이다. import sys sys.getrecursionlimit() 재귀 제한을 변경하는 방법은 아래와 같다. import sys sys.setrecursionlimit(10**4) 이걸 코드 상단에 작성해주면 이 문제에 대한 테스트 케이스를 커버할 수 있다. 아래 작성한 find() 메서드는 사용되지 않는다... 2018 카카오 블라인드 코딩 테스트 1차 무지의 먹방 라이브 단순히 풀면 효율성 탈락.. 한번에 음식을 없애고 그만큼의 시간을 감소시키는 방법을 썼다. 이런 생각을 어떻게 하지 def solution(food_times, k): # food_times를 value 오름차순 후 index 오름차순 times = sorted(enumerate(food_times), key=lambda k:(k[1], k[0])) before = 0 length = len(times) for i, v in enumerate(times): diff_v = v[1] - before diff_l = length - i if diff_v != 0: past_time = diff_v * diff_l if k >= past_time: k -= past_time before = v[1] else:.. 2018 카카오 블라인드 코딩 테스트 1차 실패율 런타임 에러가 좀 났었는데 나누는 값이 0인 경우 처리를 안해줘서 났다. 1부터 N까지의 stage 번호를 level(단계)로 표현하고 각 level마다 stages를 돌면서 유저가 있는 stage가 level보다 크거나 같다면 스테이지에 도달한 유저인 arriver를 1증가시키고, level과 유저가 있는 stage가 같다면 아직 클리어 못했으므로 not_clear를 1 증가시킨다. 나누는 값인 arriver가 0인 경우 level에 대한 실패율은 0으로 처리한다. 도착한 사람이 있는 경우엔 실패율을 구한다. fail_ratio는 각 스테이지를 key로 실패율을 value로 저장한다. 주어진 스테이지를 모두 돌았다면 dict의 value를 기준으로 내림차순 정렬한다. (1차로 value를 기준으로 정렬.. 2018 카카오 블라인드 코딩 테스트 1차 오픈채팅방 record에 있는 문자열을 공백 단위로 끊어서 list화 했다. Enter인 경우 name_dict에 uid를 key로 하고 name을 value로 넣었다. Change인 경우 name이 갱신된다. Leave했다가 Enter한 경우도 갱신된다. 최종적으로 이름을 다 바꿨으면 record에 있는 순서대로 uid로 name_dict에 접근해서 value를 가져온다. def solution(record): name_dict = {} msg_list = [] for i, msg in enumerate(record): record[i] = msg.split(' ') for msg in record: if len(msg) > 2 and msg[0]: name_dict[msg[1]] = msg[2] for msg .. 프로그래머스 단어 변환 BFS, DFS 두가지 방법으로 다 풀 수 있는 것 같다. DFS로 target에 도달할 때까지의 모든 거리 중 최소 거리를 구하면 될 것 같았는데 막상 해보니까 잘 안됐다.. BFS로 풀었다. 레벨별로 그래프 탐색을 하다가 target을 만나면 도달하는데 걸린 거리를 반환하면 된다. 시작하는 노드를 queue에 넣고 while문을 돌린다. while문이 끝날 때까지 answer를 찾지 못하면 0을 반환한다. checker는 BFS를 하면서 이전 레벨의 노드를 재방문하지 못하게 하기 위한 것이다. queue_tmp를 생각해내기 어려웠는데, queue만 사용해서 노드를 추가하게 되면 레벨이 증가할 때마다 answer가 증가하는 게 아니라 같은 레벨의 노드를 방문하는데도 answer를 증가시키게 된다. qu.. 프로그래머스 네트워크 computers의 각 원소는 컴퓨터이므로 컴퓨터마다 돌면서 연결된 컴퓨터들을 체크하면 된다. queue를 활용한 BFS를 적용한 check_com으로 초기에 선택한 컴퓨터에 연결된, 아직 체크되지 않은 모든 컴퓨터에 대해서 체크해준다. 이 컴퓨터는 queue에 들어간다. queue가 빌 때까지 check_com을 계속 호출하면 연결된 네트워크를 찾을 수 있다. 나머지 컴퓨터에 대해서 검사를 하는데 이미 체크된 것은 특정 네트워크에 속한 것이므로 검사할 필요가 없다. 체크되지 않은 컴퓨터가 있다면 answer를 증가시키고 컴퓨터를 queue에 넣고 check_com을 호출한다. 결론은 컴퓨터 하나하나를 트리의 root로 생각하고 방문하지 않았으면 answer를 증가시키고 연결된 컴퓨터(노드들)를 방문하는.. 프로그래머스 타겟 넘버 DFS를 활용했다. answer는 target과 일치하면 1씩 누적하는 변수다. 두 함수에서 사용할 수 있도록 전역변수로 만들었다. numbers와 길이, target, 0을 인자로 갖는 make_target을 호출한다. i는 level을 측정하면서 numbers의 index로도 쓰인다. numbers의 끝까지 탐색을 했다면 numbers의 합이 target과 일치하는지 판단하고 일치한다면 answer에 1을 누적한다. 그리고 make_target 함수를 종료한다. 트리 레벨(i)에 따라 레벨에 있는 하나의 원소의 기호를 변경해준다. numbers[i] *= 1 make_target(numbers, target, length, i+1) numbers[i] *= -1 make_target(numbers, .. 프로그래머스 입국심사 최악의 경우 심사를 가장 느리게 하는 곳에서 모든 사람이 심사 받는 경우다. max(times) x n 최대 시간(max(times) x n), 최소 시간(0)을 가지고 이분탐색을 하면서 중앙값을 찾는다. 입국 심사대를 돌면서 심사대당 주어진 시간 내에 몇명을 처리할 수 있는지 구한다. 처리할 수 있는 누적 인원이 n과 같을 때 일단 list에 삽입해놓는다. 주어진 시간 내에 n명을 초과해서 처리할 수 있고, 초과된 인원이 현재 심사대에서 주어진 시간 내에 처리할 수 있는 인원보다 작거나 같으면 list에 중앙값을 추가한다. (count와 n이 일치하지 않더라도 시간 내에 처리할 수 있는 시간인 경우를 포함시킴) list에는 n명을 처리할 수 있는 시간들이 있는데 가장 작은 값이 답이다. def solu.. 이전 1 2 3 4 ··· 16 다음
