공부의 발자취를 남기는 블로그

문제분석 Level2 답지않게 여러 기술을 많이알아야 풀수있는문제다. (역시 카카오문제) 문제목표: 차량기록을 모두처리한뒤에, 이용한 차량마다 주차요금 구하기 (차량번호 적은순) 제일먼저, 요금표에있는 기본시간 (std_time) , 기본요금 (std_pay) , 단위 시간(per_time), 시간당 요금(per_pay) 로 알기쉽게 분리해놨다. 그리고 우리가 문제를 풀기위해서 2개의 Map을 준비했다. 첫번째, 이용시간을 구하기위한 Key= 차량너버, value=입장시간인 맵 하나와 두번째, 각 차량넘버의 이용비를 저장하는 Key=넘버 ,value=이용비 맵 하나를 준비했다. 그리고, 차랑넘버순으로 정렬을 해줘야하니 TreeMap으로 설정해뒀다. 주차기록을 처리하는 로직이다. 기록의 문자열을 정리하여 ..

문제풀이 문제보고 한 5분동안 멍 때린 문제다.... 처음 생각했을때, 문제 설명처럼 0P0 , 0P, P0, P인 경우를 모두 고려해서 뽑아야 하나 생각햇는데, 방법도 잘 떠오르지도 않으며 그냥 귀찮았다... 뭔가... 좀 쉽게 풀수는 없나 꼼수를 부리다가 이런 생각 해봤다. 그냥 이거 "0" 들어간걸 기준으로 분해시켜버리면 되는거아닌가?? 생각해보니 4개의 기준 모두 0을 기준으로 분리가되어있고, 0을 기준으로 분해를해도 문제될게 전혀 없다는걸 발견했다. 문제를 풀기위한 첫번째 스텝으로 N진법 로직이다. 알고리즘 문제를 많이풀어봤으면 N진법 변환 로직은 간단하다. While문을 사용하여, N을 K로 나눈 나머지를 계속 앞에다가 붙여가면된다. 두번째 스텝으로, 이 N진법으로 푼 문자열을 "0" 을 기준..

문제분석 되게 심플한 문제설명과는 달리, Level2 치곤 (본인이 느끼기엔) 매우 높은 구현난이도를 가지고 있다. 문제 설명에서 '1924를 수 두 개를 제거해 {19,12,14 ...} 를 만들수 있습니다' 를보고 오.. 이 문제는 조합 알고리즘(백트래킹) 써서 만들면 되는구나.. -> 하는 순간 당신은 함정에 빠지는겁니다 이 문제의 제한사항을 보시면 number자리수가 100만자리입니다. 조합을 쓰면.. 1,000,000C2 라는 연산을 하는데 당연히 효율성 펑크나겟죠..? 요점은 무엇이냐! 최대 시간복잡도 O(N)으로 짜야한다는점. 근데 사실 100만번도 많아요... 더줄여야해요 .. O(log(N))을 노력합시다. 풀이전략: 어찌댓든 저희 목표는 제거해서 남는 숫자를 담아야합니다. 즉 반복문을 ..

문제분석 brown 과 yellow의 블록갯수를 주어집니다. brown은 테두리 색깔이고, yellow는 테두리를 제외한 내부의 색깔입니다. 목표: 카펫의 행과 열의 갯수 구해주기 우선 전체 블록갯수를 구할수있습니다. brown+yellow 로 구할수있죠. 카펫의 전체블록갯수는 행X열로 구할수있습니다. 행, 열을 구하려면 전체블록수/행의갯수 = 열의갯수 가 가능한부분을 모두 구하자. 여기서 전체블록수%행의갯수가 0이 아닌경우는 모두 빼야한다. (실수인값은 모두 제외해야함) 이렇게 모인 행,열 가능한 후보자들을 모두 모아 내부갯수가 yellow와 일치한지구한다. 카펫의 테두리를제외한 내부의 갯수는 (행-2)*(열-2)값으로 자동적으로 구해진다. 문제풀이 1 2 3 4 5 6 7 8 9 10 11 12 13..

문제분석 꽤나 당황스러운 규칙을 가졋습니다. 문제를 보니 위키백과를 링크를 해줬으니 들어가서 참고 하라는것 같습니다. 물론 보지않고 푸시는 분이 있겟지만, 저는 참고했습니다. 도대체 이게 무슨 공식인가.. 하면 일단, 이 수식을 사용하려면 배열을 내림차순 정렬을 해달라고 했습니다. 헌데.. 문제에서 준 int[] 배열은 내림차순 정렬을 그상태론 못합니다. 내림차순 정렬을 하기위해선, Collections.reverseOrder()나 comparator를 사용해야하는데, 이 메소드를 지원하는건 객체 상태로 Wrapper된 타입만 지원합니다. -> int[] 를 Integer[]로 바꿔야하죠 따라서, 그냥 오름차순 정렬을 한뒤, 뒤에서부터 탐색을 하기로 했습니다. 괜히 내림차순 정렬한다고 타입을 변환하는 연..

문제분석 목표: 모든 트럭을 다리를 건널때 걸리는 시간구하기 특수조건: 다리는 일정한 무게(weight)만 견딜수있음. 다리를 건널때 길이당 1초씩 걸림. 문제를 들어가기전에 소제목으로 스택/큐가 있는것처럼, 스택/큐의 기본기를 강화시키기 좋은 문제라고 생각합니다. 스택은 FILO 으로 먼저 들어간게 제일 나중에 나오는 형식이고, 큐는 FIFO으로 먼저 들어간게 제일 먼저 나오는 형식을 가집니다. 제일 먼저 들어간 트럭이 제일 먼저 나오는 문제의 맥락상 Queue를 써야겟다고 판단했습니다. Queue를 사용하되, 트럭이 들어가는 조건, 탈출하는 시간을 구할 필요가있습니다. 그 이유는, 1.트럭이 여러대 들어가다 다리가 무게를 못견디는 경우를 제외해야하며, 2.트럭이 탈출할때, 다리의 무게가 다시 트럭의 ..

문제분석 목표: 스파이가 위장을 할수있는 경우의 수를 구하시오. 주어지는 입력: [의상의 이름, 의상의 종류] 형식으로 주어지는 clothes 위 사진의 표를 보면, 종류와 이름이 너무 이쁘게 Key , Values로 나누어져 있지않나요? 주어지는 입력들도 Key, Value형식으로도 마침 주었고요. 그래서 필자는 적극적으로 Map(HashMap)을 사용했습니다. Key : 의상의 종류 , Value : 의상의 이름을 담는 리스트 Map에 정보를 입력할때, 2가지 분기를 나누어줫습니다. 1. 의상의 종류가 없을때 -> 새로운 리스트를 생성한뒤, 의상의 이름을 담아 넣어준다. 2.의상의 종류가 이미 있을때 ->그 의상의 종류의 의상리스트를 가져와, 새로운 의상을추가해 다시 넣어준다. ------------..

문제분석 문제로, 각 마을간의 다리와 이동거리를 주어집니다. 목표 : 1번마을로부터 출발한다고 가정할때, N시간 이하로 배달이 완료되는 지역 개수를 구하시오. 요점은, 정점과 정점 사이의 최소거리를 구하는 알고리즘을 구현하면된다. 그게 바로, 플로이드 와샬 알고리즘이다. 구현은 구글링을하시면 다 나와있습니다. 플로이드 와샬 구현법: 1. 정점의 개수만큼 2차원 배열 생성, 그리고 모든 배열값에 INF 부여 (큰 숫자) 2. 입력으로 받은 정점과 정점사이의 다리를 입력합니다. 3. 3차반복을통해, 정점과 정점사이의 다리의 최소거리를 구합니다. 사실 이 플로이드 와샬 알고리즘은 꽤나 쉽게 구현이 가능합니다. 자세하게 돌아가는 원리를 아는게 힘들다면, 언제 어떨때 써야하는지 알고, 검색하고 적용하는게 중요하다..

문제분석 () [] {} 로 이루어진 괄호기호가 무작위로 배치가되어있습니다. 괄호 기호를 첫 입력과 똑같이 될때까지 한 문자씩 회전시킵니다. 회전시키는 도중 올바른 괄호문자열이 있으면 갯수를 셉니다. 2개의 로직을 구현할 필요가있습니다. 1. 해당 문자열이 올바른 괄호 문자열인지? 2. 해당 문자열을 한문자씩 회전시키기 1번 로직은 Stack으로 구현이 가능합니다. '(' 와 ')' '['와 ']' 만나면 제거를 한뒤, 스택이 텅텅비어있으면 올바른 괄호문자열입니다. 2번 로직은 for loop로 문자열 길이만큼 반복을한뒤, 첫번째 문자를 맨 뒤로 보내면 끝입니다. (문자열 다루기) 문제풀이 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 2..

문제분석 주어지는 입력 : A의 대진번호, B의 대진번호 구해야하는 값: A 와 B가 대진하게될 라운드를 구하기. 규칙: A,B는 만나기전까지 무조건 이기는것을 가정한다. 이 문제의 핵심은 규칙파악입니다. 규칙이 도대체 뭘까요? 1번과 2번이 대진을 벌여 이기면, 1번을 부여받고 다음 라운드로 진출합니다. 3번과 4번이 대진을 벌여 이기면, 2번을 부여받고 다음 라운드로 진출합니다. 5번과 6번이 대진을 벌여 이기면, 3번을 부여받고 다음 라운드로 진출합니다. ... 짝수번호/2 = 다음라운드에서 받게될 번호 라는걸 눈치채셧을겁니다. 홀수번호는 (홀수번호 +1) /2 = 다음라운드의 번호입니다. 이 형식을 반복하다, A와 B의 차이가 1이될경우 반복로직을 종료합니다. 문제풀이 1 2 3 4 5 6 7 8..