본문 바로가기

algorithm68

[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] 2048(Easy) 삼성 기출 문제 (백준 12100) 전형적인 구현 문제 상하좌우를 그대로 구현했는데 다른 사람들 풀이 보니까 rotate 를 구현하고 방향 하나만 구현한 것이 많이 보였다.. 이렇게하면 확실히 코드 길이는 줄어 들듯 하다. 내 코드를 보면서 불필요한 부분들이 몇개 발견되었다. 먼저 나의 풀이를 소개한다. 만약 배열의 한줄만 생각한다고 가정하자. [2,2,0,4,4] 의 배열이 있을 때 오른쪽으로 이동하면 [0,0,0,4,8] 왼쪽으로 이동하면 [4,8,0,0,0] 이렇게 될 것이다. 왼쪽으로 이동할 때 어떻게 풀었는지 보자. 똑같은 크기의 0으로 가득차있는 배열 tmp = [0,0,0,0,0] 를 선언및 초기화한다. 그리고 비어있는 Deque 한개를 선언하고 boolean으로 ok =true를 선언하여 이전에 합쳐졌는지 안 합쳐졌는지 체크.. 2020. 9. 1.
[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.
[JAVA] 메모리 사용량과 시간을 줄이는 간단한 아이디어 문제는 백준 2573번 문제로 진행했다. https://www.acmicpc.net/problem/2573 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 � www.acmicpc.net 1. 문제 풀이 1) 2차원 배월의 모든 원소가 0인가? 그렇다면 6)으로 간다. 그게 아니라 하나라도 0보다 큰 수가 있다면 2)번으로간다. 2) answer 를 1증가 시킨다. 3) 2차원 배열을 1년이 지난 배열로 만든다. 4) bfs를 이용해 영역의 수를 카운트하고 2이상이면 ok에 표시하고 6)번으로 간다. 5) 2)반복한다. 6) ok가.. 2020. 8. 20.
[JAVA] 토마토 (백준 7569) 이 문제는 2차원이 아니라 3차원으로 bfs푸는 것이다. 또한 익기 시작하는 지점이 정해진 것도 아니며 여러개가 있을 수도 있고 없을 수도 있다. 관건은 모든 토마토가 익었는지 확인하는 것과 모두 익었다면 며칠이 걸리는지 구하는 것이 핵심이다. 본인이 접근한 방법대로 2층짜리 3x3 토마토상자가 있다고 가정하고 풀어보는 예시를 보자. 예) (z,x,y) 에서 z 는 높이이며 , x 는 가로, y는 세로다. x,y,z 모두 0부터 시작한다. 시작전 ( 0초 ) 큐에 남은 좌표 : (0,1,1) 1층 0 0 0 0 1 0 0 0 0 2층 0 0 0 0 0 0 0 0 0 1초후 큐에 남은 좌표: (0,0,1) , (0,1,0), (0,2,1) , (0,1,2) 1층 0 2 0 2 1 2 0 2 0 2층 0 0.. 2020. 8. 15.

티스토리툴바