네발로 코딩하는 포메라니안

1. 문제 https://school.programmers.co.kr/learn/courses/30/lessons/72412 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 2. 풀이 과정 처음엔 시간 계산안하고 풀어서 효율성에서 딱걸렸다. (info의 크기) x (query의 크기)는 50억으로 2중 반복문 도는 순간 무조건 효율성에서 걸린다. 따라서 메모리를 좀 더 쓰더라도 (info의 크기) + (query의 크기)가 되도록 해야한다. 구체적인 프로세스는 아래와 같다. 1) info를 돌면서, 모든 가능한 경우를 Key값으로, 점수를 Value로 한다..

문제 https://www.acmicpc.net/problem/20291 20291번: 파일 정리 친구로부터 노트북을 중고로 산 스브러스는 노트북을 켜자마자 경악할 수밖에 없었다. 바탕화면에 온갖 파일들이 정리도 안 된 채 가득했기 때문이다. 그리고 화면의 구석에서 친구의 메시지를 www.acmicpc.net 풀이 과정 TreeMap은 내부적으로 레드-블랙 트리 구조를 갖추고 있어, 정렬한 자료가 필요할 때 유용하다. 따로 key를 복사해서 정렬하지 않고, 값을 넣으면서 Entry자체를 정렬하는 것이다. import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Map; import java.util.TreeMap; ..

문제 https://www.acmicpc.net/problem/21609 21609번: 상어 중학교 상어 중학교의 코딩 동아리에서 게임을 만들었다. 이 게임은 크기가 N×N인 격자에서 진행되고, 초기에 격자의 모든 칸에는 블록이 하나씩 들어있고, 블록은 검은색 블록, 무지개 블록, 일반 블록 www.acmicpc.net 풀이 과정 가장 왼쪽, 위쪽에서 출발해서 일반 블럭일 때만 DFS 탐색을 하면, 일반블럭이 무조건 1개 이상인 조건을 만족한다. 탐색 후, (블럭 사이즈가 최대) || (이전 블럭 사이즈와 같고 rainbow블럭의 개수가 같거나 큼)일 때, 가장 큰 블럭 값을 갱신해준다. 가장 큰 블럭은 삭제하면서 -2로 표시한다. import java.io.BufferedReader; import ja..

문제 https://www.acmicpc.net/problem/1309 1309번: 동물원 첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다. www.acmicpc.net 풀이 과정 dp[i] = (dp[i-1][x] + dp[i-1][1] + dp[i-1][2]) + (dp[i-1][x] + dp[i-1][2]) + (dp[i-1][x] + dp[i-1][1]) = dp[i-1]*2 + dp[i-1][x] = dp[i-1]*2 + dp[i-2] import java.io.BufferedReader; import java.io.InputStreamReader; public class Main { public static void main(String[] args) throws Exception..

문제 https://www.acmicpc.net/problem/11048 11048번: 이동하기 준규는 N×M 크기의 미로에 갇혀있다. 미로는 1×1크기의 방으로 나누어져 있고, 각 방에는 사탕이 놓여져 있다. 미로의 가장 왼쪽 윗 방은 (1, 1)이고, 가장 오른쪽 아랫 방은 (N, M)이다. 준규는 www.acmicpc.net 풀이 과정 처음엔, 3방향 다 Math.max로 고려해줬었다. 하지만, 최단 거리가 아니기 때문에, 대각선에서 오는 것보다 위 혹은 왼쪽을 거쳐 오는 것이 총 사탕 개수가 같거나 큰 경로이므로 대각선은 고려하지 않는 것이 효율적이다. import java.io.BufferedReader; import java.io.InputStreamReader; import java.util..

문제 https://www.acmicpc.net/problem/12851 12851번: 숨바꼭질 2 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 풀이 과정 BFS를 떠올리기는 쉬웠는데 K까지 도달하는 개수를 어떻게 셀 지에 대해서 생각하기가 어려웠다. 방문체크를 q에서 꺼낼 때함으로써, 현재 step에서는 중복을 허용하되 다음 step에서는 이전에 방문한 것을 제외하고 방문하도록 할 수 있었다. import java.io.BufferedReader; import java.io.InputStream..

문제 https://school.programmers.co.kr/learn/courses/30/lessons/84021 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 과정 1. BFS 탐색으로 퍼즐(remove를 쓰기 위해 LinkedList를 사용)과 빈 칸을 각각 분석한다. 1-1. 블럭의 가장 위쪽에서 가장 왼쪽에 있는 블럭을 (0, 0)으로 맞추어 블럭들의 좌표를 변경한다. - setCenter메서드 2. 각 빈칸에 퍼즐을 넣을 수 있는 지 검사한다. 2-1. 개수가 다르면 return false; 2-2. 개수가 같으면 회전시켜가면서 넣을 ..

문제 https://www.acmicpc.net/problem/17070 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net 풀이 과정 처음에, 어차피 왼쪽에서 오른쪽, 위에서 아래로만 움직일 수 있기 때문에 2중 반복문으로 풀 수 있을 것 같았다. 하지만, 방향까지 고려해야 돼서 생각하다가 DFS로 풀었다. 다 풀고나서, 고민하다가 방향마다 따라 결과를 저장해가면 2중 반복문으로 풀 수 있을 것 같아서 다시 풀었다. 결과적으로 속도가 2배 향상되었다. 이전 코드 : DFS import j..

문제 https://school.programmers.co.kr/learn/courses/30/lessons/84512 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 과정 처음엔 AEIOU 순서대로 DFS방식을 통해 사전순대로 읽어가면서 해당 문자열을 만나면 return하는 방식이 떠올랐다. 그런데, 굳이 순서대로 다 탐색하는 것보다 몇 번째인지 바로 계산할 수 있는 방식이 있어서 이 방식으로 구현했다. 원래는 O(N)만큼 걸리는 알고리즘을 O(1)으로 구현할 수 있는 것이다. 수식 : 5^(length("AEIOU")-1-i) + sum(1*5^(..

문제 https://www.acmicpc.net/problem/2531 2531번: 회전 초밥 첫 번째 줄에는 회전 초밥 벨트에 놓인 접시의 수 N, 초밥의 가짓수 d, 연속해서 먹는 접시의 수 k, 쿠폰 번호 c가 각각 하나의 빈 칸을 사이에 두고 주어진다. 단, 2 ≤ N ≤ 30,000, 2 ≤ d ≤ 3,000, 2 ≤ www.acmicpc.net 풀이과정 각 번호별로 먹은 횟수를 1차원 배열에 기록했다. 여기서 인덱스는 음식의 번호를 의미한다. 이 문제에서는 K개라는 window크기가 정해져있으므로 window를 한칸씩 오른쪽으로 움직여가며 값을 계산했다. window가 옮겨질 때는 window맨 첫번째 수를 빼주고 다음 수를 하나 더해주는 방식으로 진행한다. import java.io.Buff..