Coding 한놈만 팬다

문제링크 문제 설명 주어진 항공권을 모두 이용하여 여행경로를 짜려고 합니다. 항상 "ICN" 공항에서 출발합니다. 항공권 정보가 담긴 2차원 배열 tickets가 매개변수로 주어질 때, 방문하는 공항 경로를 배열에 담아 return 하도록 solution 함수를 작성해주세요. 제한사항 모든 공항은 알파벳 대문자 3글자로 이루어집니다. 주어진 공항 수는 3개 이상 10,000개 이하입니다. tickets의 각 행 [a, b]는 a 공항에서 b 공항으로 가는 항공권이 있다는 의미입니다. 주어진 항공권은 모두 사용해야 합니다. 만일 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 return 합니다. 모든 도시를 방문할 수 없는 경우는 주어지지 않습니다. 입출력 예 설명 예제 #1 ["ICN", ..

문제링크 문제 설명 [본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.] 개발자 출신으로 세계 최고의 갑부가 된 어피치는 스트레스를 받을 때면 이를 풀기 위해 오프라인 매장에 쇼핑을 하러 가곤 합니다. 어피치는 쇼핑을 할 때면 매장 진열대의 특정 범위의 물건들을 모두 싹쓸이 구매하는 습관이 있습니다. 어느 날 스트레스를 풀기 위해 보석 매장에 쇼핑을 하러 간 어피치는 이전처럼 진열대의 특정 범위의 보석을 모두 구매하되 특별히 아래 목적을 달성하고 싶었습니다. 진열된 모든 종류의 보석을 적어도 1개 이상 포함하는 가장 짧은 구간을 찾아서 구매 예를 들어 아래 진열대는 4종류의 보석(RUBY, DIA, EMERALD, SAPPHIRE) 8개가 진열된 예시입니다. 진열대의 3번부터 7번까지 5개..

문제링크 문제 풀이 과정 결혼식에 초대 가능한 친구는 친구와 그 친구의 친구까지 초대가 가능하다. 이것은 탐색 할 때 깊이가 2까지만 탐색한다는 것을 의미 할 수 있다. 예제 1번 기준으로 그래프로 나타내면 아래와 같다. 1의 기준으로 친구는 2, 3 이 해당 된다. 친구의 친구는 4가 해당 된다. public static void Find(int depth, int start){ if(depth == 2){ return; } for (int i = 0; i < list[start].size(); i++) { int next = list[start].get(i); visited[next] = true; Find(depth + 1, next); } } 재귀호출 탈출 조건을 깊이가 2일때로 해주었다. 근처 ..

문제링크 문제 설명 게임 캐릭터를 4가지 명령어를 통해 움직이려 합니다. 명령어는 다음과 같습니다. U: 위쪽으로 한 칸 가기 D: 아래쪽으로 한 칸 가기 R: 오른쪽으로 한 칸 가기 L: 왼쪽으로 한 칸 가기 캐릭터는 좌표평면의 (0, 0) 위치에서 시작합니다. 좌표평면의 경계는 왼쪽 위(-5, 5), 왼쪽 아래(-5, -5), 오른쪽 위(5, 5), 오른쪽 아래(5, -5)로 이루어져 있습니다. 예를 들어, "ULURRDLLU"로 명령했다면 1번 명령어부터 7번 명령어까지 다음과 같이 움직입니다. 8번 명령어부터 9번 명령어까지 다음과 같이 움직입니다. 이때, 우리는 게임 캐릭터가 지나간 길 중 캐릭터가 처음 걸어본 길의 길이를 구하려고 합니다. 예를 들어 위의 예시에서 게임 캐릭터가 움직인 길이는 ..

문제링크 문제 풀이 과정 투포인터를 이용하면 간단하게 해결되는 문제이다. 부분 수열의 합이 중복 되면 안되므로 부분수열의 합을 HashSet 에 저장하여 나중에 HashSet 의 size 를 출력하면 부분 수열의 합의 수가 출력이 된다. HashSet sumSet = new HashSet(); for(int item : elements){ sumSet.add(item); } 부분 수열의 길이가 1인 경우는 배열 원소가 해당 되므로 우선 배열 원소 각각을 set 에 넣어 주었다. 부분 수열의 길이가 2일때 초기 start 와 end 를 start 는 0, end 는 start + i(간격) 으로 지정해준다. start 부터 end 까지의 합을 sum 에다 저장해둔다. 그다음 부분수열로 움직일때 sum 에서..

문제링크 문제 풀이 과정 이 문제의 핵심은 LRU 알고리즘을 이용하는 것인데, LRU 알고리즘을 사전에 알고 있으면 쉽게 해결 되는 문제이다. 첫번째 예제를 이용하자면 캐시의 사이즈가 3이므로 3개의 도시까지 캐시에 들어 올 수 있다. 도시배열을 보면 3번째까지 도시가 겹치는 것이 없으므로 3개의 도시가 캐시 미스 되어 캐시에 들어 오게 된다. 그 다음 도시인 NewYork 은 기존 캐시에 없었으므로 캐시 미스가 발생 하게 된다. 이때 캐시 사이즈는 3이므로 LRU 알고리즘에 의해서 제일 처음에 사용했던 캐시 부분이 삭제된다. 만약 캐시에 넣을 데이터가 캐시에 존재 하고 있다면 캐시 히트가 발생 하여 기존 캐시에 있던 데이터를 삭제 할 필요가 없어진다. 전체코드

문제링크 문제 풀이 과정 보석을 가방에 넣는 로직에서 보석이 중복으로 들어가지 않는 것에 대해 오래 고민을 한 문제이다. 우선 보석의 무게와 비용을 한번에 담기 위해서 Item 클래스를 만들었다. static class Item implements Comparable{ int idx; int weight; int cost; public Item(int idx, int weight, int cost) { this.idx = idx; this.weight = weight; this.cost = cost; } @Override public int compareTo(Item o) { if(this.weight == o.weight){ return o.cost - this.cost; } return this.we..

문제링크 문제 풀이 과정 플로이드-워셜 알고리즘을 학습 할 수 있는 기본적인 문제라고 생각한다. 플로이드-워셜 알고리즘을 그대로 사용하여 문제를 해결하였다. 다만 제출 할때 항상 98% 에서 틀렸습니다가 나와서 의문이였다. 알고보니 MAX 값으로 잡았던 값이 작아서 문제가 되었다. 여기서 MAX 값을 Integer.MAX_VALUE 로 잡으면 오버플로워가 발생하게 된다. 전체 코드

문제링크 문제 풀이 과정 문자열 일부분에 PPAP 가 있을 때 이 문자열을 P 로 치환을 하여 마지막에 문자열 P 하나만 남아 있다면 이 문자열은 PPAP 문자열이다. 처음에는 이 문제를 문자열을 배열로 변환한 뒤 스택을 이용하여 풀었더니 시간초과가 되었다. 문자열을 배열로 변환하지 않고 문자열의 인덱스를 이용하여 문제를 풀었더니 해결되었다. 문자열에서 P 가 나오면 P 의 갯수를 카운트를 해준다. 이것을 A 가 나올때까지 카운트 해준다. A 가 나왔을 때 P 의 갯수가 2개 이상이며, 다음 문자열이 P 일때만 PPAP 문자열이 되므로, P 의 수를 한개 줄여주고 문자열의 인덱스를 증가시킨다. 여기서 P 의 갯수를 한개 줄이는 PPAP 는 다시 P 로 치환되기때문에 다시 P 가 추가 된다. 결국 -2 +..

문제 링크 문제 풀이 과정 이 문제는 탐색을 통해서 해결해한다. 다이나믹 프로그래밍으로 해결 하기위해서는 우선 dp 용 배열을 하나 만들어 둔다. 탐색 할때 첫번째 행과 열일 때는 별도의 탐색을 하지 않는다 첫번째 열과 행이 아니면서 1일때는 현재 기준으로 위, 왼쪽, 왼쪽 대각선의 값을 확인 해봐야한다. 그 중에서 최소값에다가 + 1을 한 값이 사각형의 크기가 된다. (1, 1) 인 경우에는 현재값이 1이라 위, 왼쪽, 왼쪽 대각선의 값을 비교해야한다. 이 세개의 최소 값은 0 이고 이 값에 + 1한 값은 1이 된다. (2, 2) 일때는 위, 왼쪽, 왼쪽 대각선의 값의 최솟값이 1이며, 이 값에 + 1 하면 2가 된다. 여기서 나온 2는 이 사각형의 크기가 된다. 전체 코드