목록전체 글 (179)
有希
arr이 2개 주어진다. 1번째 arr에 담겨있는 숫자들의 공배수들 중 2번째 arr의 가장 작은 값 이하인 녀석들을 num이라 한다면, 2번째 arr에 담겨있는 숫자들을 나머지가 0이 되도록 나눌 수 있는 num의 개수를 세는 문제이다. 예시를 보자면 a=[2,6]이 주어지고 b=[24,36]이 주어진다. 2와 6의 공배수는 6의 배수들이다. 6,12,18,24,30,36.... 이 중 24보다 작은 녀석들은 6,12,18,24 이다. 다시 이 녀석들 중 b의 원소들을 모두 나머지 없이 나눌 수 있는 녀석들은 6,12의 2가지고 return 값은 2가 된다. 공배수니 뭐니 수학적 얘기가 막 나와서 머리가 좀 아픈데, 수학적 얘기들을 치우면 단순한 해결법이 존재한다. a[마지막]
두 캥거루가 각자 다른 출발선에서 각자 다른 속도로 한 번씩 점프할 때 만날 수 있는가를 물어보는 문제. 속도가 빠른 녀석이 앞에 있다면 영영 만나지 못하니 NO 속도가 빠른 녀석이 뒤에 있다면 만날수도 있으므로 루프 돌면서 계산해서 만나면 YES처리해준다. 더 빠르게는, abs(x1-x2)%abs(y1-y2) == 0 라면 YES가 되겠다. while 루프를 도는 것을 한 번에 수학식으로 처리한 것이다. string kangaroo(int x1, int v1, int x2, int v2) { string ret=""; while(true) { if(v1 >= v2 && x1>x2) { ret = "NO"; break; } if(v2 >= v1 && x2 > x1) { ret = "NO"; break; ..
문제를 잘 읽어보면 그대로 숫자를 두는 경우는 2가지가 있다. 1. 2를 더해도 40이상이 되지 않을때 -> 38미만은 모두 그대로 둔다. 2. 2를 더해도 다음 5의 배수 이상 숫자가 되지 않을때 -> 5로 나눴을때 나머지가 3미만이라면 2를 더해도 다음 5의 배수가 되지 않는다. 숫자를 반올림처리(인접한 자기보다 큰 5의 배수로 올리는 처리)를 하는 경우는 다음과 같다. 1. 2를 더했을 때 자기보다 큰 최소의 5의 배수숫자 이상이 될 때. -> 5로 나머지 구했을때 3미만이면 된다. 반올림한 숫자는 자기자신 + 다음 5의 배수까지 부족한 만큼이다. 부족한 만큼은 5 - (나를 5로 나눈 나머지) 이다. vector gradingStudents(vector grades) { for(int i=0; i
12시간 체제를 24시간 체제로 바꾸는 문제. 주의해야 할 것은 h가 12일때 뿐이다. 오전 12시는 00시로 바꿔줘야 하고, 오후 12시는 그대로 둬야 한다. 오후 12보다 오후 11시가 더 늦은 시간임에 주의할 것. PM처럼 AM에서 h-12를 해버리면 시간표기 양식인 00이 아니라 0이 나오므로 "00"으로 밀어준다는 점도 주의해야 한다 string timeConversion(string s) { string h = s.substr(0,2); string format = s.substr(8,2); if(format == "PM") { if(h != "12") h = to_string(stoi(h)+12); } //AM else { if(h == "12") { h = "00"; } } string r..
0번째 인덱스부터 세려고 하면 어렵다. dp 적용하기도 어렵고. 차라리 거꾸로 적용하면 편하다. 2 3 1 1 4 를 예시로 보면 4부터 시작해서 3까지 거꾸로 간다. 1. 4 + 4 >= 4 이므로 target은 4 2. 1 + 3 >= 4 이므로 target은 3 2. 1 + 2 >= 3 이므로 target은 2 3. 1 + 1 >= 2 이므로 target은 1 4. 2 >= 1 이므로 return true 일련의 과정에서 알 수 있듯이 target까지만 어떻게든 도달한다면 index의 끝까지 도달할 수 있다. class Solution { public: bool canJump(vector& nums) { int target = nums.size()-1; for(int i = target-1; i >..
인자로 주어지는 n명의 사람들 중 한 명이 judge이고 n-1명은 이 사람을 믿는다. 는 것이 맞으면 해당 사람의 번호를 return하고 조건에 부합하지 않으면 -1을 return하는 문제. vector 2개를 둬서 등징횟수 세는 용도, 믿는 count 세는 용도로 쓴다. judge는 아무도 믿지 않으므로 등장횟수는 0, 믿음 받은 count는 자기 자신을 제외한 마을 사람들 모두 이므로 n-1이 되어야 한다. 위 조건에 해당하지 않으면 judge가 없으므로 -1이다. class Solution { public: int findJudge(int n, vector& trust) { //idea is to count indegree of each vertices //if indegree is n-1 mea..
예전의 나였다면 어떻게든 수학식으로 일반화시켜서 해당 식에서 바로 값을 추출해서 vector에 넣고 반환했을 것이다. 수학적으로 정리해서 깔끔하게 짧은 시간내에 완성하는건 좋은데 시간이 많이 걸린다. 그냥 단순무식하게 문제에서 주어진 것처럼 빙글빙글 탐색하면 된다! 1. 우->하->좌->상 으로 탐색하므로 이를 깔끔하게 처리할 방향배열 dy dx를 선언한다. 2. 현재 위치 y,x 변수, 다음 이동할 위치 nextY, nextX 변수 선언, cnt는 이동횟수, num은 전체 칸 갯수. 전체 칸 갯수만큼 이동하고 나면 루프를 빠져나와서 res를 반환하면 된다. 3. h와 w는 이동할 수 있는 곳인지 아닌지를 판단하기 위해 저장한다. dir은 dy dx벡터에서 이용할 방향의 인덱스 1. 0,0에서 시작하므로..
어려운 문제는 아니다. 기본적인 수학 문제. 다만 문제가 조금 이상한게, 예외처리에서 n이 INT_MAX이거나 INT_MIN일 때만 처리하면 된다. double의 범위에서 1다음으로 큰 1.00001 을 2^31-1 제곱하면 다음과 같은 수가 나온다. 나는 이렇게 크게 나올지 몰랐는데 1을 2^31-1 했을때 timeout이 나오는거 보고 설마해서 계산해봤더니 엄청 큰 수가 나왔다. 아무튼, INT_MAX와 INT_MAX일 때에는 항상 x가 1 or -1 or 0이 주어진다고 보면 된다. 따라서 코드는 아래와 같이 짠다. 속도는 0ms 나오는거보면 더 고민해 볼 필요는 없을듯. discuss에 가봐도 다들 1중 루프 써서 풀었다. class Solution { public: double myPow(dou..
"apple" 이 3개가 있으면 그대로 3개를 넣어야 한다는 점에 유의해야 한다. "eat" "ate" "tea"를 어떻게 하나로 묶을까를 우선 생각해 봐야 한다. 하나의 그룹에 대해서 묶을 방법만 생각해낸다면 다른 그룹에 대해서도 묶을 수 있고 이것들을 그대로 vector에 담아서 return하면 되기 때문. 처음에는 eat의 알파벳별 개수를 map에 저장해서 strs를 순회하며 같으면 set에 넣고 하는 방식으로 하려고 했었다. 하지만 잘 생각해보면 문제에 이미 힌트가 있다. -> '이루는 알파벳의 종류와 수가 같다' 즉, 정렬하면 같은 단어가 된다는 말이다. 이를 이용해서 정렬한 단어를 key로 이용하고 원래 단어를 value로 쓴다. map을 하나 만들어서 key를 string, value를 ve..
고등학교 때 배운 회전행렬을 이용하려 했었으나, 행렬의 idx를 우리가 기존에 쓰는 x,y 직교 좌표계로 변경해야 하는등 어려움이 있었다. 문제에서 주어진 그림을 뚫어져라 살펴보면 다음과 같다. 123456789 행렬을 예로 들면 변환 후 각 행의 구성 요소는 741 852 963 이다. 이는 기존의 행렬에서 각 원소를 대각선 기준으로 transpose 했을 때의 행 구성과 같다. 이제 각 행 별로 거꾸로 뒤집어 주면 똑같다. class Solution { public: void rotate(vector& matrix) { int n=matrix.size(); for(int i=0;i