본문 바로가기

📊알고리즘112

BOJ 17299] 오등큰수 [ 접근법 ] - 오큰수 문제와의 차이점이라면 등장 횟수를 추가로 저장해야한다는 것이다. - 등장 횟수를 따로 저장하는 것 이외에 그대로 진행하면 된다. [ 주의 사항 ] - 등장횟수와 값을 저장하는 배열 두가지를 혼동하지 말자. - stack과 결과값에는 순서를 저장해두자! [ 코드 ] 더보기 #include #include #include #include #include using namespace std; stack s; int arr[1000001]; //num[i]의 등장횟수 int num[1000001]; //i번째 원소의 값 int res[1000001]; //v에는 오등큰수의 순서가 정리 int main() { ios_base::sync_with_stdio(false); cin.tie(NU.. 2022. 12. 15.
BOJ 17298] 오큰수 [ 접근법 ] - 오른쪽 수열에서 자신보다 큰 수중 가장 작은 값을 구하는 것이기 때문에 stack을 이용하자. - 하나하나 비교하는 o(n*n)는 수가 100000에 달하기 때문에 다른 방법을 모색해야 된다. - 왼쪽에 있는 수열의 오큰수는 무조건 오른쪽의 있는 수열보다 작거나 같다. - 그렇기 때문에 만약 다음 수열이 자신의 오큰수가 아니라면 stack에 저장해두고 다음 수열의 오큰수가 등장하면, 그때 stack을 pop하면서 해당 오큰수가 stack에 저장된 오큰수가 맞나 확인을 한다. - 만약 오큰수가 아니라면 -1을 저장한다. [ 주의사항 ] - 결과 저장배열에 수열 순서대로 저장해야 순서가 뒤죽박죽 되지 않는다. - 시간이 1초라고 해서 이중반복문이 등장하면 안되는 것이 아니다! - 마찬가지로.. 2022. 12. 15.
BOJ 1874] 스택 수열 [ 문제 이해 ] 입력 값 예) 3 5 1 2 4 - 1부터 n까지의 수를 순서대로 스택에 넣는다. (+출력) 스택 : 1 2 3 - 위를 하다 입력된 값과 같아지면 그 수를 스택에서 제거한다 (-출력) 스택 : 1 2 (3제거) 스택 : 1 2 4 (5제거) 이런 식으로... - 위 과정을 몇번해서 스택이 비워지고, 해당 수열이 완성되는 지 총 횟수를 출력한다 - 만약 위 과정을 진행하다 수열이 만들어지지 않으면 NO를 출력한다. [ 접근법 ] 1. 스택에 1부터 1씩 증가하면서 스택에 넣는다. 2. 입력받은 값이 스택의 top 과 같아지면 스택을 pop()한다. 3. 1,2 과정을 반복하다 스택이 비워지면 종료 4. 만약 위 과정 중 스택이 입력값이 스택의 topp()보다 크면 "NO" 를 출력하고 .. 2022. 12. 13.
BOJ 6198] 옥상 정원 꾸미기 문제 바로가기 접근법 하나의 빌딩은 오른쪽 방향에 있는 빌딩만 볼 수 있다. 한 방향으로만 진행되므로 스택을 이용하면 좋을 것 같다고 생각함. 1. 빌딩의 높이를 저장하는 스택(빌딩[])과, 순서를 저장하는 스택(시퀀스[]) 두가지를 이용한다. 2. 첫번째 입력값을 두가지 스택에 일단 푸쉬한다. 3. 두번째 빌딩의 높이가 주어지면, 빌딩 스택의 top과 비교한다. 3-1. 만약 top 입력값이면, 빌딩 스택과 시퀀스 스택 모두 저장한다. 4. 모든 데이터가 스택에 저장되서 끝나게 되면, 남은 스택의 개수 만큼 result를 증가시킨다. [코드 보기] 더보기 #include #include #include using namespace std; stack s; stack sequence; int main().. 2022. 12. 13.

티스토리툴바