OR 연산을 사용할 수 있는지 묻는 문제이다.
주의할 점 : | 연산 결과를 #과 ' '의 문자열로 만들 때,
문자열의 길이가 주어진 arr의 길이보다 작을 경우 문자열의 앞에 ' '를 추가해야한다
ex) 4 = 000100(2) = '()()()#()()' (arr의 길이가 6인 경우)
문제 설명을 이해하는데 시간이 좀 걸렸던 문제인데 그냥 문제의 조건대로 구현만 하면되는 문제였다.
여러 구현 방법이 있겠지만 문자를 어떻게 잘라서 구현할까 생각하다 "스택에 넣고 빼고하는 방식" 으로 구현했다.
주의할 점은 점수가 10점인 경우도 있으므로 char단위로 자를 때 10인지 아닌지 검사하는 과정이 필요하다.
(10인 경우 인덱스를 한 칸 더 옮겨줌)
LRU(가장 사용한지 오래된 페이지부터 교체)를 구현하는 문제였다 (포인트는 2가지)
1. LRU를 구현하는 것 (벡터로 구현)
* 주의할 점 : 캐시 히트한 경우 해당 데이터를 지워주고 벡터의 가장 뒤에 다시 재삽입하는 과정이 필요하다.
2. 대소문자 구분 없이 비교하는 것 : 모든 문자를 대문자로(혹은 소문자로) 변환한다.
따로 다른 자료구조를 사용한다는 생각을 못하고 string 처리만으로 구현을 시도했는데 실패했다.
직전 버스에 타야할 인원이 m보다 많아서 남아있는 경우 뒷버스로 넘어가게 되는데
이걸 처리하기 번거로워서 결국 처음 시도한 이 방법은 실패했다.
구현 설명 (성공)
블로그들을 참고해서 priority queue를 사용하여 구현했다.
1. 모든 시간을 분단위로 변환한다.
2. pq에 시간대 빠른순으로 정렬하여 삽입한다.
3. 막차 직전 셔틀까지 t(셔틀 도착간격)시간 간격마다 크루들을 태운다.(pq에서 꺼낸다)
4. 마지막 셔틀에서 m-1명까지 우선 처리한다.
5. if : pq가 비었거나(남는 자리가 있거나), 나머지 크루들이 모두 막차보다 늦게온다면
정시에 도착해서 타도록한다.
else : 더 탈 수 있는 크루가 남아 있다면, 해당 크루보다 1분 일찍 온다.
6. 분단위로 변환된 시간을 string 시간으로 바꿔서 반환한다.
깨달은 점
1. compare 함수 작성 시 compare(a, b)에서, a와 b의 값이 동일한 경우 false로 처리하지 않으면 에러가 발생함
2. 시간과 관련된 문제를 처리할 때 낮은 단위로 변환하여 처리하는게 편함
c++ stl의 set관련 함수를 사용하여 구현했다
C++의 set 함수로 문제에서 요구하는 "중복을 허용하는 다중집합"을 구현할 수 있기 때문에
set_union과 set_interaction을 사용하여 쉽게구현했다.
ex)
set_union 함수가 완전 중복 원소를 하나만 가지는건 아니고
vec1이 {1,1,2} vec2가 {1,1,1,3}이면
union = {1,1,1,2,3} 이렇게 됨 (중복된 다중 원소는 더 개수가 많은 쪽을 선택?)
입력 값이 최대 30X30으로 작기 때문에 완전탐색으로도 충분히 해결할 수 있는 문제였다.
삭제하고 블럭들을 밑으로 내려주는걸 어떻게 구현할까 고민했는데 (벡터로 하나하나 내려주는건 번거롭다고 생각했다)
삭제한 블럭들을 제외하고 스택에 담은 뒤, 나머지부분을 삭제한 블록으로 채우고,
스택의 값을 다시 벡터에 넣는 식으로 구현했다.
1. 블럭 string 벡터를 //<블록캐릭터, 삭제유무> 쌍의 벡터로 만든다 (삭제되면 true, 삭제되지 않았으면 false)
2. 완전탐색을 진행하며 제거할 수 있는 블럭을 체크하고, 제거할 수 있는 블럭의 수를 반환한다.
3. 제거할 수 있는 블럭 수가 0이상이면 블럭을 제거하고 아래로 내려준다. (stack 이용)
4. 2번으로 되돌아가고 제거할 수 있는 블럭의 수가 0일때까지 반복한다.
//블럭을 제거하고 아래로 내려준다.voideraseBlock(vector<vector<pair<char, bool>>>& board, int height, int width) {
stack<pair<char, bool>> s;
for (int x = 0; x < width; ++x) {
//삭제되지 않을 블럭을 아래부터 순서대로 스택에 채운다for (int y = height - 1; y >= 0; --y) {
if (!board[y][x].second)
s.push(make_pair(board[y][x].first, false));
}
//나머지부분을 모두 삭제된 블럭으로 채운다while (s.size() != height)
s.push(make_pair('', true));
//다시 board에 넣어준다. for (int y = 0; y < height; ++y) {
board[y][x] = s.top();
s.pop();
}
}
}
감이 안잡혀서 설명을 보고도 한참을 해맸던 문제이다
문제 해설에서 보면 요청량이 변하는 순간은 각 로그의 시작과 끝이라고 나온다.
이를 이용해서 각 로그의 시작 ~ 시작+1초 , 끝 ~ 끝+1초 부분의 요청량을 검사하여 최대값을 찾아내는 문제이다.
point :
1. 시간을 정수 단위로 변환할 것(0.001ms : 1 로 변환)(실수로 계산하면 오차가 발생함)
2. log를 시작시간이 빠른 순으로 정렬한다.
3. 해당구간에 실행중인게 있는지 확인하는 조건
3번조건을 못세워서 계속 실패했었다..