Algorithm/Programmers
-
[Programmers] 단체사진 찍기Algorithm/Programmers 2020. 12. 28. 23:46
[2017 카카오코드 본선] 단체사진 찍기 programmers.co.kr/learn/courses/30/lessons/1835# Solution permutation으로 모든 캐릭터의 순서를 구한다음 조건에 맞는지 체크하는 방식으로 풀었다. 캐릭터의 위치를 저장하기 위해 알파벳을 idx로 하는 배열을 만들어 위치를 저장했는데 그렇게 할 필요없이 map으로 위치를 저장하는 방법도 있었다. 소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 ..
-
[Programmers] 호텔 방 배정Algorithm/Programmers 2020. 9. 2. 14:47
[2019 카카오 겨울 인턴십] 호텔 방 배정 https://programmers.co.kr/learn/courses/30/lessons/64063 Solution 처음에 연결리스트를 사용해서 room이 이미 선택됐을 경우 room+1 부터 순회하면서 방을 탐색하는 방식으로 구현했었는데 O(N)의 시간복잡도로는 해당 문제의 효율성 테스트를 통과할 수 없었다. 이후 다른 사람의 풀이에서 HashMap을 사용해 다음 방을 탐색하는 횟수를 최소로 하는 탐색 방법을 볼 수 있었다. map.put(선택된 방, 다음 방)으로 탐색의 시작점을 기록하는 것이다. 1. room_number 배열의 모든 원소에 대해 findEmptyRoom(int room) 함수를 호출 2. map에 room이 없는 경우는 아직 선택되지..
-
[Programmers] 2020카카오공채 문자열 압축Algorithm/Programmers 2020. 8. 24. 19:50
[Level 2] 문자열 압축 https://programmers.co.kr/learn/courses/30/lessons/60057 레벨 2 문제인데 문제를 제대로 이해하지 못해서 너무 오래 풀었다.. ㅠㅠ 압축할 문자열 s가 매개변수로 주어질 째, 1개 이상 단위로 문자열을 잘라 압축하여 표현한 문자열 중 가장 짧은 것의 길이를 return 하도록 solution 함수를 완성하시오. 헷갈렸던 포인트는 문자열을 앞에서 부터 n개씩 잘라야한다는 부분이 n=2, aa/ab/aa/dd/ee/... 같이 연속해서 n개로 압축하는 것이 아니라 aa/abcabcd/rr/dd/... 처럼 첫 부분만 2개로 잘리면 뒷부분에서는 자유롭게 2개씩 묶어 압축하는 방식으로 이해했다. 노답스;; Solution 완전 탐색으로 ..
-
[Programmers] 카카오프렌즈 컬러링북Algorithm/Programmers 2020. 6. 16. 12:23
[Level 2] 카카오프렌즈 컬러링북 https://programmers.co.kr/learn/courses/30/lessons/1829 그림에 몇 개의 영역이 있는지와 가장 큰 영역의 넓이는 얼마인지 계산하는 프로그램 작성 영역이란 상하좌우로 연결된 같은 색상의 공간을 의미한다. 그림의 원소 중 값이 0인 경우는 색칠하지 않는 영역을 뜻한다. Solution picture 전체 배열을 돌면서 0이 아니면서 아직 방문하지 않은 영역(count 하지 않은 영역)에 대해 BFS를 돌린다. BFS()에서는 해당 영역에 해당하는 최대 칸 수를 갱신하고 max 변수에 저장한다. 소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 2..
-
[Programmers] 라면공장Algorithm/Programmers 2020. 6. 4. 01:14
[Level 2] 라면공장 https://programmers.co.kr/learn/courses/30/lessons/42629 라면 공장에서는 하루에 밀가루를 1톤씩 사용합니다. 원래 밀가루를 공급받던 공장의 고장으로 앞으로 k일 이후에야 밀가루를 공급받을 수 있기 때문에 해외 공장에서 밀가루를 수입해야 합니다. 해외 공장에서는 향후 밀가루를 공급할 수 있는 날짜와 수량을 알려주었고, 라면 공장에서는 운송비를 줄이기 위해 최소한의 횟수로 밀가루를 공급받고 싶습니다. 현재 공장에 남아있는 밀가루 수량 stock, 밀가루 공급 일정(dates)과 해당 시점에 공급 가능한 밀가루 수량(suppies), 원래 공장으로부터 공급받을 수 있는 시점 k가 주어질 때, 밀가루가 떨어지지 않고 공장을 운영하기 위해서 ..
-
[Programmers] 괄호 변환Algorithm/Programmers 2020. 6. 2. 16:13
[Level 2] 괄호 변환 https://programmers.co.kr/learn/courses/30/lessons/60058 Solution 문제에서 주어진 조건대로 재귀 함수로 구현하여 풀 수 있었다. 소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 import java.util.*; class Solution { static StringBuilder sb; public String solution(String p) { String answer ..
-
[Programmers] 전화번호 목록Algorithm/Programmers 2020. 6. 1. 22:25
[Level 2] 전화번호 목록 https://programmers.co.kr/learn/courses/30/lessons/42577 전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다. 전화번호가 다음과 같은 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다. 구조대 : 119 박준영 : 97674223 지영석 : 1195524421 전화번호부에 적힌 전화번호를 담은 배열 phone_book이 solution 함수의 매개변수로 주어질 때, 어떤 번호가 다른 번호의 접두어인 경우가 있으면 false를 그렇지 않으면 true를 return 하도록 solution 함수를 작성해주세요. Solution phone_book[]의 원소를 String 길이 기준으로..
-
[Programmers] 멀쩡한 사각형Algorithm/Programmers 2020. 6. 1. 21:28
[Level 2] 멀쩡한 사각형 https://programmers.co.kr/learn/courses/30/lessons/62048 가로 길이가 Wcm, 세로 길이가 Hcm인 직사각형 종이가 있습니다. 가로, 세로 방향과 평행하게 격자 형태로 선이 그어져 있으며, 모든 격자칸은 1cm * 1cm 크기 입니다. 누군가 이 종이를 대각선 꼭지점 2개를 잇는 방향으로 잘라놓았습니다. 가로의 길이 W와 세로의 길이 H가 주어질 때, 사용할 수 있는 정사각형의 개수를 구하는 solution 함수를 완성해주세요. Solution 아이디어를 생각하기 어렵다 ㅠ-ㅠ,, 예시를 기준으로 12*8 크기의 직사각형 종이가 있을 때, 사용할 수 없는 정사각형의 패턴을 보면 2*3 크기의 직사각형 내에서 테트리스 모양의 4개..