프로그래머스13 [JAVA] 프로그래머스 - 단체사진 찍기 ( 카카오 코드 2017 본선 ) 문제를 처음에 잘못이해해서 왜 3648 가지가 나오는지 고민했는데 그냥 단순한 순열 문제였다. # 3648 인 이유 N 과 F 는 이웃하면서 R과 T 사이에 3명이상 사람이 오는 경우의 수를 묻는다. 1) R 과 T사이에 NF포함 3명이 있는 경우 = 4! * 4C1 * 2! * 2! * 2! = 768 2) R 과 T 사이에 NF를 포함하지 않는 3명이 있는 경우 = 3! * 4C3 * 3! * 2! * 2! = 576 3) R 과 T 사이에 NF 포함 4명이 있는 경우 = 3! * 4C2 * 3! * 2! * 2! = 864 4) R과 T사이에 NF를 포함하지 않는 4명이 있는 경우 = 2! * 4! * 2! * 2! = 192 5) R 과 T 사이에 5명 있는 경우 = 2! * 4C3 * 4! * .. 2020. 10. 9. [JAVA] 지형이동 - 프로그래머스 이때까지 배운 알고리즘들을 정리하기 딱 좋은 문제. 난이도가 4인 이유는 아마 구현해야할 양이 많아서 인듯 하다. 1. BFS or DFS 로 그룹 나누기 만약 height 가 3일 때 land가 아래와 같다면 land[3][3] 1 1 13 5 1 12 7 6 11 원하는 결과인 group[3][3] 는 아래와 같다. group의 각 원소는 그룹 번호를 의미한다. 2. 인접리스트 생성하기 인접행렬로 할시 아래 처럼 메모리 초과난다. 인접 리스트의 결과물은 아래처럼 될것이다. 3. 거리가 작은 순으로 정렬하기 새로운 리스트와 클래스를 만들어서 정렬한다. gn 은 다음 그룹번호다. list 는 인접리스트를 말한다. Node 라는 클래스 인데 Node 는 원소로 a,b,d를 가진다. 즉, 그룹번호 a와 그룹.. 2020. 9. 26. [PYTHON] 무지의 먹방 라이브 (프로그래머스 kakao 2019) 미리 스포 -> 이분탐색으로 풀어보기 효율성 때문에 겁부터 먹고 들어 갔다. 아무런 알고리즘 없이 문제에서 설명한 그대로 구현한다면 입출력 예 1번 처럼 k가 5라면 최소 5번은 확인해야한다. 만약 k가 2*10^13 이라면 2*10^13 번 확인해야하므로 시간초과가 난다. 즉, 문제 설명대로 구현하지 말고 "어떠한 아이디어를 떠올려봐라"가 핵심이다. 그래서 프로그래머스에서 lv4를 책정한듯 하다. 이런 문제를 접근하기 위해서 시뮬레이션 해보고 규칙이 있는 지 찾아보는 것이 우선이다. 규칙을 찾기 위해 그냥 문제에서 하라는 대로 해보았다. 먼저 아래의 표를 해석해 보자. (참고로) 임의의 테스트 케이스 food_times = [4,2,3,6,7,1,5,8] k=16 이라고 해보자. 3(1초) 라는 말은 .. 2020. 9. 11. [PYTHON] 매칭 점수(kakao 2019 프로그래머스) 정규 표현식 한번 연습해보려고 선택한 문제다. java 보다는 파이썬이 편한거 같아서 파이썬으로 풀어본다. 또한 정규표현식에서 아래 링크가 많이 도움이 되었다. 사실 이거보고 다 풀었다... https://whatisthenext.tistory.com/116 [파이썬] 정규표현식(regular expression) 정규표현식 정규표현식(Regular Expressions) re 모듈 : 파이썬 정규 표현식을 지원한다. 파이썬에서는 정규 표현식을 지원하기 위해 re(regular expression) 모듈을 제공한다. 자바(JAVA)에서 패턴 객체(p)의 �� whatisthenext.tistory.com 여기서 쓸만하게 챙겨갈것을 따로 한번 정리해 보려고 한다. 먼저 findall은 내가 찾아야 하는 문.. 2020. 9. 10. [JAVA] 소수 찾기 ( 프로그래머스 ) 모든 조합 + 순열을 확인해야하는 문제다. numbers 의 길이가 최대 7개 이므로 최대 경우의 수는 7 + 7*6 + 7*6*5 + 7*6*5*4+7*6*5*4*3 + 7*6*5*4*3*2 + 7*6*5*4*3*2*1 =13699이다. 완전 탐색해도 1초 안에 확인할 수 있는 충분한 경우의 수다. 만약 카드가 1~5까지 5장이 있다고 가정하자. 모든 경우를 탐색하는 DFS를 구현해본다. 아래의 경우의 수는 모든 경우의 수 가지들 중에 일부 가지들이다. 1. 첫번째 자리 ( 모든 한자리 수 검사) 한 자리수의 경우는 1에서 5까지 수 중에서 1가지를 선택할 수 있다. 총 5가지 경우의 수가 있다. 1부터 5까지 숫자를 하나씩 소수인지 아닌지 검사한다. 소수가 맞다면 소수만 모아두는 Set에 넣어둔다. .. 2020. 9. 4. [JAVA] 후보키 (kakao 2019 프로그래머스) 여기서 사용한 모든 기술은 아래 글에 기록하였다. https://onejunu.tistory.com/63 [JAVA] 비트 연산자를 이용하여 조합 & 부분집합 & 부분집합 여부파악 아래 배열을 계속 쓸 것이다. int[] arr = new int[]{1,2,3}; # 부분 집합 구하기 코드 생각 없이 그냥 부분 집합을 구한다고 하면 어떻게 구할까?? 1 2 3 1,2 1,3 2,3 1,2,3 그렇다면 비트 마스크로 한다면 아래. onejunu.tistory.com import java.util.*; class Solution{ static List ans = new ArrayList(); public int solution(String[][] relation) { int n = relation.lengt.. 2020. 8. 30. [JAVA] 오픈채팅방 (2019 kakao 프로그래머스) 문제의 핵심은 "마지막에 바꾼 닉네임이 진짜 닉네임" 이라는 것이다. 만약 record의 리스트가 아래처럼 주어졌다고 가정하자. ex) record ["Enter id1 A","Enter id2 B","Leave A","Enter id1 B", "Change id2 C"] 그리고 비어있는 HashMap 초기화 한다. 이유는 고유한 아이디마다 하나의 닉네임을 결국에 가지게 될것이기 때문이다. 뒤에서 부터 아이디가 HashMap에 있는지 검색하고 없으면 추가한다. record 의 크기가 5이므로 뒤에서 부터 총 5번의 과정에서 HashMap이 어떻게 변화하는지 보자. 1) { "id2":"C" } 2) {"id1":"B","id2":"C"} 3) {"id1":"B","id2":"C"} 4) {"id1":"B.. 2020. 8. 25. [JAVA] 가사검색 (kakao 2020 프로그래머스) trie 자료구조로 문제를 푼다. 1) 문자열 저장 만약 "fla","fly","ka" 문자열들을 가진다면 트라이 자료구조는 아래처럼 될 것이다. 2) 길이정보 저장하기 만약 쿼리를 "fro??"로 준다면 fro 로 시작하고 5글자인 모든 문자열의 수를 알아야 한다. 본인은 각 노드마다 문자열들의 수를 저장하는 해시맵을 각각의 노드마다 추가했다. 1)에서의 정보를 바탕으로 자료구조를 수정하면 다음과 같다. (x:y) 의 의미는 x길이의 문자열의 수는 y 다. 즉, (3:2) 는 길이가 3인 문자열의 수가 2개 있다는 뜻이다. 문제) 쿼리가 "fl?"로 왔다면 답) 파란박스에서 lenHashMap.get(3) "?" 로 시작하는 문자열은 문자열을 거꾸로 만들어서 똑같이 구현하면 된다. import java.. 2020. 8. 24. [JAVA] 기둥과 보 설치( 프로그래머스 kakao 2020 공채) 제약 사항이 너무 많다... 보자마자 빡시게 구현하겠구나 생각했다. 이런 문제 풀 때 가장 중요한 점은 잔머리 굴리면 안된다. 있는 그대로 모든 조건 활용해서 구현해야 한다.. 1) 격자 설정하기 (먼저 2차원 격자를 설정해서 문제를 풀어야 하는데 이 부분에서는 문제 내용을 어떻게 표시할지 본인만의 방법으로 생각해내야 한다.) n x n 격자지만 사실은 0을 포함하고 있기 때문에 길이는 n+1 이다. 기둥을 표시할 격자 gidung 과 보를 표시할 격자 boo 를 boolean 2차원 배열로 설정했다. 한편 문제에서 주어진 대로 (1,0) 이라는 좌표에 대해 생각해보자. (1,0) 을 좌표 그대로 생각하면 x좌표가 1 이며 y좌표가 0 인점이 떠오를 것이다. 하지만, 이를 2차원 컴퓨터 배열로 생각하면 .. 2020. 8. 21. 이전 1 2 다음
