태야

https://www.acmicpc.net/problem/9375

import sys

input = sys.stdin.readline

N = int(input().rstrip())
for _ in range(N):
    M = int(input().rstrip())
    clothes = {}

    for _ in range(M):
        (item, cloth_type) = list(input().rstrip().split())
        clothes[cloth_type] = clothes.get(cloth_type, 0) + 1

    result = 1
    for count in clothes.values():
        result *= (count + 1) #해당 종류의 의상을 선택하지 않는 경우 포함

    print(result - 1) # 아무 옷도 안 입는 경우 제외

의상 타입별 고르지 않는 경우도 카운트하는게 중요하다.

https://www.acmicpc.net/problem/11478

1번째 풀이 - O(N^2)

import sys

input = sys.stdin.readline

S = input().rstrip()

for i in range(len(S)):
    if S[i] in result:
        result[S[i]] += 1
    else:
        result[S[i]] = 1

    if i == len(S) - 1:
        break

    current_string = S[i]

    for j in range(i + 1, len(S)):
        current_string = current_string + S[j]
        if current_string in result:
            result[current_string] += 1
        else:
            result[current_string] = 1

print(len(result))

시간복잡도 O(n^2)이 걸리는 풀이로 작성했다. 해당 코드를 python의 set 자료형을 활용하면 간단하게 작성할 수 있다. 

python set() 활용 풀이 - O(N^2)

import sys

input = sys.stdin.readline

S = input().rstrip()

result = set()

for i in range(len(S)):
    for j in range(i + 1, len(S) + 1):
        result.add(S[i:j])
print(len(result))

set(집합) 자료형은 집합의 중복을 제거하고 순서를 보장하지 않는 리터럴 객체를 생성한다.

https://www.acmicpc.net/problem/1158

1차 풀이

from collections import deque
import sys
input = sys.stdin.readline
[N, K] = list(map(int, input().strip().split()))

def get_answer():
    numbers = deque(range(1, N+1, 1))
    deleted_numbers = []

    i = -1
    count = 0
    while len(deleted_numbers) != N:
        i += 1

        if i >= N:
            i = 0

        if numbers[i] not in deleted_numbers:
            count += 1
            if count == K:
                count = 0
                deleted_numbers.append(numbers[i])
                continue
    return "<" + ", ".join(map(str, deleted_numbers)) + ">"

print(get_answer())

문제점

- 효율성 문제

• 삭제 여부 확인 방식:
  코드에서는 원래의 numbers 데크에서 값을 제거하지 않고, 별도의 deleted_numbers 리스트에 추가한 후, 매번 if numbers[i] not in deleted_numbers:로 삭제 여부를 확인한다. 이 방식은 리스트의 멤버십 검사가 O(n) 시간 복잡도를 가지므로, N이 5000과 같이 큰 경우 불필요하게 많은 연산을 수행하게 되어 성능 문제가 발생할 수 있다.
• 불필요한 자료구조 사용:
  데크(deque)를 선언해두었지만, 데크의 효율적인 회전(rotate) 기능이나 popleft() 등을 활용하지 않고 단순히 인덱스 접근 방식으로 사용하고 있습니다

개선된 코드

from collections import deque
import sys
input = sys.stdin.readline
[N, K] = list(map(int, input().strip().split()))

def get_answer():
    dq = deque(range(1, N+1, 1))
    result = []

    while dq:
        for _ in range(K - 1):
            dq.append(dq.popleft())
        result.append(dq.popleft())


    return "<" + ", ".join(map(str, result)) + ">"

print(get_answer())

개선 효과

- 매번 불필요한 인덱스 접근이나 멤버십 검사를 하지 않아 시간 복잡도를 O(N)으로 줄일 수 있다.

Python rotate 메서드 활용 코드

from collections import deque
import sys

input = sys.stdin.readline
N, K = map(int, input().split())
dq = deque(range(1, N + 1))
result = []

while dq:
    dq.rotate(-(K - 1))  # K-1번 왼쪽으로 회전
    result.append(dq.popleft())

print("<" + ", ".join(map(str, result)) + ">")

요세푸스 문제는 원형 구조를 활용해 특정 규칙에 따라 요소들을 제거하는 시뮬레이션 문제인데, 그 개념 자체는 원형 연결 리스트 (circular linked list)와 매우 유사하다.

주요 포인트

• 원형 연결 리스트:
  노드들이 원형으로 연결되어 있어 마지막 노드의 다음이 첫 번째 노드가 된다. 요세푸스 문제에서는 이 구조를 통해 K번째 원소를 계속해서 찾아 제거하는 과정을 구현한다.
• 시뮬레이션:
  문제의 해결 방법은 실제로 원형 연결 리스트를 사용해 구현할 수도 있고, Python의 deque 같은 자료구조를 이용해 원형 큐의 동작(회전 및 제거)을 시뮬레이션하는 방식으로도 구현할 수 있다.
  예를 들어, deque를 사용하면 rotate()나 popleft() 같은 메서드로 간단하게 원형 구조를 흉내낼 수 있다.
• 알고리즘 선택:
  요세푸스 문제는 원형 연결 리스트를 이용하는 시뮬레이션 문제로 접근할 수 있지만, 경우에 따라 수학적인 공식을 활용해 더 효율적으로 풀 수도 있다. 단, 일반적으로 K가 임의의 값일 때는 시뮬레이션 방법이 가장 직관적이다.

https://www.acmicpc.net/problem/3015

import sys

input = sys.stdin.readline
N = int(input().strip())
heights = list(int(input().strip()) for _ in range(N))

def get_answer():
    stack = [] #(높이, 동일 높이 연속 개수) 집합
    result = 0
    for h in heights:
        same_count = 1
        #현재 h보다 작은 사람들은 볼 수 없으므로 pop하고, 그들이 형성헀던 쌍의 수를 더함
        while stack and stack[-1][0] < h:
            result += stack[-1][1]
            stack.pop()

        # 같은 높이의 경우, 같은 높이 그룹의 사람들과는 모두 볼 수 있음
        if stack and stack[-1][0] == h:
            cnt = stack[-1][1]
            stack.pop()
            result += cnt # 같은 높이 사람들과의 쌍 추가

            # 만약 스택에 아직 사람이 남아 있다면, 그 다음 높이 같은 사람과도 볼 수 있음
            if stack:
                result += 1
            same_count = cnt + 1
        else:
            # 스택이 비어있지 않다면, 바로 앞 사람과는 항상 볼 수 있음
            if stack:
                result += 1
        stack.append((h, same_count))
    return result

print(get_answer())

이 알고리즘의 핵심은:

• 왼쪽부터 순회하면서 스택에 (높이, 동일 높이 연속 개수)를 저장한다.
• 현재 사람보다 작은 사람들은 pop하여 그동안 형성된 쌍을 결과에 더하고,
  동일한 높이의 사람들은 하나의 그룹으로 묶어 개수를 관리한다.
• 남아 있는 스택의 최상단이 있다면 그 사람과는 볼 수 있으므로 1을 더한다.

이 방식은 각 사람을 한 번씩만 처리하여 O(N) 시간 내에 해결할 수 있다.