[코딩테스트#1] 기초 자료 구조: 배열, 문자열, 스택, 큐

 

방학 계획 중 하나인 코딩테스트 공부 포스팅을 지속적으로 해보도록 하겠습니다 (근데 제가 생각한 방학이랑은 많이 다른 상황이라,, 요즘 프로젝트 다시 엄청해서 개인공부.. 따흑.. 그래도 할겁니다)

우선 한동안은 인강 들으면서 기초를 쌓고 그 이후에는 인강 + 백준으로 진행될 것 같습니다

인강에서도 예제로 백준을 풉니다

백준도 처음써봐서 적응중입니다. 첫 제 풀이 예제가 조금 이상할수도..

 

기초 중 기초인 자료 구조인데에도, 이렇게 공부하니 또 색다르고 정리가 딱 되는것 같아서 좋습니다

인강은 패스트캠퍼스 인강을 보고 있습니다.

저는 비전공자라 파이썬을 야매로? 배웠더니 인강이 너무 적절하고 만족스럽네요ㅎㅎ

나중에 쭉 다 보고 더 후기 남기겠습니다 (아직 전체 공개 안된 강의)

 

https://fastcampus.co.kr/dev_online_pythoncote

 

---

 

1. 배열 자료 구조 소개

• 배열
  • 수열을 저장할 때
  • 무언가 체크할 때
    • ex) 학습에서 출석 체크
    • a=[1, 1, 0, 1, 0]
    • (1) 출석한 총 학생 수 → 배열 총합
    • (2) 아직 출석 x 학생 파악→ 0인 인덱스
  • 무언가 카운트할 때
    • ex) 학급 반장 선거
    • a= [1, 1, 0, 2, 0]
    • (1) 가장 많은 표 → 값 최대 인덱스
    • (2) 총 투표 수 → 배열 총합
    • (3) 두 번째 많은 표
• 배열 사용 예제1
  • https://www.acmicpc.net/problem/5597

# 인강 풀이
# 체크 배열 사용
check = [0] * 31

for i in range(28):
    n=int(input())
    check[n]=1

answer=[]
for i in range(1, 31):
    if check[i]==0:
        answer.append(i)

print(answer[0])
print(answer[1])

 

• 배열 사용 예제2
  • https://www.acmicpc.net/problem/3052

# 내 풀이
# a="""39
# 40
# 41
# 42
# 43
# 44
# 82
# 83
# 84
# 85
# """

remain_list=[]

for i in range(10):
    #n=int(a.split("\n")[i])
    n=int(input())
    remains=n%42
    if remains not in remain_list:
        remain_list.append(remains)
print(len(remain_list))

# 인강 풀이
# 체크배열 사용
check = [0] * 42

for i in range(10):
    # n=int(input())
    n=int(a.split("\n")[i])
    check[n%42]=1

sum=0
for i in range(42):
    sum+=check[i]

print(sum)

 

 

 

2. 문자열 자료 구조 소개

• 배열과 크게 다르지 x
• “문장” 나누는 자료구조
• TIP
  • 예시) 문장에 나오는 알파벳의 개수 각각 알고 싶은 상황
  • “coding test”
  • a의 갯수?
  • count 배열 사용 시
    • 문자열별 인덱스 대응하는 함수가 필요함 (딕셔너리로 정의 필요)
    • a → 0인덱스 +1
    • b → 1인덱스 +1
  • 알파벳끼리 연산이 가능함
    • ‘b’ - ‘a’ =1
    • ‘z’ - ‘a’ = 25
    • 아스키 코드 간의 연산이 진행돼서 가능한 것
• 문자열 사용 예제1
  • https://www.acmicpc.net/problem/10809

# 인강 풀이
s=input()

check=[-1] * 26 #체크 배열

for i in range(len(s)):
    index=ord(s[i]) - ord('a') #아스키코드 변환

    if check[index]==-1:
        check[index]=i

for i in range(26):
    print(check[i], end=" ")

 

• 문자열 사용 예제2
  • https://www.acmicpc.net/problem/11720

# 내 풀이
n=int(input())
s=input()

sum=0
for i in range(int(n)):
    sum+=int(s[i])
print(sum)

# 인강 풀이
# 아스키코드 활용

n=int(input())
s=input()

sum=0
for i in range(n):
    sum+= ord(s[i]) - ord('0')
print(sum)

 

3. 스택 자료 구조 소개

• 자료구조: 데이터를 어떻게 저장하고, 관리할까 방법론
  • 단순히 저장 공간을 의미하는 것이 아님
  • 스택 & 큐: 데이터 추가/제거 어떤 규칙으로 할 것인가
• 스택Stack: LIFO (Last In First Out)
  • 마지막에 들어온 걸 우선해서 제거한다
  • 5 추가 → 4추가 → 3추가 → 3제거 → 4제거
• 스택 사용 예제1
  • https://www.acmicpc.net/problem/10773
  • 기록 → 추가
  • 기록 취소 → 제거 (마지막으로 한 기록을 지우기 → LIFO)

# 인강 풀이
k=int(input())

stack=[]

for i in range(k):
  n=int(input())

  if n==0:
    stack.pop(-1)
  else:
    stack.append(n)

sum=0
for e in stack:
  sum+=e

print(sum)

 

• 스택 사용 예제2
  • https://www.acmicpc.net/problem/4949

# 내 풀이
while True:
  s=str(input())

  if s==".":
    break

  else:
    stack=[]
    status=True
    for i in s:
      if i== "(" or i=="[":
        stack.append(i)
      elif i==")" and len(stack)!=0:
        if stack[-1]!="(" :
          print("no")
          status=False
          break 
        elif stack[-1]=="(":
          stack.pop(-1)
      elif  i=="]" and len(stack)!=0:
        if stack[-1]!="[" :
          print("no")
          status=False
          break
        elif stack[-1]=="[":
          stack.pop(-1)
      elif (i=="]" or i==")") and len(stack)==0:
        print("no")
        status=False
        break

  if status==False:
    pass
  else:
    if len(stack)!=0:
      print("no")
    else:
      print("yes")

# 인강 풀이
while True:
  s=input()
  if s==".":
    break

  stack=[]
  balanced=True

  for i in range(len(s)):
    if s[i]=='(' or s[i]=='[':
      stack.append(s[i])
    if s[i]==')':
      # stack이 비어있으면 안됨
      if len(stack)==0:
        balanced=False
        break

      last=stack.pop(-1)
      if last!="(":
        balanced=False
        break

    if s[i]==']':
      # stack이 비어있으면 안됨
      if len(stack)==0:
        balanced=False
        break

      last=stack.pop(-1)
      if last!="[":
        balanced=False
        break

  # 마지막에는 stack이 비어 있어야 함
  if len(stack)!=0:
    balanced=False

  if balanced==True:
    print("yes")
  else:
    print("no")

 

4. 큐 자료 구조 소개

• 스택과 비교 (둘 다 추가/제거)
  • 스택: 제거할 때 가장 마지막에 추가된 원소 제거(LIFO)
  • 큐: 제거할 때 가장 처음에 추가된 원소 제거(FIFO)
• 큐 사용 예제1
  • https://www.acmicpc.net/problem/18258
  • Deque 라는 라이브러리
  • sys.stdin.readline를 사용했는데
    • 빠르게 여러 줄을 입력받기 위해 사용. 아래글에 더 자세히 정리되어 있다.
    • https://velog.io/@yeseolee/Python-파이썬-입력-정리sys.stdin.readline
    • 근데 이는 주피터 노트북에서 작동하지 않는다 (코랩도 당연히)
      • 표준 입력을 받을 수 있는 콘솔이 없기 때문에 sys.stdin을 사용할 수 없다.

# 인강 풀이
import sys
from collections import deque

input = sys.stdin.readline
N=int(input())
d=deque([])

for i in range(N):
  command=sys.stdin.readline()
  command=command.split()

  if command[0]=="push":
    d.append(command[1])

  if command[0]=="pop":
    if len(d) == 0:
      print("-1")
    else:
      print(d.popleft()) # 빼는 동시에 print

  if command[0]=="size":
    print(len(d))

  if command[0]=="empty":
    if len(d) == 0:
      print("1")
    else:
      print("0")

  if command[0]=="front":
    if len (d) == 0:
      print("-1")
    else:
      print(d[0])

  if command[0]=="back":
    if len (d) == 0:
      print("-1")
    else:
      print(d[-1])

 

• 큐 사용 예제2
  • https://www.acmicpc.net/problem/2164

# 내 풀이
from collections import deque

d=deque([])

n=int(input())
for i in range(1, n+1):
  d.append(i)

while len(d)>1:
  d.popleft()
  move_card=d.popleft()
  d.append(move_card)

if len(d)==1:
  print(d[0])

# 인강 풀이
from collections import deque

N= int(input())
d=deque(list(range(1, N+1)))

drop=True

while len(d)>1:
  if drop:
    d.popleft()
    drop=False
  else:
    x=d.popleft()
    d.append(x)
    drop=True

print(d[0])