프로그래머스44

• 

  [프로그래머스 / Level_3 / C++] 가장 먼 노드 #접근방법 먼저 그래프의 정보를 다 담아놓자 양방향 간선이기 때문에 from 에서 to로 그리고 to 에서 from 의 정보를 저장한다. 이차원 벡터에서 인덱스 3번에 4, 8 ,9 가 붙어있따면 노드 3에서 노드 4, 노드 3에서 노드 8, 노드 3에서 노드 9 로 연결되어 있다는 뜻! 이후 bfs() 를 적용하기 위해서는 queue 를 생성하는데 처음 담아지는 원소의 값은 1이다 왜냐하면 1에서 가장 멀리 떨어지는 노드를 찾는거니까 1이 시작점인거지! 그리고 queue가 빌때 동안 queue의 첫번째 값을 꺼집어내서 그 값에 연결되어 있는 값들을 queue에 다시 붙여준다. 근데 이때 거리도 하나 올려서 거리 배열에 기록해주자. 근데 만약 현재 보고있는 노드번호에 거리 배열을 찾아가보니까 값이 이미 .. 프로그래머스/Level_3 2022. 5. 18.

• 

  [프로그래머스 / Level_2 / C++] 땅따먹기 이차원 dp를 활용해서 푼 문제이다. #접근방법 해당 문제는 Top-down 방식으로 큰 문제를 해결하기 위해 작은 문제를 호출하는 방식을 썼다. 먼저 현재 위치한 인덱스 번호를 pos에 저장을 하였고 다음 재귀호출을 할 때는 현재 pos에 저장된 열의 번호가 아닌 다른 3개의 열을 나타내는 값으로 전달한다. 언제까지 호출하냐? 2차원 배열 사이즈가 같을 때까지 계속 호출한다. 즉, Level 이 행의 크기만큼 왔을 때는 더 이상 호출할 수 없기 때문에 이때부터 리턴값을 전달해준다. 리턴한 값들은 이전에 재귀함수를 호출했던 코드영역에 가서 반환 받은 값들의 크기를 비교해서 큰 값을 dp에 저장한다. #include #include #include using namespace std; int level; .. 프로그래머스/Level_2 2022. 5. 18.

• 

  [프로그래머스 / Level_2 / C++] 다음 큰 숫자 단순 계산 문제이다. #접근방법 자료구조, 알고리즘 그런거 쓰인거 없이 문제 조건을 보고 무작정쳐서 푼 문제이다. 이 방식보다 더 효율적인 방법인 분명히 있을 거라고 보지만 0.01ms 로 모든 테스트 케이스를 통과하였으니, 더 나은 방식을 찾아보는 것은 생략한다. 먼저, n값을 받으면 이진수로 변환하여 문자열에 저장한다. 이 로직에서는 이진수가 반대로 뒤집혀진 상태로 저장되어있는 것을 기억하자. 해당 이진수 문자열에서 1의 개수가 같은 상태를 유지하면서 큰 값을 구해야한다. 그렇기 때문에 가장 가까운 1의 위치를 찾고 그 위치로부터 인접한 모든 1을 0으로 바꿔주고 최초 0을 만난 경우 그 위치를 1로 바꿔준다. 이때, 1을 0으로 바꿔준 개수를 세어주며 이후 반복문이 종료되면 해당 개수의 -1 만큼 .. 프로그래머스/Level_2 2022. 5. 16.

• 

  [프로그래머스 / Level_2 / C++] 올바른 괄호 스택을 잘 활용하면 풀 수 있는 쉬운 문제이다. #접근 방법 괄호의 쌍은 '(' 와 ')' 이다. 문자열의 길이만큼 돌아보면서 '(' 라면 스택에 담고 ')'라면 스택의 top에 '('가 위치한지 확인한다 본인은 문자형으로 넣지 않고 숫자 1이 '(' 의 의미이다. 만약 문자열의 현재 문자가 ')' 이고 stack의 top이 1이라면 ')'의 짝이 맞으니 스택의 top을 pop해준다. 만약 문자열의 현재 문자가 ')' stack의 top이 1이 아니라면 ')' 괄호가 먼저 시작된 의미이므로 더 돌아볼 필요도 없이 바로 false를 리턴해준다. 그 이유는 괄호의 짝은 순차적으로 정해진다. 즉, ')' 닫히는 괄호를 만났다면 그 전에 짝인 '(' 괄호가 바로 앞에 존재해야한다. 근데 '((((()))))" .. 프로그래머스/Level_2 2022. 5. 16.

• 

  [프로그래머스 / Level_2 / C++] 모음사전 완전탐색을 이용하면 간단하게 풀리는 문제이다. #접근방법 먼저 전달받은 문자열이 사전의 몇번째 위치인지 확인하려면 사전을 미리 만들어야한다. 사전에 알파벳 모음 'A', 'E', 'I', 'O', 'U'만을 사용하여 만들 수 있는, 길이 5 이하의 모든 단어가 수록되어 있습니다. 위의 조건을 보면 알파벳 모음은 5개밖에 없고 길이도 5이하라면 완전탐색으로 사전을 만드는데 충분한 시간을 가지고 있다는 것이다. A : 1 AA : 2 AAA : 3 AAAA : 4 AAAAA : 5 AAAAE : 6 위의 순서를 보면 DFS가 살짝 보인다. 뭔가 문자열 길이가 5일때까지 A를 뒤에다가 붙여주고 길이가 5가 된다면 맨끝 알파벳을 E로 바꿔주고 그다음에는 I가 될거고 ... 대충 느낌이 올것이다. 즉, DFS 방.. 프로그래머스/Level_2 2022. 5. 15.

• 

  [프로그래머스 / Level_2 / C++] 구명보트 이 문제는 그리디를 활용해서 풀면 되는 문제므로 어떻게 문제에 접근해야할지 잠깐 고민할 시간이 필요하다. 해당 문제에서 구명보트에는 단 두사람만 탈수 있다는 것에 중점을 두고 풀어야한다. 아무리 몸무게가 낮다고 해도 탈 수 있는 사람은 단 두명! 그렇기 때문에 가장 적절하게 사람들을 태우기 위해서는 "제일 무거운사람 한명"과 "제일 가벼운사람 한명"을 태워야한다. 왜냐하면 무거운 애들 두명을 태울려고 해도 limit을 넘길 경우가 무조건 있을 것이다. 그렇기 때문에 최대한 가벼운애 한명 + 무거운애 한명을 태우는게 이 문제에서 요구하는 조건인것이다. #접근방법 1. 무게를 담고 있는 벡터 오름차순으로 정렬 2. 투포인터를 활용하기 위해 시작 포인터 s와 끝 포인터 e를 생성한다. 3. s가 가리키는 원소.. 프로그래머스/Level_2 2022. 5. 14.

• 

  [Level_2 / C++ / Python / 카카오] 오픈채팅방 공백으로 문자열 자르기 문자열이 공백이 주어진 상태로 주어진다면 공백을 기준으로 문자열을 자를 수 있다. 예) string s = "abc def gh" ; 해당 문자열을 "abc" , "def" , "gh" 로 자르는 거다. 해당 문법을 알아보자. #include #inclu.. baebalja.tistory.com 1. stringstream 을 활용해서 띄워쓰기에 따른 값들을 해당 변수에 저장한다. 2. unordered_map 을 활용해 uid에 따른 name을 저장한다. (change 명령이 들어와도 덮어씌우면 된다.) 3. map에서 uid에 해당하는 value값을 출력하면 된다. #include #include #include #include #include using namespace st.. 프로그래머스/Level_2 2022. 3. 31.

• 

  [프로그래머스 / Level_2 / C++ ] 프린터 Queue를 응용해서 String의 substr 를 활용했다. #접근방법 문제를 잘 읽어보면 중요도는 1~9까지 표현가능하다고 했다. 그렇기 때문에 찾고자 하는 location위치의 우선순위 값을 res_num이라는 변수에 따로 빼놓고 해당 위치의 우선순위 값을 0으로 수정한다. 그리고 priorities 벡터를 오름차순으로 정렬한 뒤, 뒤에서부터 찾는다. 1. 우선순위가 가장 높은 것을 탐색하는데 가장 높은 우선순위가 아니면 지나간다. 2. 만약 우선순위 가장 높은 것을 탐색했으면 그 값을 기준으로 자르고 왼쪽 문자열과 오른쪽 문자열을 위치를 바꾼다. 3. 만약 찾고자하는 location의 값을 만나게 된다면 그 즉시 cnt를 반환한다. ( cnt는 문자열을 자른 횟수) #include #include.. 프로그래머스/Level_2 2022. 3. 28.

• 

  [프로그래머스 / Level_2] 소수 찾기 완전 탐색 문제이다. #접근방법 카드 번호로 만들 수 있는 모든 값들을 조합해보면서 소수를 찾는 문제이다. dfs를 처음 호출했을 때는 만들어진 문자열이 없으므로 level이 1 이상일 때만 현재 만들어진 문자열이 소수인지 체크한다. 문자열로 전달하였기 때문에 stoi 함수를 활용해서 int형으로 변환 후 prime_check 함수를 호출하여 해당 값이 소수인지 판별한다. 만약 그 값이 소수라면 set 자료구조를 이용해서 해당 값을 넣어준다. ( set은 중복 무시 ) 이후 방문처리 되지 않은 카드가 있다면 문자열 뒤에 붙여주면서 dfs를 호출한다. dfs 호출 후 돌아오고 나면 다른 case에서도 사용해야하기 때문에 방문 처리했던 값을 다시 false로 반환한다. #include #include #in.. 프로그래머스/Level_2 2022. 3. 26.

• 

  [프로그래머스 Level_3 / C++] 최고의 집합 각 원소의 합이 S가 되는 수의 집합 위 조건을 만족하면서 각 원소의 곱이 최대가 되는 집합 원소의 합이 S가 되는 수 중에 제일 곱이 최대가 될 때가 언제인지 짐작이 오면 된다. S를 N으로 나누었을 때 생성되는 평균값에 가까울수록 곱이 최대가 된다. 예를 들어, S = 86 이고 N = 9 이고, 이 의미는 숫자 9개를 가지고 합을 86을 만들면 된다. N으로 S를 일단 나눠보자. 몫은 9 (평균값)이고 나머지는 5이다. 평균값 9를 N개 만큼 나열 해보자. "9 9 9 9 9 9 9 9 9" 여기에 나머지 값인 5를 가지고 1씩 공평하게 나눠주자. "9 9 9 9 10 10 10 10 10" 이 값들을 곱했을 때 최대가 나온다. #include #include #include using namesp.. 프로그래머스/Level_3 2022. 3. 4.