3주차 문제풀이 정리

• 회전 초밥(박재훈)

  • 입력된 모든 초밥을 슬라이스의 첫 번째요소로 만들고 그 슬라이스(K개)에 대해 조사(나머지 연산 사용)
  • N = 3,000,000
  • K = 3,000
  • N*K = 9,000,000,000 ⇒ O(N^2)으로는 풀 수 없음
  1. 모든 초밥의 개수를 담을 수 있는 counting 배열 생성
     1. 쿠폰 번호는 무조건 추가되어야 하기 때문에 처음부터 counting 배열에 1을 넣어주고 시작
  2. 다음 슬라이스를 넘어가면서 (인덱스를 1씩 늘려주면서) max count 갱신
  • 가장 왼쪽에 있던 초밥의 개수를 1 감소
  • 새로 먹는 초밥에 대해서 그 초밥의 개수를 1 증가
  • 현재 슬라이스의 countring 값을 max 값과 비교

• 내려가기(이찬민)

  • N = 1 : 는 배열의 최대, 최소를 리턴

  • N > 1

    • 새로운 1차원 배열 2개(최대값, 최소값)를 새로 만들어 준다
      • N번 row에 대해
        • 새로운 배열의 0번째 인덱스에 N-1번 row의 0,1번 인덱스의 최대, 최소를 더해줌
        • 새로운 배열의 1번째 인덱스 : N-1번 row의 0,1,2번 인덱스의 최대, 최소를 더해줌
        • 새로운 배열의 2번째 인덱스 : N-1번 row의 1,2번 인덱스의 최대, 최소를 더해줌
    • 최대값 배열의 최대값을 max로
    • 최소값 배열의 최소값을 min으로
    • max와 min을 리턴

  • padding : 원래 배열의 맨 첫번째 row를 (0,0,0)으로 준다면

  • N == 1일때 를 따로 나누지 않아도 된다.

• 세 용액(김주현)

  • first값을 기준으로 그 뒤의 요소에 대해 두 용액 풀이를 적용
  • 두 용액 풀이
    • 입력된 배열을 오름차순으로 정렬한다 → 왼쪽은 음수, 오른쪽은 양수가 됨
    • leftIndex = 가장 왼쪽 요소를 가리키는 포인터
    • rightIndex = 가장 오른쪽 요소를 가리키는 포인터
    • 두 포인터가 가리키는 원소끼리 더하여 두 수의 합이 0에 가깝도록 두 포인터를 업데이트해 나간다.
      • 두 수의 합이 0보다 작다면 더 커져야하기 때문에 leftIndex를 증가
      • 두 수의 합이 0보다 크다면 더 작아져야하기 때문에 rightIndex를 감소
        • |(두 수의 합)|이 기존의 합보다 더 작다면 min값을 업데이트
          • 만약 0이 나왔다면 break.
      • 0이 나오거나 (rightIndex - leftIndex = 1)일때 까지 양쪽 인덱스를 옮겨가며 해답을 찾는다.

• 암호화된 비밀번호

  • 배열 생성

    • 평문의 알파벳 개수 배열
    • 슬라이스된 문자의 알파벳 개수 배열

  • 슬라이스 크기 : 평문의 길이

  • 다음 슬라이스를 넘어가면서 (인덱스를 1씩 늘려주면서

  • 슬라이스된 문자의 알파벳 개수 배열에서,

    • 가장 왼쪽에 있던 문자의 개수를 1 감소
    • 새로 추가되는 문자의 개수를 1 증가

  • 매 슬라이스 마다 평문의 알파벳 개수 배열과

  • 슬라이스 된 문자의 알파벳 개수 배열을 O(N)의 시간복잡도로 비교(각 알파벳의 개수가 같은지)

  • 같으면 슬라이싱 중단하고 “YES” 리턴

  • 끝까지 같지 않으면 “NO” 리턴

• 귀여운 라이언(이찬민) - 추가

  • 슬라이드 윈도우의 사이즈를 점차 줄여나가며 해결하는 것이 포인트

  • 처음으로 1을 만나는 인덱스를 startIndex라고 하고

  • K번째 1을 만나는 인덱스를 endIndex라고 하여

  • 첫 슬라이드의 크기를 (endIndex - startIndex+1)로 지정하여

  • [end+1, (list의 길이)) 범위를 탐색

  • 만약 현재 슬라이드의 양쪽 끝이 1이라면, startIndex가 1을 만날때까지 증가시켜줌

  • 아니라면 [end+1+1, (list의길이)+1) 범위를 재탐색

  • 결국 슬라이드 크기를 줄여주어 슬라이드 크기의 최소값을 리턴하여 해결한다