길찾기 게임 입출력 예 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에 각각의 인덱스 번호 값을 추가했고, ..
파일명 정렬 문제풀다가 몰라서 해설을 보았습니다. sort에서 stable_sort로 바꾸자마자 통과되네요 ㅠㅠ 입출력 예제 입력 값 : ["img12.png", "img10.png", "img02.png", "img1.png", "IMG01.GIF", "img2.JPG"] 출력 값 : ["img1.png", "IMG01.GIF", "img02.png", "img2.JPG", "img10.png", "img12.png"] 해결 방법 2차원 배열로 이용해서 head와 number를 구해줍니다. 저는 그냥 while문 돌려가지고 숫자가 나오기 전까지 head 그다음 문자가 나오기 전까지 number로 하고 남은 것은 tail에 붙여줬습니다. 나중에 이어붙여야 하기 때문이죠 그리고 2차원 배열을 정렬 함수를 ..
자동완성 코드 엉망이네 멋지게 푸는 방법을 모르겠습니다 ㅠㅠ; 입출력 예제 words : ["go","gone","guild"] result : 7; 해결 방법 저는 이 문제를 풀기 위해서 트리구조를 이용했습니다. 문자만 있기 때문에 해당 문자의 이어지는 tree를 계속 이어서 만들었습니다. words를 길이순으로 정렬해줍니다. ex) gone이 go보다 먼저 있을 경우 안됩니다.(적어도 제코드에서는) 그리고 데이터를 집어 넣는데 입출력 예제를 예시로 처음에 go를 먼저 할때 g라는 트리에 count를 1 증가 시킵니다. 그다음 g의 o위치의 트리를 만들어서 o 위치의 트리로 이동한 후 count를 1 증가시킵니다. 그리고 마지막이라는 것을 표시하기 위해서 o번째에 flag를 달아줍니다. 그 다음 gon..
N진수 게임 누가 이런겜을 하는지 입출력 예제 n : 2t : 4m : 2p : 1result : "0111" 해결 방법 가장 중요한 것은 N진수를 만드는 방법이라고 생각합니다 20이라는 숫자있고 4진수로 만들고 싶으면 4|20 4| 5 ....0 4| 1 ....1 4| 0 ....1 이 방식대로 110이 나온다중요한건 마지막에 나눈 값이 숫자의 가장 높은 자릿수가 되버린다. LIFO이기 때문에 스택방식으로 저장해서 빼낼 수 있지만값을 20을 4로 나누고 0 데이터 넣고 (0)그다음 5를 4로 나누고 1 데이터를 0 앞에다 넣고 (10)그다음 1을 4로 나누고 1 데이터를 10 앞에다 넣어버리면 된다. 이렇게 값을 다 구했으면 튜브가 말해야 하는 위치를 골라서 answer에 넣어주면 된다. 소스 코드 ..
압축 입출력 예제 msg : TOBEORNOTTOBEORTOBEORNOTanswer : [20,15,2,5,15,18,14,15,20,27,29,31,36,30,32,34] 해결 방법 처음에 문자를 1개씩 합쳐봅니다. 저는 temp 라는 곳에 T를 넣었을 때 사전에 있으면 TO도 찾아봅니다. TO가 없을 때 이 문자를 index(사전)에 집어넣는 방법을 이용해서 풀면 해결이 됩니다. C++로 저는 find함수를 이용해서 데이터를 찾아냈습니다. 그리고 해당 번호는 find를 찾았을때 iterator로 반환되는데 iterator-벡터 시작의 값을 이용해서 색인 번호를 찾아낼 수 있습니다. 소스코드 #include #include #include using namespace std; vector solutio..
N으로 표현 입출력 예 N : 5 number : 12 return : 4 해결 방법 제가 푼 방법은 N 2개 가지고 가능한 모든 수를 구하고 n이 3개를 이용한 값을 만들기 위해서 n이 2개 사용한 값과 n이 하나인 모든 값을 n이 3개인 값의 배열에 저장합니다(1개 X 2개 , 2개 X 1개) n이 4개를 이용한 값을 만들기 위해서 1개X3개 2개X2개 3개X1개 배열들의 모든 값들을 n이 4개인 배열에 저장합니다. 이런 방법으로 문제를 풀면 정답이 나왔습니다. 당연히 n이 많을 수록 나오는 값이 굉장히 불어납니다. 그래서 효율은 많이 떨어지는 코드입니다. 소스 코드 #include #include #include using namespace std; int func1(int number) { int..
셔틀버스 입출력 예제 n = 1;t = 1;m = 5;timetable = { "08:00", "08:01", "08:02", "08:03" };return : "09:00" 해결 방법 이 문제는 콘이라는 사람이 막차를 타고 가장 늦게 타는 것이 핵심입니다.처음에 timetable의 시간은 제각각이라서 우선순위 큐를 이용해서 정렬해줬습니다.막차가 아니면 그 시간대의 사람은 전부 태울 수 있고 막차가 아닌데 그 시간대에 탈 수 있는 사람이 없다면 태울 수 있는 사람만 태우고 가버리면 되고 막차이든 막차가 아니든 사람이 없으면 가장 마지막 배차를 반환해 줘야 합니다. 그리고 막차인데 태울 수 있는 한도가 많을 경우 가장 마지막번째의 타는 사람보다 1분 도착하도록 반환을 해주는 것으로 풀었습니다. 정말 무식하..
추석 트래픽 입출력 예제 lines: [ 2016-09-15 20:59:57.421 0.351s, 2016-09-15 20:59:58.233 1.181s, 2016-09-15 20:59:58.299 0.8s, 2016-09-15 20:59:58.688 1.041s, 2016-09-15 20:59:59.591 1.412s, 2016-09-15 21:00:00.464 1.466s, 2016-09-15 21:00:00.741 1.581s, 2016-09-15 21:00:00.748 2.31s, 2016-09-15 21:00:00.966 0.381s, 2016-09-15 21:00:02.066 2.62s ] return : 7 문제 해결 수많은 에러때문에 무식하게 풀어버렸네요. 2016년 9월 15일 필요없고 ..
뉴스 클러스터링 입출력 예제 str1 : FRANCEstr2 : french 해결 방법 문제에서 2개의 문자 만들어야한다. 조합으로 만드는것이 아니라 순서대로 2글자 만드는 것이므로 for문 1개로 해당 위치와 다음 위치를 불러와서 저는 multiset에 저장했습니다. 2개의 집합을 만들어 냈으면 1번째 집합의 개수만큼 union을 더하고 2번째 집합에 대해서 1번째의 값이 속해있으면 intersaction에 더하고 없으면 union에 더하면서 풀어나가면 해결이 된다. 만약 속한게 있으면 1번째 집합에 있는 해당 값을 없애 줘야 한다. 소스 코드 #include #include #include #include using namespace std; int solution(string str1, string..
median of two sorted arrays 입출력 예제nums1 = [1, 2] nums2 = [3, 4]return : 2.5 해결 방법여기서 가장 중요한 문제는 nums1과 nums2의 병합이다. 병합정렬을 알고 있다면 충분히 쉽게 풀 수 있다고 생각한다. nums1과 nums2에 대해 각각에 처음 위치를 두고 왼쪽과 오른쪽에서 작은 순부터 새로운 배열(nums3)에 값을 차례대로 집어넣고 다 집어 넣었으면 덜 집어 넣은 배열을 한번에 nums3에 집어 넣어서 병합 정렬을 하면 된다.median은 중앙값을 의미한다. nums3가 짝수개일때는 중앙이 애매하기 때문에 중앙에 있는 왼쪽과 오른쪽의 평균값을 취하고 홀수 개일때는 가운데의 값을 반환하면 된다. 소스 코드 public class Solu..