Chapter 01. 기본 자료구조

Chapter 01. 기본 자료구조(기초 문제풀이)

혼자 힘으로 풀어보기

음계: https://www.acmicpc.net/problem/2920

문제 제목: 음계
문제 난이도: 하(easy)
문제 유형: 배열, 구현
추천 풀이 시간: 15분

문제풀이 핵심 아이디어

1. 리스트에서의 원소를 차례대로 비교합니다.
2. 비교할 때 두 원소를 기준으로 오름차순/내림차순 여부를 체크합니다.

[초기상태 오름차순: True, 내림차순: True]

[초기상태 오름차순: True, 내림차순: False]

[초기상태 오름차순: False, 내림차순: False]

• 오름차순 및 내림차순이 모두 False이므로 'mixed'를 출력합니다.

소스 코드

a = list(map(int, input().split(' ')))

ascending = True
descending = True

for i in range(1, 8):
    if a[i] > a[i-1]:
        descending = False
    elif a[i] < a[i-1]:
        ascending = False

if ascending:
    print('ascending')
elif descending:
    print('ascending')
else:
    prinf('mixed')

혼자 힘으로 풀어보기

블랙잭: https://www.acmicpc.net/problem/2798

문제 제목: 블랙잭
문제 난이도: 하(easy)
문제 유형: 배열, 완전 탐색
추천 풀이 시간: 20분

문제 풀이 핵심 아이디어

1. 카드 중 3개씩 뽑는 모든 경우의수는 C(n,3)이며, n은 최대 100입니다.
2. 따라서 단순히 3중 반복분으로 모든 경우의 수를 확인하여 문제를 해결할 수 있습니다.

소스 코드

n, m = list(map(int, input().split(' ')))
data = list(map(int, input().split(' ')))

result = 0
length = len(data)

count = 0
for i in range(0, length):
    for j in range(i+1, length):
        for K in range(j+1, length):
            sum_value = data[i] + data[j] + data[k]
            if sum_value <= m:
                result = max(result, sum_value)

print(result)

기본 자료구조 (핵심 유형 문제풀이)

혼자 힘으로 풀어보기

스택 수열: https://www.acmicpc.net/problem/1874

문제 제목: 스택 수열
문제 난이도: 하(Easy)
문제 유형: 스택, 그리디
추천 풀이 시간: 30분

문제 풀이 핵심 아이디어

1. 스택에 원소를 삽입할 때는, 단순히 특정 수에 도달할 때까지 삽입하면 됩니다.
2. 스택에서 원소를 연달아 빼낼 때 내림차순을 유지할 수 있는지 확인합니다.

소스 코드

n = int(input())

count = 1
stack = []
result = []

for i in range(1, n+1):
    data = int(input())
    while count <= data:
        stack.append(count)
        count += 1
        result.append('+')
    if stack[-1] == data:
        stack.pop()
        result.appent('-')
    else:
        print('NO')
        exit(0)

print('\n'.join(result))

혼자 힘으로 풀어보기

프린터 큐: https://www.acmicpc.net/problem/1966

문제 제목: 프린터 큐
문제 난이도: 하(Easy)
문제 유형: 큐, 구현, 그리디
추천 풀이 시간: 25분

문제 풀이 핵심 아이디어

1. 데이터의 개수(N<=100)가 많지 않으므로, 단순히 문제에서 요구하는 대로 구현합니다.
2. 현재 리스트에서 가장 큰 수가 앞에 올 때까지 회전시킨 뒤에 추출합니다.
3. 가장 큰 수가 문서 M에 해당하면서 가장 앞에 있을 때 프로그램을 종료합니다.

소스 코드

test_case = int(input())

for _ in range(test_case):
    n, m = list(map(int, input().split(' ')))
    queue = list(map(int, input().split(' ')))
    queur = [(i, idx) for idx, i in enumerate(queue)]

    count = 0
    while True:
        if queue[0][0] == max(queue, key=lambda x: x[0][0]:
            count += 1
            if queue[0][1] == m:
                print(count)
                break
            else:
                queue.pop(0)
        else:
            queue.append(queue.pop(0))

혼자 힘으로 풀어보기

키로거: https://www.acmicpc.net/problem/5397

문제 제목: 키로거
문제 난이도: 중(Medium)
문제 유형: 스택, 구현, 그리디
추천 풀이 시간: 40분

문제 풀이 핵심 아이디어

1. 문자열 크기가 최대 1,000,000이므로 시뮬레이션 방식으로는 문제를 해결할 수 없습니다.
2. 스택을 활용하여 선형시간 문제를 해결할 수 있는 알고리즘을 설계합니다.

1) 스택 두 개를 만들고, 스택 두 개의 중간 지점을 커서(Cursor)로 간주합니다.
2) 문자 입력: 왼쪽 스택에 원소를 삽입합니다.
3) - 입력: 왼쪽 스택에서 원소를 삭제합니다.
4) < 입력: 왼쪽 스택에서 오른쪽 스택으로 원소를 이동합니다.
5) > 입력: 오른쪽 스택에서 왼쪽 스택으로 원소를 이동합니다.

소스 코드

test_case = int(input())

for _ in range(test_case):
    left_stack = []
    right_stack = []
    data = input()
    for i in data:
        if i == '-':
            if left_stack:
                left_stack.pop()
        elif i == '<':
            if left_stack:
                right_stack.append(left_stack.pop())
        elif i == '>':
            if right_stack:
                left_stack.append(right_stack.pop())
        else:
            left_stack.append(i)
    left_stack.extend(reversed(right_stack))
    print(''.join(left_stack))