Algorithm/프로그래머스
[프로그래머스] 64062. 징검다리 건너기
2019 카카오 개발자 겨울 인턴십 - 64062. 징검다리 건너기 Python 풀이 풀이 일단, 효율성을 측정하는 문제이기 때문에, 한 명이 징검다리를 건널 때 마다 모든 돌에 -1을 하고, 그 때마다 k보다 간격이 큰 징검다리가 있는 지 검사하는 방식은 통할 리가 없음. def solution(stones, k): for i in range(1, 200000000): stones = list(map(lambda x: x-1, stones)) cnt = 0 for stone in stones: if stone < 1: cnt += 1 if cnt == k: return i else: cnt = 0 이런 식으로. 당연히 정확성만 통과, 효율성은 통과 하나도 못 함. 풀이 2 이것도 Union-Find로 ..
[프로그래머스] 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들에 대해 순회하며 사이클이 생기지 않도록 간선(..
[프로그래머스] 42862. 체육복
접근 가장 주의할 점은, 여벌 체육복을 가져온 학생이 체육복을 도난당했을 수 있습니다. 이때 이 학생은 체육복을 하나만 도난당했다고 가정하며, 남은 체육복이 하나이기에 다른 학생에게는 체육복을 빌려줄 수 없습니다. 이 조건. 도난당했으나 여벌 체육복이 있는 학생(lost, reserve 배열에 모두 포함되는 학생)은 미리 빼 줄 필요가 있음. 그 이후는 lost를 순회하며 reserve에 +1 or -1 학생이 존재하는 지(앞뒤에 여벌 체육복을 가진 학생이 존재하는 지)만 확인. 확인할 때, 오름차순으로 순회할 거면 index가 -1인 학생(앞에 있는 학생)부터 체육복이 있는 지 조사하고, 내림차순으로 순회할 때는 반대로 index가 +1인 학생(뒤에 있는 학생)부터 조사해야 함. def solution..