목록프로그래밍/알고리즘+코딩테스트 (97)
有希
문제를 잘 읽어보면 그대로 숫자를 두는 경우는 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
백트래킹은 항상 어렵다. 익숙하지 않아서 인듯 아래에 설명이 잘 되어있다. https://leetcode.com/problems/permutations/discuss/1961596/C%2B%2B-oror-Easy-to-Understand-with-Diagram-oror-0-ms-oror-Backtracking 눈여겨 보아야 할 점은 j는 i부터 시작이라는 점이다. 즉, 자기자신과 swap을 함으로써 모든 경우를 포함시킨다. 123을 생각해보면 for 루프를 돌면서 123 213 321 을 tracking함수에 num으로 넘기고 i는 1이 된다. 123을 생각해보면 j=i, 즉 1인 상태에서 swap 123 2인 상태에서 132 가 된다. 이제 i를 2로 만들어서 넘기면 if문에 의해 123 132가 re..
문제에서 O(log n) 이라고 했으니 이진탐색으로 풀어야 한다. 가장 작은 idx와 가장 큰 idx 를 골라내어야 한다. 가장 작은 경우: mid값이 target보다 크거나 같다면 right를 mid-1로 지정하고, 아니라면 left를 mid+1로 지정한다. 이 이유는 같은 경우에도 왼쪽에 더 작은 값이 있는지 봐야하기 때문이다. 가장 큰 경우: mid값이 target보다 크다면 right를 mid-1로 지정하고, 아니라면 left를 mid+1로 지정한다. 이유는 left right가 겹칠때까지 전부 찾은다음 target의 가장 큰 idx를 찾아야 하기 때문이다. if문에서 같으면 무조건 갱신하는 것 또한 중요하다. class Solution { public: vector searchRange(vect..