탑 코딩테스트 연습 - 탑 수평 직선에 탑 N대를 세웠습니다. 모든 탑의 꼭대기에는 신호를 송/수신하는 장치를 설치했습니다. 발사한 신호는 신호를 보낸 탑보다 높은 탑에서만 수신합니다. 또한, 한 번 수신된 신호는 다 programmers.co.kr 문제 설명 인덱스가 0인 경우에는 왼쪽에 더 이상 송전탑이 없으므로 answer에 0을 넣어주고 주어진 heights를 1부터 size까지 탐색한다. 해당 인덱스를 i라고 할 때 그 이전에 heights[i]보다 큰 높이를 찾으면 answer에 넣어주고 break를 건다. heights[i]보다 큰 송전탑이 없으면 0을 넣어준다. 문제 풀이 소스코드 : C++ #include #include using namespace std; vector solution(..

쇠막대기 코딩테스트 연습 - 쇠막대기 여러 개의 쇠막대기를 레이저로 절단하려고 합니다. 효율적인 작업을 위해서 쇠막대기를 아래에서 위로 겹쳐 놓고, 레이저를 위에서 수직으로 발사하여 쇠막대기들을 자릅니다. 쇠막대기와 레� programmers.co.kr 문제 설명 (는 스택에 쌓아주고 )일때마다 top에 있는 (를 pop하고 스택의 사이즈를 answer에 더해준다. 문제 풀이 소스코드 : C++ #include #include using namespace std; int solution(string arrangement) { int answer = 0; vector v; // stack for(int i=0; i

멀쩡한 사각형 문제 설명 처음에 문제를 접했을 때, 아무리 생각해도 로직이 떠오르지 않았다. 그래서 조금 수학적으로 생각을 바꿔보았다. 대각선을 그릴 때에도 가로의 길이와 세로의 길이와 관련이 있다. 중복되는지점이 4개라는 것을 알 수 있다. 결국 이 대각선을 지나는 사각형의 개수를 구하기 위해서는 중복되는 지점의 개수를 찾아 빼주면된다. 이 경우에 중복되는 지점은 1개이다. 빨간 부분에서 중복되는 점이 발생한다. 결국 이 중복되는 점은 두 수(2,3)의 최대공약수이며 위 모양의 반복되므로 그 개수 *4를 해주면 중복되는 지점의 개수를 구할 수 있다. 결국에는 8과 12의 최대공약수가된다. 따라서 이 문제를 식으로 해결하면 answer = w*h(전체 사각형의 개수) - (w + h - gcd(w,h)가..

뉴스 클러스터링 문제 설명 주어지는 문자열을 2글자씩 잘라 다중 집합을 만들고 두 문자열의 다중집합의 합집합의 개수와 교집합의 개수를 구하는 문제다. 문제 풀이 소스코드 : C++ 문자열을 2글자씩 잘라주는 함수 makeArr 두 글자 중 하나라도 알파벳이 아니면 continue 두 글자 모두 소문자로 변환하고 sv에 담는다. 위 과정 반복 후 반환 변환한 두 벡터 모두 비어있다면 65536을 반환하고 종료 sv에 sv2를 복제한다. 만약 sv에 sv1 값을 찾을 수 있다면 -> 교집합, answer++ answer는 교집합의 개수이고 sv1 + sv2 - answer는 합집합의 개수이다. 교집합 / 합집합 * 65536을 반환한다. #include #include #include #include #in..

점프와 순간이동 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 설명 점프 : 1칸 이동 -> 1번당 베터리 1 소모 순간이동 : 현재까지 온 거리 $\times$ 2 위치로 이동 -> 1번당 베터리 소모 X 즉, 순간이동을 최대한 많이 해서 도착지점까지 도달하는 방법을 구하는 문제 Key Point 는 순간이동은 현재위치 $\times$ 2 까지 움직일 수 있다는 것이다. $$ \require{enclose} \begin{array}{r} 0\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,(J)\\ 1 \,\,\dots \..

실패율 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 설명 N개의 stage 에 대한 카운팅 정렬을 하고 stage에 대한 실패율 (스테이지에 도달했으나 아직 클리어하지 못한 플레이어의 수 / 스테이지에 도달한 플레이어 수) 을 구하는 문제다. 문제 풀이 소스코드 : C++ 카운팅 정렬을 위한 cnt[501] 배열을 전역변수와 전체 사용자 수 size = stage.size()를 선언한다. stages에 들어있는 값들을 카운팅 정렬한다. 이때 해당 값이 N+1인 값은 제외하고 정렬한다. (N+1은 모든 스테이지를 클리언 사용자) 실패율을 구하기위한 ..

오픈채팅방 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 설명 사용자의 id를 key값으로 가지며 사용자의 행동에 따라 변하는 결과를 출력하는 문제다. 이미지의 예시가 정확한 설명을 해주고 있다. 문제 풀이 소스코드 : C++ record에 기록된 행동들에 대해 split을 해주어 vector tmp 에 순서대로 담아준다. 명령에 따라 조건을 처리해준다. Enter 라면 id를 key값으로 하고 nickname을 value로 하는 unordered_map에 넣어주고 q에 {id , "님이 들어왔습니다."}를 푸시해준다. 이때 이미 존재하는 key라면..

징검다리 건너기 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 설명 건널 수 있는 사람 수를 기준으로 1 ~ max(stones) 에 대한 이분탐색을 하여 stones 값들을 mid 값 만큼 갂아 건널 수 있는지 확인하여 그 때의 최소값을 찾는 문제이다. 문제 풀이 소스코드 : C++ left =1 , right = stones의 최대값으로 초기화하고 이분탐색에 진입한다. mid = (left + right)/2로 놓고, 건널 수 있는 mid값보다 작거나 같은 경우를 세는 cnt=0 으로 놓는다. cnt>k되면 건널 수 없는 경우이므로 cnt>=k가..