걸음마코딩기

map을 이용하면 쉽게 풀리는 구현문제이다. string 입력에서 어떻게 해야할지만 안다면 바로 풀린다. 문자열 일부를 return하는 substr함수를 이용해서 '.' 다음 글자부터 끝까지 return받는다. 그렇게 받은 값을 맵에 저장한다. (default가 오름차순이므로) #include #include using namespace std; int main(void) { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int N; cin >> N; map m; for(int i=0; i> t; string extension = t.substr(t.find('.')+1); m[extension]++; } for(auto x : m) cout

아.. 인덱스가 너무 헷갈리고 회전 레이어 다루는게 어려워서 어려운 문제가 아니었는데도 좀 고전했다.. 다시 풀어봐야할 것 같다ㅜㅠ (확실히 구현에 좀 약한듯..) 우선, 회전 레이어 갯수는 N 또는 M 중 작은 값을 2로 나눈 값과 같다. 시작점은 (0,0), (1,1) ...로 되므로 이를 이용하여 시작점을 잡아주면 된다. 우선, 회전하는 방법을 잘 생각해야 하는데, 시작점을 0,0으로 잡았기 때문에 이를 temp 변수에 넣어주고 시작점부터 채워주기 시작한다. [ 시작점부터 채우는 방향 ] 맨 윗줄 : 오 -> 왼 방향으로 채워준다 가장 오른쪽 열 : 아래 -> 위 방향으로 채워준다 맨 아랫줄 : 왼 -> 오 방향으로 채워준다 가장 왼쪽 열 : 위 -> 아래 방향으로 채워준다. 이 과정을 각 레이어마..

이번 문제는 bfs문제이다. 백준의 토마토와 비슷한 문제이다. 토마토도 괜찮은 문제이니 한번 풀어보길 추천한다! -> 토마토 문제 바로가기 전체 영토 중 방문하지 않은 영토부터 차례대로 순회를 시작한다. 큐에 넣어놓고 주변 영토(상하좌우)를 방문해보며 연합이 될 수 있는지 조건을 체크한다. 연합이 될 수 있으면 bfs용 큐와 연합들을 저장할 벡터에 저장해주고 총합을 더해준다. (나중에 인구수 조정을 위함) 연합이 만들어졌다면 (2개이상) 인구수를 조정해준다. 두번째 for루프에서 방문을 검사하는 코드, 즉 bfs를 실행하는 코드는 같은 날 다른 연합을 또 만들어야하므로 연합을 저장해주는 벡터를 초기화해준다. 두개의 for루프가 끝나고 연합이 아직 남아있다면 days를 증가시켜주고 위 과정을 연합이 만들어..

오랜만에 string 문제를 들고와봤다. 문제는 쉬운편인데, 나는 진짜 단순하게 풀었다. 조금 더 생각하면 깔끔한 코드가 나올 것 같기도 한데, 일단 queue에 무지성으로 때려박고 tag와 단어, 공백 3가지 유형으로 넣어주었다. 출력할때는 단어인 경우에만 reverse를 이용해서 출력해주었다. #include #include #include using namespace std; /* a-z, 0-9, ,(두개 개수 같음) 태그 말고 단어만 뒤집어서 출력 태그는 안으로 길이는 3이상, 공백 포함가능 태그와 단어사이에는 공백 없음 --- // inputs string tag; string words; queue q; if (input starts '') { tag += input; } q.p..

오랜만에 문제 풀기~ 처음에는 큐를 이용해서 문제를 풀까 생각했는데, 더 간단하게 풀릴것같아서 단순 구현으로 풀었다. 어차피 days는 계속 누적되고, cnt만 배포될때마다 확인 후 reset시켜주면 되는거라 while문으로 progress + speed * days가 100 넘을때까지 days를 누적시켜주고, 이후 배포되는 친구들을 위해 cnt가 0이 아닐 때, answer에다가 push해준다. 마지막 값이 누락되는 것을 방지하고자, 루프를 다 돌고 나왔을 때 cnt가 0이 아니면 answer에 push 해준다. #include #include using namespace std; vector solution(vector progresses, vector speeds) { vector answer; i..

숫자가 {2,5,8,0} 일때를 잘 다루는것이 관건! 처음에는, 단순히 현재 위치와 target값을 빼주고, 그 값이 3이면 1으로 바꿔주는 계산방식을 생각했었다. 하지만 만약 target=6이고 현재 위치가(왼손이든 오른손이든) 7이라면, 실제거리는 3이지만 이 로직은 1이라고 말할 것이다. 따라서, 전체 키패드를 격자로 생각하고, 각각의 좌표를 구해준 뒤 좌표 거리 계산을 해주어야 한다! 자세한 내용은 주석을 참고바란다. #include #include #include using namespace std; /* 시작 : 왼손 엄지 - *(10), 오른손 엄지 - #(12) 상하좌우 한칸씩만 이동가능 1,4,7 => 왼손, 3,6,9 => 오른손 2,5,8,0(11) => 둘 중 가까운 손 (거리 같으..

허허.. LV1 이라고 해서 완전 얕봤다가 map을 까먹은 나는야 바보 천치라는 것을 깨닫게 해주었다.. 물론 다른 방법이 많겠지만, 이게 가장 쉬운 접근법인것 같아 공유한다. 일단 다음달 선물을 계산하는 방법은 크게 다음과 같다. 주고 받은 선물 이력이 있는 경우 ➡️ 더 많이 준 사람에게 선물++ 주고 받은 선물 이력이 없는 경우 ➡️ 선물 지수 비교 후, 선물 지수 큰 사람에게 선물++ (선물 지수도 같으면 0) 총 3개의 map을 이용했는데, 주고받은 선물 확인용 선물 지수 확인용 다음 달에 받을 선물 개수 저장용 1번 map은 2차원으로 만들어 주었고 모든 gift를 돌면서 1번과 2번 map 값을 채워주었다. 만들어진 2차원 map(1번)을 다 검사하면 중복으로 검사가 되므로, 두번째 loop..

유명한 그리디 문제! 고려해야하는 부분은 크게 두가지인데, 상하(A~Z)최소값과 좌우최소값이다. 1. 상하 최소 구하기 우선 쉬운것부터 고려하자면 상하 최소는 target에서 'A'까지의 거리와 'Z'에서 target까지의 거리를 비교해주고 최소값을 더해주면된다. 이때, 'Z'에서 거리를 고려하는 경우는 switch가 한번 일어나기 때문에 +1 해준다. 2. 좌우 최소 구하기 이 문제의 핵심이라고 할 수 있다. 우선, 좌우 경우의 수는 크게 두개로 볼 수 있다. 간단하게 순차 진행을 해버리느냐와 역행을 넣느냐 두가지로 나눠 볼 수 있다. 우리가 여기서 집중해야하는 경우는 역행을 넣었을 때, 역행을 언제 하냐에 포인트가 있다. 예를 들어, 'BBAAAAB'는 역행 후 다시 돌아와서 순차 진행을 하는 것이 ..

#include #include using namespace std; int solution(int n, vector lost, vector reserve) { int answer = 0; int res[31]; // 전체 학생 유니폼 리스트 fill_n(res, n+1, 0); // 0으로 초기화 for(auto i : reserve) res[i] += 1; // 여분있는 사람 +1 for(auto i : lost) res[i] -= 1; // 잃어버린 사람 -1, 여기서 여분 있는데 잃어버린 사람까지 처리됨 for(int i=1; i

대표적인 dp문제이다. 하지만, 나는.. 바보같이 처음에 map써봤다가 당차게 틀려먹었다.. (대체 왜이러니..) map쓰면 문자열을 계속 순회해야해서 시간복잡도에서 걸린다. 그리고 이건 대표적인 dp라서 그냥 내가 바보였던것으로.. 넘어갑시다. 아무튼, dp를 이용해서 각 부분 문자열에 대한 LCS 값을 구해나가면 된다! 여기서 dp의 경우의 수는 두가지인데, i번째 문자열 == j번째 문자열 이건 왼쪽 위 대각선 값에 +1 해주면된다. 왼쪽 위 대각선 값이 이전 문자열인 (i-1,j-1)의 LCS 값이기 때문! i번째 문자열 != j번째 문자열 이건 왼쪽과 위 중 max값을 가져가면 된다. #include #include using namespace std; int main(void) { ios::s..