Algorithm

[프로그래머스] 64063. 호텔 방 배정

2019 카카오 개발자 겨울 인턴십 - 64063. 호텔 방 배정 Python 풀이 풀이 Union-Find 알고리즘을 이용하여 풀면 될 것이라고 직감이 왔다. [백준] 10775. 공항 문제와 굉장히 유사했기 때문. 그런데 이제, 효율성을 위해 알고리즘을 조금 바꿀 필요가 있었다. Find는 그대로 두지만, Union하는 과정에서, 무조건 숫자가 높은 쪽이 root가 되도록 하는 것. 그렇게 하고, n번의 방이 찰 때마다, n과 n+1을 Union하는 방식으로 진행한다. 이 예시에서는, k = 10 room_number = [1,3,4,1,3,1] 맨 처음엔 dictionary가 이 상태일 것이다. {1: 1, 2: 2, 3: 3, 4: 4, 5: 5, 6: 6, 7: 7, 8: 8, 9: 9, 10:..

[프로그래머스] 64064. 불량 사용자

2019 카카오 개발자 겨울 인턴십 - 64064. 불량 사용자 Python 풀이 풀이 우선 user_id 배열의 크기는 1 이상 8 이하입니다. banned_id 배열의 크기는 1 이상 user_id 배열의 크기 이하입니다. 의 조건이 존재하기 때문에, 효율성을 크게 따질 필요는 없어 보임. isSame() => banned ID에 user ID가 들어갈 수 있는 지 확인하는 함수. 하나 만들어 놓고, 빈 dictionary(able) 생성해서, banned_id 의 index 순으로 대입 가능한 user_id 의 배열을 집어넣어 놓음. user_id = ["frodo", "fradi", "crodo", "abc123", "frodoc"] banned_id = ["fr*d*", "*rodo", "***..

[프로그래머스] 64065. 튜플

2019 카카오 개발자 겨울 인턴십 - 64065. 튜플 풀이 map과 split을 적절히 이용해서 배열화한 후, 길이가 작은 순서대로 중복없이 집어넣어야 순서가 맞음. def solution(s): def split_(s): return list(s.split(',')) s = s[2:-2] s = list(s.split('},{')) s = list(map(split_, s)) for i, a in enumerate(s): s[i] = list(map(int, a)) s.sort(key=lambda x: len(x)) answer = [] for a in s: for i in a: if i not in answer: answer.append(i) return answer

[프로그래머스] 64061. 크레인 인형뽑기 게임

2019 카카오 개발자 겨울 인턴십 - 64061. 크레인 인형뽑기 게임 풀이 Stack을 이용하면 간단히 풀 수 있는 문제. from collections import deque def solution(board, moves): stack = deque([]) answer = 0 for move in moves: for i in range(len(board)): if board[i][move-1] != 0: stack.append(board[i][move-1]) board[i][move-1] = 0 break if len(stack) >= 2 and stack[-1] == stack[-2]: stack.pop() stack.pop() answer += 2 return answer

[프로그래머스] 42884. 단속카메라

[프로그래머스] 42884. 단속카메라 - 파이썬 https://school.programmers.co.kr/learn/courses/30/lessons/42884 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 그리디하게 풀어내면 어렵지 않게 풀 수 있다. 크게 생각할 거리가 없었던 문제. 풀이 routes 배열을 우선 진출 지점 기준으로 정렬해준 뒤, 배열을 하나씩 순회하며 검사. 범위 안에 카메라가 없다면 진출 지점에 카메라를 설치 (가장 적게.. Greedy하게 카메라를 설치하게 되는 최적의 위치) 범위 안에 카메라가 이미 설치되었다면 continu..

[프로그래머스] 42861. 섬 연결하기

https://school.programmers.co.kr/learn/courses/30/lessons/42861 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 최소 신장 트리 (MST)의 Kruskal 알고리즘을 이용하여 풀었음. 우선 cost에 따라 오름차순으로 배열 정렬. vertex의 연결을 저장하고, Union-Find에 이용할 dicionary를 하나 생성하고, union-find를 구현(find, union func.) Kruskal 알고리즘을 적용해 cost가 낮은 순으로 정렬한 edge들에 대해 순회하며 사이클이 생기지 않도록 간선(..

[백준] 2437. 저울

https://www.acmicpc.net/problem/2437 2437번: 저울 하나의 양팔 저울을 이용하여 물건의 무게를 측정하려고 한다. 이 저울의 양 팔의 끝에는 물건이나 추를 올려놓는 접시가 달려 있고, 양팔의 길이는 같다. 또한, 저울의 한쪽에는 저울추들만 놓 www.acmicpc.net 풀이를 생각해내기 쉽지 않았던 문제. 풀이 입력된 숫자 배열을 오름차순으로 정렬한 후 검사. 만약 [이전의 숫자들을 더한 결과 + 1] < [다음 숫자] 라면, 더해서 만들 수 없는 수가 생기게 됨. EX 1 - [1, 2, 2, 7, 9, 13, 15] 1+2+2 + 1 < 7 이므로 &#39;6&#39; 을 만들 수 없음 EX 2 - [1, 1, 4, 9, 13] 1+1 + 1 < 4 이므로 &#39;3..

[백준] 1700. 멀티탭 스케줄링

[백준] 1700. 멀티탭 스케줄링 - 파이썬 https://www.acmicpc.net/problem/1700 1700번: 멀티탭 스케줄링 기숙사에서 살고 있는 준규는 한 개의 멀티탭을 이용하고 있다. 준규는 키보드, 헤어드라이기, 핸드폰 충전기, 디지털 카메라 충전기 등 여러 개의 전기용품을 사용하면서 어쩔 수 없이 각종 전 www.acmicpc.net 풀이 플러그를 새로 꽂을 때마다 경우의 수가 나눠지는데 플러그 자리가 남아 있을 때 꽂혀 있는 기기를 그대로 사용 플러그 하나를 빼야 함. 1, 2번은 그냥 처리하면 되고, 3번을 처리하는 방법이 문제다. Greedy하게 처리하자면, 앞으로 쓸 일이 없거나, 가장 나중에 사용할 기기를 빼는 것이 최선이므로, 그렇게 처리함. from collection..