태야

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) 시간 내에 해결할 수 있다.

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

이 문제는 "다음 큰(또는 같은) 수(Next Greater or Equal Element)" 문제다. 배열이나 리스트에서 각 원소에 대해 오른쪽에 있는 원소들 중 자신보다 크거나 같은(또는 보통은 '큰' 경우가 많지만, 변형으로 '크거나 같은' 조건을 쓰기도 한다) 첫 번째 원소를 찾는 문제이다.

1. 단순 탐색 풀이 - O(n^2)

from functools import reduce
import sys

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

def get_answer():
    results = []

    while heights:
        height = heights.pop(0)
        count = 0
        for i in range(len(heights)):
            if heights[i] < height:
                count += 1
            else:
                break
        results.append(count)
    print(reduce(lambda acc, value: acc + value, results))

2. 스택 이용 최적화 풀이 - O(n)

from functools import reduce
import sys

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

def get_answer():
    stack = []
    total_visible = 0

    for i in range(N - 1, -1, -1):
        # 현재 빌딩보다 낮은 빌딩들은 스택에서 제거
        while stack and heights[stack[-1]] < heights[i]:
            stack.pop()

        # 스택에 차단 빌딩이 있으면 그 위치까지 빌딩 수 계산
        if stack:
            visible = stack[-1] - i - 1
        else:
            # 오른쪽의 모든 빌딩이 보이는 경우
            visible = N - i - 1
        total_visible += visible

        # 현재 빌딩 인덱스를 추가
        stack.append(i)

    return total_visible

print(get_answer())

• 스택을 활용하면 오른쪽에서 왼쪽으로 한 번의 순회로 각 빌딩의 보이는 옥상 수를 구할 수 있어 전체 시간복잡도를 O(n)으로 최적화할 수 있다.
• 이 방법은 각 빌딩이 스택에 단 한 번 들어가고 한 번씩만 제거되므로 효율적이다.

<내 코드>

class Solution {
    public int[] solution(int[] prices) {
        int[] answer = new int[prices.length];
        
        for(int i=0; i<prices.length; i++){
            for(int j=i+1; j< prices.length; j++){
                if (prices[i] > prices[j]) {
                    answer[i] = j-i;
                    break;
                }
                if(j == prices.length-1){ // 마지막 요소 확인
                    answer[i] = j-i;
                }
            }
        } 
        return answer;
    }
}

def solution(prices):
    answer = []
    
    n = len(prices)
    for i in range(n): #0~4
        cnt = 0
        if i == n-1:
            answer.append(cnt)
            break
        for j in range(i+1,n): #1~4
            if prices[i] <= prices[j]:
                cnt += 1
            else:
                cnt += 1
                break
        answer.append(cnt)
    
    return answer

<내 코드>

def solution(heights):
    answer = []
    re_ans = []
    re_heights = list(reversed(heights))
    pk = 0
    
    while(pk != len(heights)):
        tmp = re_heights[pk]
        if(pk == len(heights)-1):
            re_ans.append(0)
            break
        
        for i in range(pk + 1, len(heights)):
            if(tmp < re_heights[i]):
                re_ans.append(len(heights) - i)
                break
            else:
                if(i == len(heights)-1):
                    re_ans.append(0)
        pk += 1
        
    answer = list(reversed(re_ans))
    return answer

reverse() 함수는 단순히 해당 리스트의 값을 뒤집고, 어떤 값을 리턴하지 않는다.

reversed는 리스트의 함수가 아닌 파이썬 자체의 내장 함수로, 리턴으로 객체를 보내기에 리스트로 값을 얻기 위해 list() 함수를 사용했다.

<다른 풀이>

def solution(h):
    ans = [0] * len(h)
    for i in range(len(h)-1, 0, -1):
        for j in range(i-1, -1, -1):
            if h[i] < h[j]:
                ans[i] = j+1
                break
    return ans

진짜 이렇게 간단하게 해결을 할 수 있다니...정말..경이롭다...

여기서 range를 시작, 끝, 스텝을 이용해 -1씩 감소하게 해 reverse, reversed 없이 가능한 걸 알게 됐다.

 파이썬 기초 문법 - 자료형 

1. 숫자 자료형

파이썬의 숫자 자료형은 '정수, 실수형, 2진수, 8진수, 16진수'로 표현할 수 있다.

'''
        정수           : -10, 0, 10
        실수형         : -1.1, 10.123
        2진수(binary)  : 0b10, 0B10
        8진수(octal)   : 0o10, 0O10
        16진수(hexadecimal) : 0x10, 0X10
'''

아래에 간단한 예제를 보자.

print("[기본 숫자형]")
print("정수 :", 10, -10, 0)
print("실수 :", -1.1, 10.123)
# print() 함수는 숫자를 10진수로 출력
print("2진수 :", 0b100, 0B100)
print("8진수 :", 0o10, 0O10)
print("16진수 :", 0x10, 0X10)

결과는 다음과 같다.

정수 : 10 -10 0
실수 : -1.1 10.123
2진수 : 4 4
8진수 : 8 8
16진수 : 16 16

2. 문자열

파이썬에서 문자열을 만드는 방법은 4가지가 있다.

• 1. 큰 따옴표 1개

• 2. 작은따옴표 1개

• 3. 큰 따옴표 3개

• 4. 작은 따옴표 3개

print("1. happy day")
print('2. happy day')
print("""3. happy day""")
print('''4. happy day''')

결과는 다음과 같다.

1. happy day
2. happy day
3. happy day
4. happy day

만약 여러 줄의 문자열을 출력하고 싶다면 따옴표 3개짜리를 이용하면 된다.

print("""안녕하세요
파이썬입니다.""")

hello = '''반가워요
파이썬!'''
print(hello)

문자열을 사용하고 출력할 때 사용되는 '이스케이프 문자'가 있는데, 이스케이프 문자는 문자열 안에서 특수한 기능을 가지는 문자들을 말한다. 이스케이프 문자는 역슬래시(\)로 시작해 사용한다. 아래에 여러 이스케이프 문자들이 있다.

'''
	\n : 개행(줄바꿈)
	\t : tab키를 누른 만큼 간격 띄우기
	\\ : \ 하나를 문자로 사용
	\' : ' 하나를 문자로 사용
	\" : " 하나를 문자로 사용
'''

문자열 연산하기

문자열을 연산할 때 주의할 것이 문자열끼리만 연산이 가능하다는 것이다. 예를 들어 정수와 문자열 사이의 연산을 하게 되면 오류가 발생한다. 그러니 이 점을 주의해서 사용해야 한다.

문자열 연산은 2가지 경우가 있다.

#1. + : 연결
print("안녕" + "하세요")
str1 = "안녕"
str2 = "하세요"
print(str1 + str2)

#2. * : 반복
print("안녕" * 5)
str3 = "곱셈" * 3 # 연산 결과를 만든 후 변수에 대입
print(str3)

문자열 인덱싱(Indexing)

인덱싱(Indexing)이란 index 색인, '무언가를 가리킨다'는 것으로, 문자열에서 특정 글자를 뽑아내어 사용하는 것이다. 특정 글자를 찾을 때, '순서'를 사용하는데 이 때 인덱스 번호를 이용한다. 프로그래밍에서 순서는 0부터 시작을 하며 음수일 경우 뒤에서부터 순서를 세는 방식이다.

문자열 슬라이싱

문자열 슬라이싱은 문자열은 원하는 길이만큼 조각내는 것이다. 인덱스로 특정 범위의 문자를 조각내서 사용한다. 아래처럼 다양하게 사용할 수 있다.

a[0:3] --> 콜론(:)으로 범위 지정

a[시작 인덱스:끝 인덱스] --> 끝 인덱스는 포함 X

a[시작 인덱스:] --> '시작 인덱스'부터 '끝'까지

a[:끝 인덱스] --> '처음'부터 '끝 인덱스'까지 (끝 인덱스는 포함 X)

a[:] --> 시작부터 끝 --> 전체

문자열 기본 포매팅

문자열 포매팅은 문자열 안에 '값'을 '삽입'하는 방법이다. 포매팅 코드(서식문자)는 4가지가 있다.

%s - 문자열 (String)
%c - 문자 1개
%d - 정수
%f - 실수
%% - % 하나를 문자로 삽입

서식 문자를 사용한 문자열 포매팅 예제들입니다.

# 문자열 뒤에 바로 % 기호를 붙여서 값을 입력
print("정수 : %d" % 20)
my_str = "정수 : %d" % 30
print(my_str)

print("실수 : %f" % 10.1)
print("문자열 : %s" % "나는 문자열")

print("정수 : %d" % 10.123) # 실수 값을 정수로 삽입(소수점은 없어짐)
print("실수 : %f" % 30) # 정수 값을 실수로 삽입(없던 소수점 생김)

print("문자열 : %s" % 10) # %s는 전부 문자 취급
print("문자열 : %s" % 10.123)

#결과
정수 : 20
정수 : 30
실수 : 10.100000
문자열 : 나는 문자열
정수 : 10
실수 : 30.000000
문자열 : 10
문자열 : 10.123

다음으로 포맷 코드 대신 format() 함수를 이용한 문자열 포매팅 방법입니다.

my_str = "제 이름은 {}입니다.".format("홍길동") # 만든 문자열을 변수에 대입
print(my_str)

name = "홍길동"
age = 20
print("제 이름은 {}이고, {}살 입니다.".format(name, age))