본문 바로가기

알고리즘 풀이

 (84)
[백준] 1800번: 인터넷 설치 - JAVA 🔗 문제 링크 BOJ 1800번: 인터넷 설치 1800번: 인터넷 설치 첫 번째 줄에 N(1 ≤ N ≤ 1,000), 케이블선의 개수 P(1 ≤ P ≤ 10,000), 공짜로 제공하는 케이블선의 개수 K(0 ≤ K < N)이 주어진다. 다음 P개의 줄에는 케이블이 연결하는 두 컴퓨터 번호와 그 가격이 차 www.acmicpc.net 📝 풀이 과정 처음에는 방문할 때마다 가격을 저장하고 해당 가격순으로 정렬하여 K개만큼 제외하는 등의 작업이 굉장히 오래걸렸기 때문에 당연하게도 시간초과가 발생했다... 계속 고민하며 아이디어가 떠오르지 않아 고생하던 중 한가지 힌트를 보게 되었다. 최소값을 미리 정한 뒤 탐색을 하라는 것이었다. 최소값을 x로 두고 가격이 x이하인 선은 그냥 연결을 하고, x이상인 선은 K개..
[프로그래머스] 방금그곡 / 2018 KAKAO BLIND RECRUITMENT(3차) - JAVA 🔗 문제 링크 [프로그래머스] 방금그곡 / 2018 KAKAO BLIND RECRUITMENT(3차) 코딩테스트 연습 - [3차] 방금그곡 방금그곡 라디오를 자주 듣는 네오는 라디오에서 방금 나왔던 음악이 무슨 음악인지 궁금해질 때가 많다. 그럴 때 네오는 다음 포털의 '방금그곡' 서비스를 이용하곤 한다. 방금그곡에서는 TV, programmers.co.kr 📝 풀이 과정 주어진 멜로디를 포함하는 악보를 가진 음악을 구하는 문제이다. 문제에서 중요한 점은 C와 C#은 다르기 때문에 #이 붙어있는 음을 바꿔주어야 문자열을 찾게 될 때 오류가 없어지게 된다. 주어진 문자열에서 변환음을 모두 바꾸어 반환해주는 changeStr(str) 함수를 만들어 사용하였다. 음악은 재생된 시간만큼 멜로디가 구성되는데, 만..
[프로그래머스] 캐시 / 2018 KAKAO BLIND RECRUITMENT(1차) - JAVA 🔗 문제 링크 [프로그래머스] 캐시 / 2018 KAKAO BLIND RECRUITMENT(1차) 코딩테스트 연습 - [1차] 캐시 3 [Jeju, Pangyo, Seoul, NewYork, LA, Jeju, Pangyo, Seoul, NewYork, LA] 50 3 [Jeju, Pangyo, Seoul, Jeju, Pangyo, Seoul, Jeju, Pangyo, Seoul] 21 2 [Jeju, Pangyo, Seoul, NewYork, LA, SanFrancisco, Seoul, Rome, Paris, Jeju, NewYork, Rome] 60 5 [Jeju, Pangyo, S programmers.co.kr 📝 풀이 과정 가장 최근 참조하지 않은 것을 교체하는 LRU 알고리즘을 구현해보는 문제이..
[프로그래머스] 프렌즈4블록 / 2018 KAKAO BLIND RECRUITMENT(1차) - JAVA 🔗 문제 링크 [프로그래머스] 프렌즈4블록 / 2018 KAKAO BLIND RECRUITMENT(1차) 코딩테스트 연습 - [1차] 프렌즈4블록 프렌즈4블록 블라인드 공채를 통과한 신입 사원 라이언은 신규 게임 개발 업무를 맡게 되었다. 이번에 출시할 게임 제목은 프렌즈4블록. 같은 모양의 카카오프렌즈 블록이 2×2 형태로 4개가 붙 programmers.co.kr 📝 풀이 과정 입력은 String 배열로 들어왔지만 코드의 편의성을 위해 char형의 이중 배열로 변경하였다 블록을 좌상단부터 시작해 탐색하며 좌우, 좌하, 우하의 칸이 모두 자신의 칸과 동일하면 제거하기 위한 nextBlock에 .으로 값을 변경하여 찍어주었다. 이후, 모두 제거가 된 블럭들로 생긴 빈칸을 채우기 위해 반복문을 통해 탐색..
[프로그래머스] 뉴스 클러스터링 / 2018 KAKAO BLIND RECRUITMENT(1차) - JAVA 🔗 문제 링크 [프로그래머스] 뉴스 클러스터링 / 2018 KAKAO BLIND RECRUITMENT(1차) 코딩테스트 연습 - [1차] 뉴스 클러스터링 뉴스 클러스터링 여러 언론사에서 쏟아지는 뉴스, 특히 속보성 뉴스를 보면 비슷비슷한 제목의 기사가 많아 정작 필요한 기사를 찾기가 어렵다. Daum 뉴스의 개발 업무를 맡게 된 신입사원 튜브 programmers.co.kr 📝 풀이 과정 집합을 만들어 교집합과 합집합을 조사해야 하는데, 같은 원소가 여러번 등장할 수 있고 자주 찾아 반환해주어야 하기 때문에 HashMap 자료구조를 사용하기로 했다. 집합에 대소문자 구분은 없으므로 String.toLowerCase()를 사용해 모든 문자열을 소문자로 변경해주었다. 첫번째 문자열을 모두 끊어 Map에 넣어..
[백준] 5639번: 이진 검색 트리 - JAVA 🔗 문제 링크 BOJ 5639번: 이진 검색 트리 1️⃣ 트리 직접 그리기 📝 풀이 과정 전위 순회의 경우 처음 탐색한 값이 항상 root이기 때문에 먼저 처음 값을 root로 설정해 주었다. 이후 반복문을 돌며 Node에 insert함수를 구현해 현재 노드의 값보다 작으면 왼쪽 자식, 크면 오른쪽 자식으로 넘어가 null일 경우 해당 노드를 생성해주고 아니라면 재귀적으로 다시 탐색하는 방식으로 구현해주었다. 트리가 모두 완성되면 후위 순회 함수를 구현해 왼쪽 자식, 오른쪽 자식, 현재 노드 순으로 탐색해 출력해 주었다. 💻 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; publi..
[백준] 2638번: 치즈 - JAVA 🔗 문제 링크 BOJ 2638번:치즈 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5≤N, M≤100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 표 www.acmicpc.net 📝 풀이 과정 문제에서 외부 공기라는 개념이 존재하기 때문에, 가장자리는 항상 공기이므로 먼저 [0, 0]에서부터 BFS를 통해 0인 칸은 모두 10으로 변경해주었다. 이후 반복문을 돌며 치즈 칸에서 상하좌우 칸의 합이 20이상일 경우 외부 공기가 2칸 이상 존재한다는 것을 의미하므로 외부 공기로 변화시키는 BFS를 위한 Queue에 삽입한다. 반복문을 돌며 Queue 내부에 있는 값들을 10으로 변경하고 접촉한 공..
[프로그래머스] 기능개발 - JAVA 🔗 문제 링크 [프로그래머스] 기능개발 코딩테스트 연습 - 기능개발 프로그래머스 팀에서는 기능 개선 작업을 수행 중입니다. 각 기능은 진도가 100%일 때 서비스에 반영할 수 있습니다. 또, 각 기능의 개발속도는 모두 다르기 때문에 뒤에 있는 기능이 앞에 있는 programmers.co.kr 📝 풀이 과정 각 기능은 정해진 순서대로만 배포가 가능하기 때문에 현재 기능이 완료됐다고하더라도 앞의 기능이 완료되지 않으면 배포가 불가능하다. 따라서 입력 순서대로 반환하는 Queue를 사용하였다. for (int i = 0; i < progresses.length; i++) queue.add((int) (Math.ceil((100.0 - progresses[i]) / speeds[i]))); 기능구현이 완료되는 ..

티스토리툴바