내가 그린 코딩 그림

문제요약) - 시작단어, 타겟단어가 주어짐 - 주어지는 단어리스트를 통해 시작단어부터 타겟단어까지 변환시키기 - 한번에 한 글자만 바꿀 수 있음 주의점) - DFS를 쓴다면 단어 사용후 백트래킹 할 때 사용한 단어 초기화 - BFS를 쓰는 경우 최단 거리만 찾으면 되기에 크게 중요x 풀이) dfs, bfs 둘 다 괜찮게 사용이 가능한 문제입니다. 다만, 최단 거리를 구하는 문제인 만큼 웬만해서는 bfs를 쓰는게 효율성은 더 잘나오게 됩니다. 1. DFS -> boolean배열 혹은 HashMap을 통해 사용한 단어 구분 -> 사용한 단어가 아니고, 다음단어로 갈 수 있는 단어면 DFS이어서 진행 -> 사용한 단어 표기 해제 package programmers.kit.dfsbfs; import java.u..

테스트 케이스는 맨 아래에 있습니다. 문제요약) - 주어진 맵에서 최단거리(칸 수) 리턴 주의점) - 맵은 n * m 으로 이루어져 있고 서로 다를 수 있음 풀이) 1. 최단거리를 찾기에 BFS로 접근 2. 거리를 판단해야 하기에 주어진 map과 같은 visit 배열을 만들어서 거리를 표기 3. 4방향 탐색을 하면서 q에 넣는데 맵을 벗어나지 않게 처리, 이미 방문한곳을 안가게 처리 4. n과 m의 범위를 주의해야합니다. 저의 경우 이 부분을 헷갈려 시간을 낭비했습니다. 정답코드) import java.util.*; public class gameMinDistance { // 각 4방향을 보기 위한 dx, dy static int[] dx = {0, 1, 0, -1}; static int[] dy = {..

문제요약) - 던전 출입에 필요한 피로도, 클리어시 소모되는 피로도 주어짐 - 최대한 많은 던전 돌았을때의 클리어 던전수 리턴 주의점) - X 풀이방법) 1. 모든 던전 케이스를 확인해야해서 DFS로 완전탐색 2. 이미 돈 던전은 전역으로 방문 배열 잡기 3. 방문배열, 피로도 등 확인해서 던전 돌 수 있는지 판단 4. 뎁스를 answer에 저장 DFS를 통해 완전탐색을 해야하는 유형이 문제인데 풀이가 바로 떠오르지 않아서 던전이 A, B, C 총 3개인 경우로 생각하고 재귀로 들어가는 과정을 그림을 그려보았습니다. public class Fatigue { static boolean[] visited; static int answer = 0; static boolean flag; public static..

문제요약) - 작업의 요청시기, 작업 소요시간으로 날라옴 - 각 작업이 요청부터 작업 끝까지 걸린시간 평균 리턴 풀이방법) 우선 순위큐를 사용 1. 각각 요청온 순서대로 job 정렬, 빨리 끝나는 순서대로 우선순위큐 정렬 2. 만약, 요청 처리가 가능한 시간이면 빨리 끝나는 작업부터 시행해서 대기시간 최소화 3. 만약, 앞 작업이 끝나고 뒷작업 요청 시간이 아직 남았을 경우 실행대기를 한게 아니므로 해당 시간은 제외해서 계산 위 사진에서를 예시로 들면 실제 기다린 시간 + 실제 실행 시간만 계산해야한다.

프로그래머스 고득점 kit 해시 카테고리의 레벨 3 문제 "베스트앨범" 이라는 문제입니다. 문제요약) - 장르, 재생횟수가 주어짐 - 인기 있는 장르, 재생횟수, 인덱스 순서대로 분류해서 리턴 주의점) - 특정 장르의 모든 재생횟수를 더해서 가장 인기있는 장르 순서를 파악 - 한 장르에서 최대2곡만 선정해서 정답배열에 담아야함 풀이방법) 1. 특정 장르를 계산 -> HashMap활용해서 재생횟수를 더함 2. 인기있는 장르부터 선별하기 위해 내림차순 정렬이 필요하기에 List정의, 람다식을 활용해 재생횟수 기준으로 내림차순 정렬 3. List의 key값 순서대로 최대 두 곡을 뽑아서 정답배열에 분배 특정 장르에서 재생횟수가 많은 부분을 찾는건 조금 더 좋은 코드로 쓸 수 있을 것 같습니다. 코드의 중복 제..

프로그래머스 고득점 Kit 해시 분류의 "의상" 이라는 문제입니다. 문제요약) - 여러 종류의 의상이 주어짐 - 매일 다른 옷을 입는 경우의 수 리턴 주의점) - 옷을 하나라도 입으면 인정 풀이 방법) - 종류별로 옷의 개수 + 해당 종류의 옷을 안입는 경우를 계산해서 다른 옷의 종류와 곱 정답 코드) 경우의 수만 헷갈리지 않고 계산해준다면 큰 어려움 없이 풀 수 있는 문제 같습니다.

프로그래머스 고득점 Kit 해시 분류의 "전화번호 목록"이라는 문제입니다. 문제요약) - 전화번호 여러개가 주어짐 - 그 중 어떤 전화번호가 다른 전화번호의 접두사면 false, 아니면 true 리턴 주의점) - 시간복잡도 고려(phone_book의 길이가 100만이어서 O(n2)시 시간초과 위험) - 포함여부가 아닌, "접두사" 여부 판단 풀이 방법) 1. 단순 무식하게 for문 두번 돌리면서 비교 O(n2). -> 2022년까지 되던 방법이었으나 현재 효율성 기준을 보완한것으로 보임. 이 방법으로 진행 시 효율성 테스트 통과x 2. 문자열 정렬 특성을 활용해서 정렬 후 해시값 비교 1번 방법은 사실 잠깐이라도 되었던게 이상할 정도의 문제로 보입니다. 2번으로 풀이하시면 되겠습니다. 정답 코드) 여기서..

프로그래머스 고득점 Kit 폰켓몬이라는 문제는 위와 같습니다. 문제요약) - 여러 종류의 폰켓몬이 존재 - 총 폰켓몬 수의 절반만큼 가져올 수 있음 - 가져올 수 있는 최대 종류의 폰켓몬을 반환 주의점) - 없음 풀이 방법) 1. 폰켓몬의 종류를 HashMap에 저장 2. 몇마리이든 종류를 반환하기 때문에 같은 종류의 수는 무관 정답 코드)

완주하지 못한 선수라는 문제는 위와 같습니다. 문제 요약) - 선수 명단이 주어진다. - 완주자 명단이 주어진다. - 완주하지 못한 선수 이름을 반환하는 함수 작성 주의점) - 동명이인이 있을 수 있다. 풀이 방법) 1. HashMap에 각 선수 저장 2. 동명이인이 존재하기 때문에 true, false 등으로 단순 구분이 아닌 인원을 판단해야하기에 HashMap형태로 선언 3. 완주하지 못한 선수 반환 정답 코드)