본문 바로가기

string22

[Problem Solving] BOJ 2608: 로마 숫자 문제 출처: https://www.acmicpc.net/problem/2608 로마숫자를 입력 받아서 합한 다음, 아라비아 숫자와 로마 숫자로 출력하는 문제이다. 먼저 로마 숫자를 아라비아 숫자로 변환할 때, 앞에 두개가 아라비아 숫자로 만들 수 있는 건지 확인먼저 하고 그렇지 않다면 앞에 하나를 아라비아 숫자로 만들 수 있는 건지 확인한다. 아라비아 숫자를 로마 숫자로 변환할 때는, (아라비아 숫자, 로마 숫자) 쌍을 내림차순으로 정렬해 놓고, 큰 수 부터 뺄 수 있는 만큼 빼고 그것의 로마 숫자를 하나씩 추가한다. import sysread = sys.stdin.readlinerom = { "I": 1, "V": 5, "X": 10, "L": 50, "C": 100, .. 2025. 8. 22.
[Problem Solving] BOJ 15927: 회문은 회문아니야!! 문제 출처: https://www.acmicpc.net/problem/15927 알파벳 대문자로 이루어진 문자열이 주어졌을 때, 팰린드롬이 아닌 가장 긴 부분문자열의 길이를 구하는 문제이다. 주어진 문자열의 길이를 n이라고 하자. 주어진 문자열 자체가 팰린드롬이 아닐 경우 -> n을 그대로 출력한다. 주어진 문자열 자체가 팰린드롬일 경우문자열 안 모든 문자가 같다면 -> -1을 출력한다.문자열 안 모든 문자가 같지 않은 팰린드롬이라면, 양쪽 끝에서 하나만 없애도 팰린드롬이 아니게 된다. -> n - 1을 출력한다. import sysread = sys.stdin.readlines = read().rstrip()n = len(s)if s != s[::-1]: print(n)else: if s.c.. 2025. 8. 6.
[Problem Solving] 프로그래머스 SQL 고득점 Kit: 조건에 맞는 사용자 정보 조회하기 문제 출처: https://school.programmers.co.kr/learn/courses/30/lessons/164670 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 게시물을 3건 이상 등록한 사용자의 사용자 ID, 닉네임, 전체주소, 전화번호를 출력해야한다. 우선 두 테이블을 Join해서 모든 사용자가 올린 글과 사용자 정보를 알 수 있다.SELECT *FROM USED_GOODS_BOARD AS BJOIN USED_GOODS_USER AS UON B.WRITER_ID = U.USER_ID 여기서 SELECT U.USER_ID를 하고 U.USER_ID로 그룹핑 한 후, HAVING COUNT(*)를 .. 2025. 8. 3.
[Problem Solving] BOJ 1414: 불우이웃돕기 문제 출처: https://www.acmicpc.net/problem/1414 N*N 행렬에 컴퓨터간 연결된 랜선의 길이가 주어진다.a~z는 1~26이고A~Z는 27~52이다. 일단 그래프를 만드는데, 자기 자신으로 다시 돌아오는 엣지는 제외하고, 중복되는 간선이 있다면 가중치가 가장 작은 것을 택한다.이제 이 그래프를 통해, 최소 신장 트리를 만들고, 그 최소 신장 트리에 있는 간선의 가중치의 합만큼을 전체 가중치에서 뺀 값을 출력하면 된다. 모든 컴퓨터가 연결되어있지 않으면 -1을 출력하면 되는데, 한 노드에서 시작하는 BFS를 한번 시행해서 모든 노드 방문을 시도 한다. 그래도 방문하지 않은 노드가 하나라도 있으면 -1을 출력하면 된다. 최소 신장 트리에 관한 포스트: https://junstory.. 2025. 7. 31.
[Problem Solving] 프로그래머스 SQL 고득점 Kit: 자동차 대여 기록 별 대여 금액 구하기 문제 출처: https://school.programmers.co.kr/learn/courses/30/lessons/151141 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 자동차 대여 기록 별 대여 금액을 구하여 대여 기록 ID와 대여 금액을 구하여 출력하면 된다. 우선 종류가 트럭인 자동차의 대여 기록ID와 일일 대여 요금, 대여 기간은 다음과 같이 구할 수 있다.SELECT H.HISTORY_ID, C.DAILY_FEE, DATEDIFF(H.END_DATE, H.START_DATE) + 1 AS DURATION, FROM CAR_RENTAL_COMPANY_CAR AS CJOI.. 2025. 7. 30.
[Problem Solving] 프로그래머스 SQL 고득점 Kit: 조회수가 가장 많은 중고거래 게시판의 첨부파일 조회하기 문제 출처: https://school.programmers.co.kr/learn/courses/30/lessons/164671 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 우선 USED_GOODS_BOARD에서 조회수가 가장 많은 게시물의 BOARD_ID를 반환하는 서브 쿼리를 다음과 같이 작성할 수 있다.SELECT B.BOARD_IDFROM USED_GOODS_BOARD AS BORDER BY B.VIEWS DESCLIMIT 1 이 쿼리에서 나온 테이블과 USED_GOODS_FILE을 BOARD_ID로 JOIN하면 조회수가 가장 많은 게시판의 첨부파일 정보를 가져올 수 있다. 그 정보들을 문제에서 제시한.. 2025. 7. 25.
[Problem Solving] BOJ 2800: 괄호 제거 문제 출처: https://www.acmicpc.net/problem/2800 괄호 쌍을 제거해서 나올 수 있는 모든 경우를 사전 순으로 출력하는 문제이다. 1. 괄호 쌍의 인덱스 쌍을 parList에 담는다.2. 비트마스크로 부분집합을 구한다.3. 괄호 쌍의 인덱스 쌍을 풀어서 모든 인덱스를 idxes에 담는다.4. 길이가 len(op)이고 모든 원소가 True인 flags 리스트를 만들고, idxes에 있는 인덱스에 위치하는 것들을 False로 바꾼다.5. 빈 문자열인 s를 만들고, flags[i]가 true일때 s에 op[i]를 추가한다.6. s가 빈 문자열이 아니면 set타입의 result에 문자열을 담는다. 위의 동작을 모든 부분집합에 대해서 수행했다면 result를 정렬하고 하나씩 출력하면 된.. 2025. 7. 25.
[Problem Solving] BOJ 2671: 잠수함 식별 문제 출처: https://www.acmicpc.net/problem/2671 정규표현식에 부합하는 문자열인지 판단하는 문제. import sysimport reread = sys.stdin.readlinepattern = re.compile(r'^(100+1+|01)+$')s = read().rstrip()if pattern.fullmatch(s): print("SUBMARINE")else: print("NOISE") 2025. 7. 17.
[Problem Solving] BOJ 1701: Cubeditor 문제 출처: https://www.acmicpc.net/problem/1701 문자열에서 2번 이상 나타나는 substring중 가장 긴 것의 길이를 구하는 문제이다.문자열 s가 있을때0 ~ len(s) - 1 의 값을 가지는 i에 대해서 get_pi(s[i:])의 최댓값을 구해야한다. get_pi(s)는 문자열 s의 부분문자열에서 동일한 접두사와 접미사가 존재할 때, 그것의 최대 길이를 return하는 함수이다.KMP알고리즘에서 LSP를 구하는 것과 같은 방식이다.x = 'aabaaa'라고 하자.pi[i]는 문자열 x[:i + 1]에서 동일한 접두사와 접미사가 존재할때 그것의 최대 길이이다.j는 현재까지 일치한 접두사의 길이로, 0부터 시작한다.i는 1부터 x의 끝까지 이동한다. x[i]와 x[j]가 .. 2025. 7. 9.
[Problem Solving] BOJ 16120: PPAP 문제 출처: https://www.acmicpc.net/problem/16120 문자열에 있는 P를 PPAP로 바꿀 수 있다고 할 때 이 과정을 반복해서 만들어진 문자열을 PPAP문자열이라고 한다. 주어진 문자열이 PPAP 문자열인지 판단하는 문제이다.이 문제는 스택을 사용하면 O(len(word))에 풀 수 있다. 문자열 왼쪽에서 오른쪽 순서로 stack에 추가한다.stack의 길이가 4개 이상이 되면 가장 최근에 들어간 4개의 문자열이 PPAP인지 확인하고 그렇다면 4개를 빼고 P를 넣는다.주어진 문자열이 PPAP 문자열이었다면 스택에는 P 하나만 남게 된다. 그렇다면 PPAP를 출력하고 그렇지 않다면 NP를 출력한다. import sysread = sys.stdin.readlineword = rea.. 2025. 6. 28.
[Problem Solving] BOJ 20437: 문자열 게임 2 문제 출처: https://www.acmicpc.net/problem/20437 문자열 W가 주어졌을 때,특정 문자를 K개 포함하는 부분 문자열 중 가장 짧은 것의 길이와특정 문자를 K개 포함하면서 첫글자와 앞글자가 같은 부분 문자열 중 가장 긴 것의 길이를 구하는 문제이다. 그런데 생각해보면특정 문자를 K개 포함하는 부분 문자열 중 가장 짧은 것도 첫글자와 앞글자가 같을 수 밖에 없다. 따라서특정 문자를 K개 포함하면서 첫글자와 앞글자가 같은 부분 문자열 중 가장 짧은 것의 길이와 가장 긴 것의 길이를 구하면된다. 풀이 과정은 다음과 같다. W를 순회하면서 각각의 문자가 위치한 인덱스를 position[ch] 딕셔너리의 value인 list에 추가한다. position을 완성했다면 다음을 수행한다.po.. 2025. 6. 1.
[Problem Solving] BOJ 2002: 추월 문제 출처: https://www.acmicpc.net/problem/2002 터널에 들어가는 순서랑 나오는 순서를 보고 추월한 차량이 몇 개 인지 구하는 문제이다. 1. 딕셔너리에 {차량 번호: 들어간 순서} 로 저장한다.2. 나오는 차량을 순서대로 입력할 때 들어간 순서를 구해서 arrival 리스트에 추가한다.3. arrival에서 순서를 역전한 수가 몇 개 인지 직접 찾아서 result를 증가시킨다. import sysread = sys.stdin.readlineN = int(read())car_ranking = {}for i in range(N): car_number = read().rstrip() car_ranking[car_number] = iarrival = []for i in .. 2025. 5. 14.
[Problem Solving] BOJ 7490: 0 만들기 문제 링크: https://www.acmicpc.net/problem/7490 백트래킹 + 문자열 문제이다. 1부터 N까지의 수를 순서대로 늘어놓고 인접한 수를 붙이거나 더하거나 빼서 0이 되는 경우의 수를 출력하는 문제이다.백트래킹이기 때문에 모든 함수를 재귀 호출하여 모든 경우의 수를 따져본다.식을 s에 만들어서 재귀함수에 넘겨준다. 공백이 있으면 replace함수로 공백을 제거한다음에 eval(e)로 0이면 s를 출력한다. import syssys.setrecursionlimit(10 ** 6)read = sys.stdin.readlineN = 0def is_zero(s): e = s.replace(" ", "").rstrip() if eval(e) == 0: return T.. 2025. 4. 6.
[Problem Solving] BOJ 1013: Contact 문제 링크: https://www.acmicpc.net/problem/1013 정규 표현식을 사용하여 주어진 문자열이 정규 표현식에 매칭되는지 확인하는 문제이다.pattern에 ^(100+1+|01)+$ 을 컴파일하는데,여기서 ^와 &는 주어진 문자열의 전체를 매칭한다는 뜻이다. ^는 문자열의 시작을 의미하고, $는 문자열의 끝을 의미한다.주어진 문자열 전체에 대해 (100+1+|01)+이라는 패턴이 존재하는 지 확인해야한다.패턴 (100+1+|01)+은(100+1+) 이라는 패턴이 한 번 이상 존재 하거나, (01) 이라는 패턴이 한 번 이상 존재하는 패턴이다(100+1+)은 10뒤에 0이 한 번 이상 나타나야 하고, 그 뒤에 1이 한 번 이상 나타나는 패턴이다. import sysimport rere.. 2025. 3. 23.
[Problem Solving] BOJ 4358: 생태학 문제 링크: https://www.acmicpc.net/problem/4358 Dictionary에 종별 개수를 카운트 한다.카운트의 합을 모두 더한다비율을 계산해서 소수점 4자리까지 출력한다. import sysread = sys.stdin.readlinenameList = []nameCnt = {}while True: name = read().rstrip() if not name: break if name not in nameList: nameList.append(name) nameCnt[name] = 1 else: nameCnt[name] += 1nameList.sort()Sum = 0for i in nameList: Su.. 2025. 3. 10.

티스토리툴바