가사 검색 코딩테스트 연습 - 가사 검색 programmers.co.kr 문제 설명 주어지는 words의 단어들을 quries로 찾아내는 문제. quries에는 '?'라는 와일드 카드가 존재하고 ?는 모든 문자에 해당한다. 입출력 예 문제를 보자마자 Trie로 풀어야겠다는 생각에 예전 기억을 떠올리며 Trie 자료 구조를 이용하여 문제를 풀었지만, 효율성 테스트에서 막혔다. 가사검색 풀었던 친구에게 물어보니 reverse trie를 만들어서 해결하라는 말을 듣고, 문제를 통과했다. 문제 풀이 소스코드 : C++ Trie 를 이용한 풀이 #include #include #include #include using namespace std; int cnt; class Trie{ public: Trie *chi..

기둥과 보 설치 문제 설명 구현 문제이다. 머릿속으로 구현은 나름 빠르게 됐는데 코드로 옮기면서 조건을 한 두개씩 빼먹어서 시간이 오래걸렸다. 시험이 아닌데도 3시간씩 걸려서 푸는데.. 언제 이런문제를 1시간 안에 풀 수 있을까... 기둥과 보가 설치될 수 있는 조건을 명확하게 해결하여야한다. 설치할 때는 해당 위치에 기둥과 보가 설치될 수 있는지 확인하고, 삭제할 때는 삭제를 시킨 후 모든 구역에 대해 기둥과 보가 설치 할 수 있는지 없는지 확인한다. 문제 풀이 소스코드 : C++ 해당 좌표에 기둥과 보가 설치 되어있는지 확인하는 구조체 POS Map[101][101]을 선언한다. 우선 해당 좌표에 기둥과 보를 설치할 수 있는지 확인하는 두 함수 chk_pillar와 chk_beam을 구현한다. chk..

실패율 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. 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가..

호텔 방 배정 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 설명 을 이용하여 주어진 호텔 방 번호를 맵의 key 값으로 생각하여 방 배정을 하고 다음 방 번호를 value 로 받아 방을 배정 받을때마다 다음 방 번호를 갱신하여 준다. 자료구조 trie 에서 착안하였다. 문제 풀이 소스코드 : C++ 손님이 원하는 방 번호가 담겨있는 room_number 를 key 로 받고 해당 key 가 없으면 unordered_map m에 insert({배정 받은 방번호, {배정 받은 손님 , 다음 방 번호}})해준다. 이 때 다음 방 번호는 배정 받은 방 번호..

불량 사용자 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 설명 user_id 중에서 banned_id의 조건에 맞는 원소를 뽑는 조합 문제다. 단, banned_id의 조건에 맞는 원소를 뽑을 때 중복이 생길 수 가 있는데 이 중복을 피하는게 키포인트 인 문제이다. 백트래킹을 이용한 조합을 구현하고 ``을 이용하여 중복을 제거했다. 문제 풀이 소스코드 : C++ user_id를 사용 여부를 체크하기위한 vector chk를 user_id 사이즈 만큼 할당해준다. 백트래킹을 이용한 조합구현 process()를 진행한다. uid가 사용한 적이 없고 b..

튜플 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 설명 주어지는 s 원소들의 정보를 스플릿 하여 어떤 순서를 따르는 튜플을 찾아내는 문제이다. 즉, 주어지는 s에 있는 튜플들은 최종 순서와는 상관없이 주어지는데 이 튜플들의 원소 수가 작은 튜플부터 나열하여 최종 튜플의 순서를 찾아내면된다. 문제 풀이 소스코드 : C++ 우선 주어지는 s의 맨 처음과 끝은 각각 {, }이므로 1 ~ s.size() - 1까지 탐색한다. {이면 하나의 튜플이 시작하는 시점이므로 튜플이 시작하는 지점을 의미하는 chk를 true로 바꿔주고 스플릿 하여 담아줄 이차원 벡..