chp5 배열(Array)

이 글은 골든래빗 <코딩 테스트 합격자되기 파이썬편>의 5장 써머리입니다.

 

[실전 문법]

list_name.insert(인덱스, 삽입할 값)    -> 해당 인덱스에 특정 값 삽입 후 해당 자리부터 나머지 하나씩 뒤로 이동

 

list_name.pop(인덱스)     -> 해당 인덱스 삭제. 인데스 미입력시 제일 뒤의 것 삭제

del list.name[인덱스 or A:B 슬라이싱]    ->  pop과 달리 del은 그냥 바로 삭제도 되고 범위 삭제도 가능.

list_name.remove(특정 값)   ->  특정 값을 삭제. 특정 값이 여러 개이면 가장 앞의 것 삭제

 

list_name.count(특정 값)   -> 특정 값이 리스트 내 몇 개인지 세기 (그렇지만 연산이 많으므로 사용 비추)

list_naem.index(특정 값)   -> 특정 값에 해당하는 인덱스  출력. 중복시 제일 처음 것만 출력

 

pythonic code: map함수쓰는 것보다 list comprehension을 사용하는 것을 권장

srt_A = list(map(str, A))  # 이것보다는
str_A = [str(a) for a in A]  # 이걸 사용

 

 

 

 

문제 1) 배열 정렬하기  (스터디용)

정수배열을 정렬하세요

def solution(arr):
    return sorted(arr)


arr1 = [1,-5,2,4,3]
arr2 = [2,1,1,3,2,5,4]
arr3 = [6,1,7]


def check():
    if solution(arr1) == [-5,1,2,3,4]:
        print(True)
    else:
        print(False)
    if solution(arr2) == [1,1,2,2,3,4,5]:
        print(True)
    else:
        print(False)
    if solution(arr3) == [1,6,7]:
        print(True)
    else:
        print(False)


check()

True
True
True

 

 

또는 

def solution(arr):
    arr.sort()
    return arr

이 문제에서 알아야할 것은 sorted()와 sort()의 차이점이다.

 

 

sorted(리스트)                        <-> list_name.sort()
원본은 유지하면서 새로 정렬 <-> 원본을 바꾸고 싶을 때

 

sorted(리스트)는 보통 새 변수에 정의해서 사용

새로운_변수 = sorted(리스트)

그런데 sorted()는 list()없이도 알아서 list()효과를 준다!  ~ 실패율(6번문제) 코드 연관

 

 

 

list_name.sort()는 다음과 같이 사용

list_name.sort() # 정렬 수행 1줄 작성 후

list_name # 해당 리스트  사용

 

바로 arr.sort()을 return에 삽입시 None이 출력되므로 작동이 안된다. arr.sort() 후에, arr을 호출해야 정렬된 리스트가 나온다. arr.sort()는 정렬만 수행하기에 반환값이 없다.

 

 

 

assert solution(arr1) == [-5,1,2,3,4], '출력값1 에러'
assert solution(arr2) == [1,1,2,2,3,4,5], '출력값2 에러'
assert solution(arr3) == [1,6,7], '출력값3 에러'

사실 check()를 원한다면 이렇게 쓰는게 간편할 수 있다.

 

 

 

 

 

 

 

문제 2는 기본문제라서 본문에서 생략.

 

 

 

 

 

 

 

문제 3) 두 개 뽑아서 더하기

임의 리스트에 대해서 두 수를 더한 값을 중복 없이 모두 나열

def solution(numbers):
    numbers.sort()
    answer = []
    for i in range(len(numbers)):
        for k in range(i+1, len(numbers)):  # i+1 유념!
            answer.append(numbers[i] + numbers[k])
    return list(set(answer))




N1 = [2,1,3,4,1]
N2 = [5,0,2,7]
print(solution(N1))  # [2,3,4,5,6,7]
print(solution(N2))  # [2,5,7,9,12]

 

중복 없이 for문을 사용해서 더하기 위해서

set개념도 사용하고

i와 안겹치기 위해서 k의 range의 시작부분을 i+1에 두었음에 유의한다!

 

 

 

*** set의 자료구조 특성상 해당 예제에 대해서 sort()없이도 정렬된 효과를 주지만,

set은 원소 배치 기준이 정렬이 아니므로 sort()를 적용하는 것이 안전하다!

print(set({1,5,2,3,7}))
print(set({2423,516,111,254324,11}))

{1, 2, 3, 5, 7}     <- 출력값이 정렬된 효과를 보이지만
{516, 254324, 2423, 11, 111}  <- 숫자가 커지면 그렇지 않음을 보여준다.

 

 

 

 

combination을 사용한 경우는 다음과 같다.

from itertools import combinations
def find_unique_sums(nums):
    nums.sort()
    unique_sums = set()

    for pair in combinations(nums, 2):
        sum_result = sum(pair)  # combi에 for문을 적용
        unique_sums.add(sum_result)  # add로 set에 추가한다.

    return list(unique_sums)

그런데 for문에 combi를 넣어서 딱히 좋아보이진 않는다.

 

단순 이중 for와 combi와 비교하면 기본적으로 O(N^2)이지만 combi가 조금 낫다고 한다.

 

 

 

 

 

combination을 대체한 사례

            index_combi = [A[i] for i in k]  
            # k = [인덱스 리스트] 이므로 A에 해당되는 인덱스만 넣은 리스트 형성
            index_combi.sort() 
            # 오름차순 정렬
            max_sum = index_combi[-1] + index_combi[-2] 
            # 정렬된 것 중 뒤의 것 2개(큰 값 2개)만 선택

3개이상의 원소를 지닌 리스트에 대해서 2개를 뽑아서 더한 것중에 최댓값을 구하는게 문제라면,

2개를 뽑는다는 점에서 combination을 생각할 수 있지만,

해당 리스트를 오름차순으로 정렬 후에 뒤의 것 2개(큰 값 2개)만 선택해서 더하면 불필요한 연산을 확실히 줄인다.

 

조합 시간 복잡도 O(N^2)    ->   대체한 시간 복잡도 O(N logN)    ; 정렬이 조금 걸려도 이정도면 ok

 

 

 

 

 

 

 

 

 

 

문제 4) 모의고사

https://school.programmers.co.kr/learn/courses/30/lessons/42840

프로그래머스

문제 요구사항: 가장 많이 맞힌 사람이 누구인지 하나만 출력. 여러명인 경우에만 오름차순 출력

 

 

 

내가 처음 쓴 답안

def solution(answers):
    l1 = [1, 2, 3, 4, 5] * len(answers) # 부족하지않게끔 길이 늘림
    l2 = [2,1,2,3,2,4,2,5] * len(answers)
    l3 = [3,3,1,1,2,2,4,4,5,5] * len(answers)
    count = [0, 0, 0] # 점수 계산
    for i in range(len(answers)):
        if l1[i] == answers[i]:
            count[0] += 1
        if l2[i] == answers[i]:
            count[1] += 1
        if l3[i] == answers[i]:
            count[2] += 1
    result = []
    max_score = max(count)   # 미리 최댓값 계산
    for idx, v in enumerate(count):
        if max_score == v: # 최댓값과 같으면 
            result.append(idx + 1) # 해당 인덱스 추가

    return result

 

이중 for문으로 구현하고 적용된 패턴의 주기 개념

def solution(answers):
    lst = [[1, 2, 3, 4, 5], [2,1,2,3,2,4,2,5], [3,3,1,1,2,2,4,4,5,5]]
    scores = [0] * 3
    for i, answer in enumerate(answers):
        for j, ls in enumerate(lst): # 여기서 ls는 lst의 각 리스트
            if answer == ls[i % len(ls)]: 
     # 개념: [i % (패턴의 주기)]번째 패턴, 패턴의 주기 = 패턴의 길이
                scores[j] += 1
    max_s = max(scores)
    result = []
    for i, score in enumerate(scores):
        if score == max_s:
            result.append(i+1)
    
    return result

 

 

 

 

 

 

문제 5) 행렬의 곱셈

https://school.programmers.co.kr/learn/courses/30/lessons/12949

프로그래머스

내가 처음 쓴 답안

def solution(arr1, arr2):
    arr1_row = len(arr1)
    arr1_col = len(arr1[0])
    arr2_col = len(arr2[0])
    answer = [[0] * arr2_col for _ in range(arr1_row)]
    for i in range(arr1_row):
        for j in range(arr2_col):
            for k in range(arr1_col):
                answer[i][j] += arr1[i][k] * arr2[k][j]

    return answer

 

책의 답안(행과 열을 깔끔하게 정의하고 행렬 정의대로 구현)

def solution(arr1, arr2):
  # ➊ 행렬 arr1과 arr2의 행과 열의 수
  r1, c1 = len(arr1), len(arr1[0])
  r2, c2 = len(arr2), len(arr2[0])
  
  # ➋ 결과를 저장할 2차원 리스트 초기화
  ret = [[0] * c2 for _ in range(r1)]

  # ➌ 첫 번째 행렬 arr1의 각 행과 두 번째 행렬 arr2의 각 열에 대해
  for i in range(r1):
    for j in range(c2):
      # ➍ 두 행렬의 데이터를 곱해 결과 리스트에 더해줌
      for k in range(c1):
        ret[i][j] += arr1[i][k] * arr2[k][j]
  return ret

 -> 행1 열1 행2 열2 일때, 열1과 행2의 숫자가 같고 행1과 열2가 행렬의 크기가 된다.

2차원 배열에서 for문(r1)은 행을 형성.  단순 곱(c2)는 열을 형성

 

 

 

 

 

 

문제 6) 실패율 (카카오 2019)

https://school.programmers.co.kr/learn/courses/30/lessons/42889

프로그래머스

목적: 스테이지별 실패율을 내림차순으로 나열한 것을 스테이지 번호로 출력하기
stages 원소 = 게임 내 사용자가 멈춰있는 스테이지 번호
결국 각 스테이지당 몇 명인지 세는 과정 = count가 필요
실패율의 분자 = count의 원소  / 실패율의 분모 = 전체 스테이지 개수 - 현재 count 기준 이전 count 분자 합

def solution(N, stages):
    count = []  # 각 stage당 몇명이 있는지 재정의하는 리스트
    for i in range(1, N+1):   
        count.append(stages.count(i)) # stage 1부터 유저 수 저장
        
    fail = [] # 실패율 리스트
    total = len(stages) # 전체 스테이지 개수. total은 실패울의 분모값
    for j in range(len(count)):
        if j == 0: # 첫 번째 값은 total이 분모로 온전히 들어감
            fail.append(count[j]/total)
        elif j > 0: # 두 번째 값부터 total이 0이 아닌 조건 필요
            total -= count[j-1] # 분모 차감 누적
            if total != 0:  # 0이 아니라면
                fail.append(count[j]/total) # 값 추가
            else:  # 0이면
                fail.append(0)  # 0을 추가
        else:  # 위의 조건을 벗어나면 무조건 0으로 처리
            fail.append(0) 
    # 스테이지 이름 : 실패율로 dict 정의
    ndict = {key + 1 : value for key, value in enumerate(fail)}
    # ndict에서 key값만 뽑고, 내림차순 value값으로 list 형성 = answer
    answer = sorted(ndict, key=ndict.get, reverse=True)
    # sorted()는 list()가 없어도 형식이 맞다면 list()를 적용해서 출력한다.
     
    return answer

 

 

문제 풀이에 성공은 하였으나 몇몇 테스트 케이스에서는 1000ms를 넘는(5, 23) 등, 효율성이 좋지 못하다.

효율성측면에서 코드를 잘 구현하면 모두 50이하로 나올 수 있다.

 

 

 

 

 

 

효율성이 매우 좋은 책의 답안

def solution(N, stages):
  # ➊ 스테이지별 도전자 수를 구함
  challenger = [0] * (N + 2)
  for stage in stages:      # stages값의 원소를 challenger의 인덱스로 받아서
    challenger[stage] += 1  # 해당 인덱스의 값에 += 1하는 것. (count보다 효율적!)
# 계수정렬 개념과 연관있다고 한다.


  # ➋ 스테이지별 실패한 사용자 수를 계산
  fails = { }  # dict형태로 정의되었음에 유의한다!
  total = len(stages) 
  
  # ➌ 각 스테이지를 순회하며, 실패율을 계산
  for i in range(1, N + 1):  # challenger의 0번째 인덱스는 사용안하므로 1부터 N+1 설정 유의!
    if challenger[i] == 0 : # ➍ 도전한 사람이 없는 경우, 실패율은 0
      fails[i] = 0  # 실패율의 해당 인덱스 key i에 해당하는 실패율(value)는 0으로 업데이트
    else:
      fails[i] = challenger[i] / total # ➎ 해당 인덱스 i(key)에 해당하는 실패율(value) 정의
      total -= challenger[i] # ➏ 다음 스테이지 실패율을 구하기 위해 현재 스테이지의 인원을 뺌
  
  # ➐ 실패율이 높은 스테이지부터 내림차순으로 정렬
  result = sorted(fails, key=lambda x : fails[x], reverse=True)
  # fails[x]는 x라는 key에 해당한s value값을 호출한다.
  # sorted()는 list()가 없어도 형식이 맞다면 list()를 적용해서 출력한다.
  
  return result

 

1000이 넘은 기존의 것과 달리 높아야 5.37ms로 매우 수월하게 연산되고 있다.

 

 

 

 

 

 

 

 

 

 

 

 

 

문제 7) 방문 길이

https://school.programmers.co.kr/learn/courses/30/lessons/49994

프로그래머스

혼자서 못풀고 힌트보고 다른 사람 풀이 보면서 내가 보기 쉽게 정리한 버전이다.

# 목적 : 움직인 거리 중복 제외하고 측정
# dirs: 움직이는 방향. 밖을 벗어나면 무시됨
# [0,0]은 [5,5]로 바꾸어 음수 좌표를 대체 可
# 그러나 음수좌표를 그대로 활용하는 방법도 可
# 주의점: 점(좌표)가 아니라 지나온 길(선분)을 체크해야함

def solution(dirs):
    move = {'U':(0,1), 'D':(0,-1), 'L':(-1,0), 'R':(1,0)}  # 상하좌우 dict, tuple로 저장
    visited = set()  # 중복을 제거하는 set 설정
    x, y = 0, 0
    for step in dirs:
        nx, ny = x + move[step][0], y + move[step][1] #nx, ny 값 갱신
        go = (x, y, nx, ny)  # 내가 가는 것
        back = (nx, ny, x, y) # 반대로 오는 경우도 같은 의미(지나온 거리 체크 위함)
        if -5 <= nx <= 5 and -5 <= ny <= 5: # nx,ny가 범위 안에 있으면
            x, y = nx, ny # x,y 값 갱신
     #       if go not in visited and back not in visited:
     # 이걸 위에 조건문에 같이 걸면 중복 이동을 안하게되므로 오작동을 일으킴.
     # 여기서 중복 이동은 可, 중복이동한 거리를 포함시키지 않을 뿐.
     # 이 조건을 if로 따로 두고 visted.add를 넣을 수도 있지만 없어도 큰 상관은 없음
            visited.add(go)
            visited.add(back)  # 지나온 거리를 set에 기록
    return len(visited) // 2 
    # 1 step당 거리가 2개씩 기록되었으므로 전체 길이에서 2를 나누면 거리값이 나옴
    # d를 따로 설정할 필요가 없다!

 

[이 문제에서 배운 것]

• dict와 tuple로 한번에 상하좌우 정의를 할 수 있다. 매일 써먹어야할듯!
• nx, ny값을 갱신하는 식을 유의한다.(dict, tuple 호출)
• 자동 중복 제거를 위해서 set()과 set.add등을 사용할 수 있다.
• 좌표가 아닌 지나온 거리를 기록하기 위해서는 (x, y, nx, ny), (nx, ny, x, y)를 같이 add해서 기록한다.
  좌표쌍을 저장하는 것이 포인트!
• 이런 방식으로 기록된 set의 경우, set 전체 길이를 2로 나누면 d의 값이 나온다.

 

 

책의 답안

def is_valid_move(nx, ny) : # ➊ 좌표를 벗어나는지 체크
  return 0 <= nx < 11 and 0 <= ny < 11
 
def update_location(x, y, dir) : # ➋ 좌표 반영
  if dir == 'U':
    nx, ny = x, y + 1
  elif dir == 'D':
    nx, ny = x, y - 1
  elif dir == 'L':
    nx, ny = x - 1, y
  elif dir == 'R':
    nx, ny = x + 1, y
  return nx, ny

def solution(dirs):
  x, y = 5, 5 # [0,0]을 대체함
  ans = set( ) # ➌ 겹치는 좌표는 1개로 처리하기 위함
  for dir in dirs : # ➍ 주어진 명령어로 움직이면서 좌표 저장
    nx, ny = update_location(x, y, dir) # nx, ny 추출
    if not is_valid_move(nx, ny) : # ➎ 벗어난 좌표는 인정하지 않음
      continue
    # ➏ A에서 B로 간 경우 B에서 A도 추가해야 함(총 경로의 개수는 방향성이 없음)
    ans.add((x, y, nx, ny))
    ans.add((nx, ny, x, y))
    x, y = nx, ny # ➐ 좌표를 이동했으므로 업데이트
  return len(ans)/2

 

 

 

 

 

 

 

 

 

 

 

 

 

 

책의 추가문제 중, 다뤄야하는 문제: n^2배열 자르기

https://school.programmers.co.kr/learn/courses/30/lessons/87390

프로그래머스

# 1차원 배열 만드는 조건을 먼저 구한다.
# mtx는 해당 행까지는 해당 행 숫자, 그 이후로는 +1된다.
def solution(n, left, right):
    mtx = [[1] * n for _ in range(n)]
    # mtx 값 채우기 (규칙찾아 구현하기)
    for i in range(n):
        for j in range(n):
            if i == j:
                mtx[i][j] = i + 1
            elif i > j:
                mtx[i][j] = i + 1
            elif i < j:
                mtx[i][j] = j + 1
                
    # 1차원으로 나열하기
    mtx_one = [] 
    for i in mtx:
        mtx_one += i
    answer = mtx_one[left:right+1]
    
    return answer

시간초과된 코드이다. 2차원 배열을 소환하지말고 1차원 list를 바로 생성이 가능하도록 구현해야한다.

 

규칙을 생각하면

1234 2234 3334 4444니까 규칙이 있다.

 

 

'''
3x3 행렬일 때
(1,1) = 1 (1,2) = 2 (1,3) = 3
(2,1) = 2 (2,2) = 2 (2,3) = 3
(3,1) = 3 (3,2) = 3 (3,3) = 3
간단하게 각 좌표 x, y 값중 큰 값이 해당 값이 됩니다.
이제 주어지는 left ~ right 1차원 index 값을, 2차원 인덱스(x, y) 값으로 변환만 하시면 되겠네요?
'''
def solution(n, left, right):
    answer = []
    # mtx에서 row, col위치가 큰 값이 value가 됨
    for i in range(left, right + 1): # 문제 해당부분만 배열 생성
        row = i // n  #  n값이 지나야 구분되니 몫 개념 사용
        col = i % n # n값으로 나눈 나머지가 패턴의 순서를 짚음
        max_val = max(row, col) # 큰 값이 value인 규칙 적용
        answer.append(max_val + 1) # 0부터 index 시작하였으므로 +1 추가

    return answer

4번문제에 나온 패턴의 주기개념을 여기서 활용하고 있다.

몫개념(1개의 사이클)과 나머지 개념(하나하나 원소)을 기억하자

 

 

 

 

 

 

---

그 외

 

walrus operator (바다코끼리 연산자 :=)

if, for, while 구문 내에 변수 선언 및 할당을 할 때 사용한다.

 

A = 1
if A == 2:
    print(True)

로 A의 변수 할당을 if문 전에 선언했다면

 

 

if (A := 1) == 2:
    print(True)

이렇게 if문 내에 바로 A의 값을 정하고, 그 값과 2를 비교할 수 있다.

 

:=는 반드시 ( )안에 사용해서 식의 혼동을 방지해야한다. 단, 단순히 True, False를 검증하는 상황이라면 생략 可

 

 

 

그래서 list comprehension에 이런식으로 응용이 가능하다.

li = [(end:=i) if i else (start:=i) for i in range(10)]