파일 합치기 11066번: 파일 합치기 문제 소설가인 김대전은 소설을 여러 장(chapter)으로 나누어 쓰는데, 각 장은 각각 다른 파일에 저장하곤 한다. 소설의 모든 장을 쓰고 나서는 각 장이 쓰여진 파일을 합쳐서 최종적으로 소설의 완성본이 들어있는 한 개의 파일을 만든다. 이 과정에서 두 개의 파일을 합쳐서 하나의 임시파일을 만들고, 이 임시파일이나 원래의 파일을 계속 두 개씩 합쳐서 소설의 여러 장들이 연속이 되도록 파일을 합쳐나가고, 최종적으로는 하나의 파일로 합친다. 두 개의 파일을 www.acmicpc.net 해결 방법 연속된 행렬 곱셈 푸는 문제와 많이 비슷한 문제인 것 같아서 dp로 풀어줘야 한다. dp[i][j]는 i에서 j까지 합쳤을 때 가장 짧은 최소값이라고 정의를 내리고 시작했다...
문자열 풀이방법 앞에서 추가하는거 뒤에서 문자 추가하는것은 의미가 없고 B와 A문자열이 비교했을 때 가장 차이가 적은 비교한 문자열 B(A의 길이와 동일한 만큼의 부분 문자열)에서 차이가 난 만큼을 반환하면 해결된다. 소스코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { public static void main(String[] args) throws IOException { BufferedReader br=new BufferedReader(new InputStreamReader(Syste..
폰켓몬 풀이 방법 내용을 읽어보면 결국 가장 많이 가져가는 경우는 N/2이고 가장 적게 가져가는 경우는 내가 폰켓몬을 총 잡은 수(중복 제외)이다. 중복을 제외하고 폰켓몬의 종류를 알아내기 위해서 HashSet를 이용했다. HashSet은 결국 집합이니까 중복된걸 알아서 제거하고 size()메소드를 통해서 알아낼 수 있다. 종류가 N/2보다 많아도 가장 많이 가져가는건 N/2이기 때문에 Math.min함수를 이용한다. 소스 코드(Java) import java.util.HashSet; class Solution { public int solution(int[] nums) { HashSet hash=new HashSet(); for(int num:nums) hash.add(num); return Math...
해결방법 미로찾기 문제인데, 상하좌우로 길이 있는지 방문합니다. 길이 있으면 BFS로 데이터를 집어 넣고 한개씩 빼면서 그 다음 곳을 방문하는 것을 반복하면 됩니다. DFS로 하면 깊이탐색이기 때문에 최악의 거리가 나올 가능성이 많기 때문에 사용하시면 안됩니다. BFS는 주변부터 탐색이기 때문에 탐색하면서 최종 도착지가 나오면 그 값이 최단 거리이기 때문입니다. 이번에는 자바로 해봤습니다. 소스코드 import java.util.ArrayDeque; import java.util.ArrayList; import java.util.Arrays; import java.util.Deque; public class Solution { public static void main(String[] args) { in..
후보키 해결방법 후보키로 나올 수 있는 방법은 해당 어트리뷰트의 부분집합이 됩니다. 이것은 조합으로 구하고 해당 집합에 대한 칼럼을 벡터(배열)에 그 벡터 통채로 map의 KEY로 집어 넣었습니다. 그래서 Key가 같으면 후보키로 성립하지 않게 되는 것이죠. 이렇게 구하면 유일성은 걸러낼 수 있습니다. 그 다음 최소성을 만족하기 위해 남은 부분집합들은 부분집합끼리 포함되는 관계에서 포함시키는 부분집합을 제거해줘야 최소성을 만족 시 킵니다. 소스코드 #include #include #include #include #include using namespace std; void combination(vector &combinations, vector order, vector value, int current_..
블록게임 문제를 너무 막 풀어서 코드가 너무 길어버렸네요;; 가로 2X3 세로 3X2 가능한 블록만 모여나서 하나하나 비교하는 형식으로 풀었습니다. 비교했는데 비교한 전부 비교가 가능하면 지워나가는 형식으로 했습니다. possible배열은 가장 위에 어떤 블록이 있는가를 설정해서 벽이 있으나 해당 줄에 2개가 있을 경우 qqq(이름 뭘로 지을지 몰라서 막지음)변수에 저장, qqq가 2개 있을 경우 검은 블록을 안떨어뜨려도 된다고 코드를 짰습니다. 소스코드 #include #include #include #include using namespace std; bool checkgaro(vector &possible, vector &board, int i, int j, int &answer); bool che..
실패율 해결 방법 각 단계마다 스테이지에 도달했으나 아직 클리어하지 못한 플레이어수각 단계마다 스테이지에 도달한 플레이어 수를 다 구해줘야 합니다. N단계까지를 index 2개를 만들어줍니다(pass, notpass) stage벡터에 한개씩 데이터를 읽는데 3단계에서 멈춘사람은 notpass배열 3번째 인덱스를 증가시켜주고 pass배열에 1~3를 증가시켜줘야합니다.이렇게 다 돌면각 단계마다 실패율을 구할 수 있고 인덱스와 실패율을 저장한 구조체를 정렬해서 결과값을 받아오면 됩니다. 소스 코드 #include #include #include using namespace std; struct Result { int number; double fail; }; bool pred(Result a, Result b..
오픈채팅방 해결 방법istringstream를 이용하면 공백을 token으로 분리할 수 있습니다. 그리고 map을 통해서 으로 Key, Value를 잡고Enter와 Change를 만날때마다 계속해서 유저아이디의 닉네임을 계속 바꿔줍니다.그리고 다시 처음부터 해서 바꿔진 유저아이디+메시지로 반환해주면 됩니다. 소스 코드 #include #include #include #include using namespace std; vector solution(vector record) { vector answer; vector log(record.size(),vector(3)); map user; for (int i = 0; i > log[i][0]; iss >> log[i][1]; iss >> log[i][2]; ..
무지의 먹방 라이브 저는 왜 이런게 어려울까요. 입출력 예 food_times : [3,1,2]k : 5result : 1 해결방법 보면 문제가 굉장히 쉬울 줄 알았습니다만 큐에다가 원하는걸 food_times 인덱스들을 담고 k를 1개씩 검사하는 알고리즘으로 채점을 하면 시간초과로 틀려버렸습니다, 이리저리 해매다가 코드가 복잡해버려졌네요. 제가 생각하는 방법은 k를 한바퀴씩 가야되겠다고 생각했습니다. 예제를 보면 1번 음식이 3번이기 때문에 1번음식을 기준으로 한바퀴씩 돌려야 한다고 생각했습니다.가장 큰 인덱스를 구하는 max_index를 구했습니다. 여기서 인덱스가 중간에 있으면 0번부터 max_index까지 1번씩은 섭취했기 때문에 food_times를 1개씩 빼야 했습니다.그리고 한바뀌 돌때마다 ..
길찾기 게임 입출력 예 nodeinfo : [[5, 3], [11, 5], [13, 3], [3, 5], [6, 1], [1, 3], [8, 6], [7, 2], [2, 2]]result : [[7,4,6,9,1,8,5,2,3],[9,6,5,8,1,4,3,2,7]] 해결 방법 이진 트리를 만드는 방법은 보통 2가지로 알고 있습니다. 첫번째는 배열을 통해서 2를 곱했을때와 왼쪽 트리, 2를 곱하고 1를 더했을 때 오른쪽 트리를 이용해서 문제를 풀어 나갈 수 있고 클래스나 구조체를 이용해서 linked list 형식으로 왼쪽 link와 오른쪽 link로 이동하는 방법을 통해서 구현할 수 있습니다. 저는 후자를 선택했는데요 인덱스 값을 저장해야하기 때문에 nodeinfo에 각각의 인덱스 번호 값을 추가했고, ..