🚶‍♂️Road to 코테(2) - 배열

본 게시물은 BaaarkingDog님의 실전 알고리즘 강의를 통해 공부한 것을 정리합니다.

[추가] 용감하게 시작하는 코딩테스트

[추가] 코딩 테스트 합격자 되기 - 파이썬 편

메모리 상에 원소 연속 배치 구조라 k번째 원소 위치를 바로 계산할 수 있다. 시간 복잡도는 O(1)
추가적으로 소모되는 메모리 양이 거의 없다.

맨 뒤가 아닌 임의의 위치에 원소를 추가하는 과정은 O(n). 원소를 추가하고 나머지 데이터들을 뒤로 한 칸씩 미뤄야하기 때문에.
예를 들어 그래프를 표현할 때 배열을 활용하면 임의 접근을 할 수 있으므로 간선 여부도 시간 복잡도 O(1)로 판단할 수 있\다. 하지만 배열은 메모리 공간을 충분히 확보해야 하는 단점도 있다.
임의 접근이라는 특징이 있어 데이터에 빈번하게 접근하는 경우 메모리 낭비가 발생 가능.

문제 1

정수 배열을 정렬해서 반환하는 solution( ) 함수를 완성하세요.
제약조건

• 정수 배열의 길이는 2 이상 105 이하입니다.
• 정수 배열의 각 데이터 값은 -100,000 이상 100,000 이하입니다.

from sys import stdin, stdout

def solution(arr):
  arr.sort()
  print(arr)
  
input = stdin.readline 
arr=list(map(int,input().split()))
solution(arr)

sort()는 시간 복잡도가 NlogN이다. 데이터 개수는 최대 105개이기 때문에, O(n2)인 버블 정렬을 사용할 수 없다.

문제 2

정수 배열을 하나 받습니다. 배열의 중복값을 제거하고 배열 데이터를 내림차순으로 정렬해서 반환하는 solution( ) 함수를 구현하세요.

제약조건

• 배열 길이는 2 이상 1,000 이하입니다.
• 각 배열의 데이터 값은 -100,000 이상 100,000 이하입니다.

from sys import stdin, stdout

def solution(arr):
  arr=list(set(arr))
  arr.sort(reverse=True)
  print(arr)
  
input = stdin.readline 
arr=list(map(int,input().split()))
solution(arr)

마찬가지로 sort()는 시간 복잡도가 NlogN이다. 데이터 개수는 최대 1000개이기 때문에, O(n2)인 버블 정렬을 사용할 수 없다.
set()함수로 O(n)의 시간 복잡도로 중복을 제거할 수 있다.

파이썬에는 코딩 테스트에 유용한 함수가 많다. 굳이 직접 작성하려 하지 마라

문제 3

정수 배열 numbers가 주어집니다. numbers에서 서로 다른 인덱스에 있는 2개의 수를 뽑아 더해 만들 수 있는 모든 수를 배열에 오름차순으로 담아 반환하는 solution( ) 함수를 완성하세요.

제약조건

• numbers의 길이는 2 이상 100 이하입니다.
• numbers의 모든 수는 0 이상 100 이하입니다.

from sys import stdin, stdout

def solution(arr):
  ans=[]
  for i in range(len(arr)):
    for j in range(i+1,len(arr)):
      ans.append(arr[i]+arr[j])
      
  ans=sorted(list(set(ans)))
  print(ans)
  
input = stdin.readline 
arr=list(map(int,input().split()))
solution(arr)

문제 4

수포자는 수학을 포기한 사람을 줄인 표현입니다. 수포자 삼인방은 모의고사에 수학 문제를 전부 찍으려 합니다. 수포자는 1번 문제부터 마지막 문제까지 다음과 같이 찍습니다.

• 1번 수포자가 찍는 방식 : 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, ...
• 2번 수포자가 찍는 방식 : 2, 1, 2, 3, 2, 4, 2, 5, 2, 1, 2, 3, 2, 4, 2, 5, ...
• 3번 수포자가 찍는 방식 : 3, 3, 1, 1, 2, 2, 4, 4, 5, 5, 3, 3, 1, 1, 2, 2, 4, 4,5,
  1번 문제부터 마지막 문제까지의 정답이 순서대로 저장된 배열 answers가 주어졌을 때 가장 많은 문제를 맞힌 사람이 누구인지 배열에 담아 반환하도록 solution( ) 함수를 작성하세요.

제약조건

• 시험은 최대 10,000 문제로 구성되어 있습니다.
• 문제의 정답은 1, 2, 3, 4, 5 중 하나입니다.
• 가장 높은 점수를 받은 사람이 여럿이라면 반환하는 값을 오름차순으로 정렬하세요.

from sys import stdin

def solution(answers):
  scores=[0]*3
  patterns=[
    [1,2,3,4,5],
    [2,1,2,3,2,4,2,5],
    [3,3,1,1,2,2,4,4,5,5]
  ]
  for i, answer in enumerate(answers):
    for j, pattern in enumerate(patterns):
      if answer==pattern[i%len(pattern)]:
        scores[j]+=1
  
  max_score=max(scores)
  result=[]      
  for i,score in enumerate(scores):
    if score==max_score:
      result.append(i+1)
  
  return result    

  
input = stdin.readline 
answers=list(map(int,input().split()))

solution(answers)

enumerate로 순회한다.