본문 바로가기

알고리즘 풀이/프로그래머스

 (36)
[프로그래머스] 가사 검색 / 2020 KAKAO BLIND RECRUITMENT - JAVA 🔗 문제 링크 [프로그래머스] 가사 검색 / 2020 KAKAO BLIND RECRUITMENT 코딩테스트 연습 - 가사 검색 programmers.co.kr 1️⃣ Trie 📝 풀이 과정 words의 길이는 100,000개, queries의 길이는 100,000개로 단순 탐색시 시간 초과가 발생한다. 다음으로 생각한 풀이는 Trie를 사용하는 방법이었다. words를 모두 Trie에 insert한 다음 queries를 통해 문자열을 검색할 때, 삽입된 문자열의 길이를 모른다면 탐색하기 어렵다. 때문에, Trie의 노드마다 lenMap을 생성하였다. key는 삽입된 문자열의 길이고, value는 해당 길이의 문자열의 개수를 가지고 있다. 따라서 Trie의 node 위치에 도달했을 때, 해당 노드까지 도달..
[프로그래머스] 자물쇠와 열쇠 / 2020 KAKAO BLIND RECRUITMENT - JAVA 🔗 문제 링크 [프로그래머스] 자물쇠와 열쇠 / 2020 KAKAO BLIND RECRUITMENT 코딩테스트 연습 - 자물쇠와 열쇠 [[0, 0, 0], [1, 0, 0], [0, 1, 1]] [[1, 1, 1], [1, 1, 0], [1, 0, 1]] true programmers.co.kr 📝 풀이 과정 열쇠를 자물쇠에 맞게 움직이며 비교하면서 답을 찾는 문제이다. 열쇠는 자물쇠를 벗어나게 대볼 수 있기 때문에 자물쇠를 기준으로 -M ~ +N까지의 범위로 비교해볼 수 있다. 만약 자물쇠가 모두 1(돌기)인경우까지 생각해 열쇠를 아예 벗어나게 대보는 경우도 고려했다. 함수에 y, x를 전달하고 해당 범위만큼 열쇠를 자물쇠에 대보는 연산을 수행한다. 예를 들어 (-2, -1)만큼 벗어나게 대본다고 가정..
[프로그래머스] 괄호 변환 / 2020 KAKAO BLIND RECRUITMENT - JAVA 🔗 문제 링크 [프로그래머스] 괄호 변환 / 2020 KAKAO BLIND RECRUITMENT 코딩테스트 연습 - 괄호 변환 카카오에 신입 개발자로 입사한 "콘"은 선배 개발자로부터 개발역량 강화를 위해 다른 개발자가 작성한 소스 코드를 분석하여 문제점을 발견하고 수정하라는 업무 과제를 받았습니다. 소스를 programmers.co.kr 📝 풀이 과정 문제만 이해하면 그대로 구현하면 되는 문제이다. () => 균형잡힌 괄호 문자열(O), 올바른 괄호 문자열(O) )( => 균형잡힌 괄호 문자열(O), 올바른 괄호 문자열(X) )(( => 균형잡힌 괄호 문자열(X), 올바른 괄호 문자열(X) 균형잡힌 괄호로 나눠주기 위해 '('는 +1, ')'는 -1로 계산하며 값이 0이 되면 균형잡힌 괄호로 판단하고 ..
[프로그래머스] 문자열 압축 / 2020 KAKAO BLIND RECRUITMENT - JAVA 🔗 문제 링크 [프로그래머스] 문자열 압축 / 2020 KAKAO BLIND RECRUITMENT 코딩테스트 연습 - 문자열 압축 데이터 처리 전문가가 되고 싶은 "어피치"는 문자열을 압축하는 방법에 대해 공부를 하고 있습니다. 최근에 대량의 데이터 처리를 위한 간단한 비손실 압축 방법에 대해 공부를 하고 있는데, 문 programmers.co.kr 📝 풀이 과정 길이 순으로 실제 압축을 구현해 가장 작은 길이를 반환하는 문제이다. 길이는 1부터 문자열 길이의 절반까지 가능한데, 어차피 문자열의 길이의 절반 이상으로 압축을 시도해도 같은 문자열을 반복할 수 없기 때문이다. 이후, 반복문을 돌며 앞의 문자열과 같은 문자열이라면 cnt를 증가시켜주고 아니라면 반복문을 탈출해 실제 문자열이 아닌 길이만 알면 ..
[프로그래머스] 무지의 먹방 라이브 / 2019 KAKAO BLIND RECRUITMENT - JAVA 🔗 문제 링크 [프로그래머스] 무지의 먹방 라이브 / 2019 KAKAO BLIND RECRUITMENT 코딩테스트 연습 - 무지의 먹방 라이브 programmers.co.kr 📝 풀이 과정 단순 시뮬레이션으로 구현할 수도 있지만 그렇게 하면 효율성을 통과하지 못하기 때문에 아이디어가 필요하다. 5, 2, 10 => 2, 5, 10 2, 5, 10 => 0, 3, 8 => 0, 0, 5 음식의 시간순으로 오름차순 정렬을 하고, 남은 시간을 크기 순으로 한 번에 제거하면 그만큼 시간을 줄일 수 있게 된다. while (idx k) break; k ..
[프로그래머스] 매칭점수 / 2019 KAKAO BLIND RECRUITMENT - JAVA 🔗 문제 링크 [프로그래머스] 매칭점수 / 2019 KAKAO BLIND RECRUITMENT 코딩테스트 연습 - 매칭 점수 매칭 점수 프렌즈 대학교 조교였던 제이지는 허드렛일만 시키는 네오 학과장님의 마수에서 벗어나, 카카오에 입사하게 되었다. 평소에 관심있어하던 검색에 마침 결원이 발생하여, 검색개발팀 programmers.co.kr 📝 풀이 과정 다소 복잡하지만 문제에 주어진 그대로만 구현하면 되는 문제다. 자바에서 정규식 처리를 쉽게 할 수 있도록 만든 Pattern과 Matcher를 사용하여 구현하였다. (참고: [Java] Pattern, Matcher Class 사용법과 메소드 정리) Pattern urlPattern = Pattern.compile("[\\s\\S]*]*content=\"(..
[프로그래머스] 후보키 / 2019 KAKAO BLIND RECRUITMENT - JAVA 🔗 문제 링크 [프로그래머스] 후보키 / 2019 KAKAO BLIND RECRUITMENT 코딩테스트 연습 - 후보키 [["100","ryan","music","2"],["200","apeach","math","2"],["300","tube","computer","3"],["400","con","computer","4"],["500","muzi","music","3"],["600","apeach","music","2"]] 2 programmers.co.kr 📝 풀이 과정 후보키에서 유일성과 최소성을 만족하는 키를 모두 구해야한다. 따라서 키의 모든 조합을 구해 모든 튜플을 식별할 수 있으면서 최소성을 만족하는지 확인하도록 했다. 조합을 구하는 방법 중 순차적으로 최소성을 만족하는 키가 먼저 등장하기 때..
[프로그래머스] 오픈채팅방 / 2019 KAKAO BLIND RECRUITMENT - JAVA 🔗 문제 링크 [프로그래머스] 오픈채팅방 / 2019 KAKAO BLIND RECRUITMENT 코딩테스트 연습 - 오픈채팅방 오픈채팅방 카카오톡 오픈채팅방에서는 친구가 아닌 사람들과 대화를 할 수 있는데, 본래 닉네임이 아닌 가상의 닉네임을 사용하여 채팅방에 들어갈 수 있다. 신입사원인 김크루는 카카오톡 오 programmers.co.kr 📝 풀이 과정 한 유저는 유저 아이디 하나와 닉네임을 여러 개 가질 수 있고, 제일 마지막으로 지정한 닉네임을 가져야한다. 때문에 유저 아이디를 Key로 가지면서 닉네임을 Value 값으로 갖는 Map을 만들어주었다. 반복문을 돌며 새로 들어오거나 닉네임을 변경할 때마다 Map에 put을 해주면 자동으로 값이 덮어씌워지기 때문에 별도의 처리를 하지않고 넣어주었다. 모..

티스토리툴바