언젠가 꽃이 될 개발자

문제: https://school.programmers.co.kr/learn/courses/30/lessons/42586유형: 스택/큐풀이 저장소: GitHub 문제 요약기능마다 현재 진도(%)와 하루 개발 속도가 주어진다. 뒤 기능은 앞 기능이 배포될 때 함께 배포된다. 배포마다 몇 개의 기능이 나가는지 순서대로 반환한다. 왜 큐일까?문제에서 본 부분신호그래서뒤에 있는 기능이 먼저 개발될 수 있다끝난 순서와 배포 순서가 다르다배포는 앞에서부터앞에 있는 기능이 배포될 때 함께 배포된다맨 앞이 나가야 뒤도 나간다맨 앞을 기준으로 묶는다배포마다 몇 개의 기능이 배포되는지묶음의 크기를 묻는다큐에 모았다가 size()들어온 순서대로 처리하고 맨 앞이 기준이 된다. 큐가 맞는 구조다. 이 문제의 핵심기능마다 끝나..

문제: https://school.programmers.co.kr/learn/courses/30/lessons/12906유형: 스택/큐풀이 저장소: GitHub 문제 요약0~9로 이루어진 배열에서 연속으로 나오는 같은 숫자를 하나만 남긴다. 남은 숫자는 원래 순서를 유지해서 반환한다. 왜 스택/큐일까?문제에서 본 부분신호그래서연속적으로 나타나는 숫자는 하나만 남긴다바로 앞 숫자와만 비교하면 된다결과의 맨 끝 하나만 본다배열 원소들의 순서를 유지해야 한다넣은 순서대로 꺼내야 한다큐처럼 앞에서부터 꺼낸다결과 개수를 미리 알 수 없다크기가 고정된 배열에 바로 담기 어렵다컬렉션에 모은 뒤 배열로 옮긴다넣을지 말지는 맨 끝을 보고 정하고, 꺼낼 때는 맨 앞부터 꺼낸다. 양쪽 끝을 모두 쓰기 때문에 Deque(양방..

문제: https://school.programmers.co.kr/learn/courses/30/lessons/42579유형: 해시풀이 저장소: GitHub 문제 요약노래마다 장르와 재생 횟수가 주어진다. 총 재생 수가 많은 장르부터, 장르 안에서는 재생 수가 많은 노래부터 장르당 최대 2곡씩 골라 고유 번호를 순서대로 반환한다. 왜 해시일까?문제에서 본 부분신호그래서속한 노래가 많이 재생된 장르를 먼저 수록장르별 합계가 필요하다장르 → 총 재생 수 Map장르 내에서 많이 재생된 노래를 먼저 수록장르별로 노래를 묶어야 한다장르 → 노래 번호 List Map장르가 "classic", "pop" 같은 문자열배열 인덱스로 쓸 수 없다HashMap장르를 키로 쓰는 Map이 두 개 필요하다. 하나는 장르 순서를 ..

쓰인 문제: 완주하지 못한 선수 · 의상 선언default V getOrDefault(Object key, V defaultValue)Java 8에서 Map 인터페이스에 default 메서드로 추가됐다. HashMap, TreeMap, LinkedHashMap 등 모든 Map 구현체에서 쓸 수 있다.인자의미key찾을 키defaultValue키가 없을 때 대신 돌려줄 값키가 있으면 저장된 값을, 없으면 defaultValue를 반환한다. 동작Map map = new HashMap();map.put("headgear", 2);map.getOrDefault("headgear", 0); // 2 — 있으니까 저장된 값map.getOrDefault("eyewear", 0); // 0 — 없으니까 ..

연습 문제: 폰켓몬 · 완주하지 못한 선수 · 전화번호 목록 · 의상 해시란키를 넣으면 값이 저장된 위치를 바로 계산해서 찾아가는 자료구조다.배열은 인덱스(0, 1, 2…)를 알면 바로 꺼낼 수 있다. 하지만 "leo" 같은 문자열로는 배열 위치를 알 수 없다. 해시는 키를 해시 함수에 넣어 숫자(해시값)로 바꾸고, 그 숫자로 배열 위치(버킷)를 정한다."leo" → hashCode() → 107030 → 버킷 7"kiki" → hashCode() → 3291964 → 버킷 14"eden" → hashCode() → 3108232 → 버킷 7 (leo와 충돌)버킷 수가 16일 때 Java HashMap은 (h ^ (h >>> 16)) & 15 로 위치를 정한다. 해시값의 상위 비트를 하위 비트에 섞..

문제: https://school.programmers.co.kr/learn/courses/30/lessons/42578유형: 해시풀이 저장소: GitHub 문제 요약옷 목록이 [이름, 종류] 쌍으로 주어진다. 종류마다 최대 한 개씩 입고, 최소 한 개는 입어야 할 때 서로 다른 조합의 수를 구한다. 왜 해시일까?문제에서 본 부분신호그래서종류별로 최대 한 가지만 입는다종류별로 묶는다종류를 키로서로 다른 조합의 수를 구한다조합 목록이 아니라 개수를 묻는다종류별 옷 개수만 있으면 된다 → 값에 개수종류가 "headgear", "eyewear" 같은 문자열배열 인덱스로 쓸 수 없고 무엇이 나올지 모른다HashMap"~별 개수"는 해시의 대표 신호다. 이 문제는 입력이 30개로 작아서 속도보다는 종류별로 묶어 ..

문제: https://school.programmers.co.kr/learn/courses/30/lessons/42577유형: 해시풀이 저장소: GitHub 문제 요약전화번호 목록에서 어떤 번호가 다른 번호의 접두어인 경우가 있으면 false, 없으면 true를 반환한다. 왜 해시일까?문제에서 본 부분신호그래서접두어인 경우가 있으면 false, 없으면 true있다/없다만 묻는다개수는 필요 없다 → 값 없는 HashSetphone_book 길이 1 이상 1,000,000 이하입력이 매우 크다번호끼리 모두 비교하면 O(N²), 약 1조 번전화번호 길이 1 이상 20 이하번호가 짧다한 번호를 잘라서 물어보는 횟수는 최대 19번세 번째 줄이 풀이의 열쇠다. 번호끼리 비교하는 대신, 번호를 잘라서 그 조각이 목록..

문제: https://school.programmers.co.kr/learn/courses/30/lessons/42576유형: 해시풀이 저장소: GitHub 문제 요약마라톤 참가자 명단과 완주자 명단이 주어진다. 완주하지 못한 단 한 명의 이름을 구한다. 왜 해시일까?문제를 처음 읽을 때 세 군데를 본다.문제에서 본 부분신호그래서완주자 명단에 없는 참가자를 찾는다이름(값)으로 찾는다이름을 키로 바로 찾는 구조가 필요"참가자 중에는 동명이인이 있을 수 있습니다."개수를 세야 한다있다/없다(Set)로는 부족, 값에 사람 수(Map)"마라톤 경기에 참여한 선수의 수는 1명 이상 100,000명 이하입니다."입력이 크다이름마다 명단을 처음부터 찾으면 O(N²), 약 100억 번값으로 찾고, 개수를 세고, N이 ..

문제: https://school.programmers.co.kr/learn/courses/30/lessons/1845유형: 해시풀이 코드: GitHub문제 요약N마리 중 N/2마리를 고를 때, 고른 폰켓몬의 종류 수가 최대 몇인지 구한다.(고르는 방법의 수가 아니라, 고른 것 안의 종류 수)접근답의 상한이 두 개 있다.뽑는 수 N/2 — 3마리를 고르면 모두 달라도 3종류를 넘을 수 없다.전체 종류 수 — 2종류밖에 없으면 몇 마리를 골라도 2종류를 넘을 수 없다.둘 중 작은 값이 답이다.답 = min(N/2, 종류 수) 입력N/2종류 수답[3,1,2,3]232[3,3,3,2,2,4]333[3,3,3,2,2,2]322종류 수는 HashSet에 모두 넣고 size()로 구한다. 중복은 Set이 걸러준다..

회사에서 최근에 아키텍처 개선 및 프로젝트를 리빌딩 하면서 API 규격을 설계하는 작업을 맡았다. 이 작업에 도움이 될까 하여 '자바 API 디자인'이라는 책을 읽기로 결심했고,도움이 될만한 무장들을 기록해본다. 1장. 현대 소프트웨어 구축의 예술내가 생각했을 때 1장의 핵심은 다음과 같다.'왜'라는 것의 의미개인적으로 '왜'라는 질문을 아주 좋아한다.회사에서 어떤 일을 하라고 업무를 받았을 때 '왜 이걸 개발해야하나요?' 라고 질문하곤한다.혹자는 이 '왜'라는 질문을 '하기싫다'는 의미로 받아들이는 분들도 있던데내가 이 질문을 하는 이유는 사실언제 이 API가 필요한지,무엇을 위해 이 API가 필요한지 파악해어떻게 더 잘 만들것인가를 파악하기 위해서다.결국 이 책은 API 설계 및 디자인에 관한 책..