제로베이스 20220325 모의 코테 결과 정리

2번 문제

문제 유형

• 탐색
• 그리디

접근법

• 배열 길이가 최대 200,000이고, k는 30000이므로 배열 전체의 조합을 따질경우 ${200000}C{30000}$까지 나올수 있으므로, 시간 초과될 가능성이 높음.

• 따라서 탐색 한번으로 마무리 지어야 한다.

• 탐색하는 매 시점마다 연속하는 최대 부분수열을 계산하여 update하는것이 핵심.

• 떨어진 두곳을 연결해봤자 최대 길이의 부분수열은 나올수 없기 때문에, 최대한 연속된 구간의 빈곳을 변경한다.

• 0인 부분을 발견하면 1로 바꿔주며 cnt를 올려주고, cnt가 k를 넘을때 이전에 변경했던것중 가장 앞의 변경을 취소하는 방식으로 진행한다.

3번 문제

문제 유형

• 스택
• 구현

접근법

• 괄호는 중첩될수 있으므로, 가장 안쪽 괄호부터 풀어주어야 한다.

• 닫는 괄호가 아닐때 일단 무조건 스택에 저장

• 닫는 괄호가 나오면 스택에서 데이터 pop

  • 여는 괄호가 나올때까지는 문자열로 저장
  • 여는 괄호가 나온다면 문자열 저장 종료.
  • 여는 괄호 이후 숫자가 나오지 않거나 , 스택 내부의 값이 없을때까지 pop하여 숫자로 인식

3번 문제

문제 유형

• 덱
• 구현

접근법

• 최소 갯수의 괄호를 제거하여 올바른 괄호문자열로 만들어야 함.

• isValid(s) : s가 올바른 괄호문자열인지 체크함.
  • 여는 괄호와 닫는 괄호의 개수가 일치하면 return True
  • 일치하지 않으면 return False

• 한번 체크한 문자열은 다시 체크하지 않도록 set안에 넣어 검사.

• 괄호를 하나 빼고 해당 문자열이 올바른지 검사하는것을 반복