알고리즘 스터디 2주차 문제풀이
3986 좋은단어
https://www.acmicpc.net/problem/3986
평석아 이상한 거 하지 말고 자라... 수면부족이다
문제설명
stack을 사용한 데이터 삽입, 추출
전에 풀었던 괄호와 비슷한 유형의 문제이다
https://gyummodiary.tistory.com/83
접근방식
O(T x N) 선형 시간복잡도
각 문자열은 한 번씩 순회하며 처리된다.
각 문자열의 길이를 n이라고 할때, 내부 루프에서 문자열을 순회하며 스택 연산을 수행한다.
각 문자열에 대해 스택 연산은 O(n)시간이 걸린다.
스택 연산은 상수 시간이 걸리는데, 스택의 연산이 각 O(1) 시간 복잡도를 가지기 때문에 O(n x 1) = O(n) 시간이다.
문자열 개수가 T라고 했을때, 모든 입력을 한 번씩 읽어오므로 시간 복잡도는 O(T x n)이 된다.
전체 테스트 케이스의 수를 T라고 하면, 전체 코드의 시간복잡도는 O(T×n)가 된다.
따라서 이 알고리즘의 시간 복잡도는 입력으로 주어지는 문자열 총 길이에 선형으로 비례하며
각 문자열은 스택을 이용한 단일 순회로 처리된다.
문제 조건 분석 과정
1. 처음에 아치형이라 막막했으나, 괄호처럼 A에는 B 한쌍이 이루어져야 된다고 단순하게 생각해보자.
2. stack에 A를 넣고 다음 문자가 없을 경우 B를 삽입하고 종료하거나
3. 있을 경우 반환한다.
자료구조
Stack<Character>
문자형 데이터를 저장하는 스택을 생성
- push: st.push(val)를 사용하여 스택의 맨 위에 문자 val을 추가.
- pop: st.pop()을 호출하여 스택의 맨 위에 있는 값을 제거하고 반환한다.
- peek: st.peek()을 호출하여 스택의 맨 위에 있는 값을 조회한다.
- 제거하지 않고 값을 가져오며, 스택이 비어있을 경우 예외를 발생시키지 않고 null을 반환한다.
- empty: st.empty()를 사용하여 스택이 비어있는지 여부를 확인한다.
- 비어있으면 true, 아니면 false를 반환한다
틀린이유
풀이방법, 자료구조 파악을 하는데 시간이 걸렸다.
올바른 접근 방식 및 해결 방식
문제를 이해하는데 시간이 걸렸던 것 같다.
문제를 파악하기 힘들때는 성공하는 케이스의 경우의 수를 그려보자.
전체코드
import java.util.*;
import java.io.*;
public class Main3982_stack2 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
//개수 입력
int T = Integer.parseInt(br.readLine());
int result = 0;
//입력된 문자열 개수만큼 반복
for (int i = 0; i < T; i++) {
Stack<Character> st = new Stack<Character>();
//문자열 입력
String A = br.readLine();
for (int j = 0; j < A.length(); j++) {
//문자열을 하나씩 쪼갬
char val = A.charAt(j);
//스택이 비어있으면 현재 문자열을 넣음
if (st.empty()) {
st.push(val);
} else {
//스택이 비어있지 않으면 스택의 맨 위와 현재 문자 비교
if (st.peek() == val) {
//맨 위 문자와 현재 문자가 같으면 스택에서 제거
st.pop();
} else {
//맨 위 문자와 현재 문자가 다르면 현재 문자 삽입
st.push(val);
}
}
}
if (st.empty()) {
result++;
}
}
System.out.println(result);
}
}3613 java vs C++
1. 문제설명
모든 경우의 수를 찾아 문자열을 올바르게 변환
2. 접근방식
O(L)
입력된 변수명의 길이에 비례한다.
문제 조건 분석 과정
1. 형식이 틀리면 error 반환
- 대문자와 _가 문자열 내에 같이 있는가
- 문자 처음에 _나 대문자가 있는가
- 문자 마지막에 _가 있는가
- _가 두개 이상 연속으로 있는가
2. 형식이 맞으면 java, cpp, 단어형 검사 메소드로 보냄
- 자바 형식: 대문자가 있음
- 대문자를 소문자로 바꾸고 앞에 _를 추가한다
- cpp형식: _가 있음
- _를 지우고 단어를 대문자로 바꾼다
- 단어형
- 문자열 그대로 반환
3. 틀린 이유
모든 경우의 수에 대하여 반례 찾는게 힘들었다
4. 올바른 접근 방식 및 해결 방식
이런 반례찾기 유형의 문제는 많이 풀어보는 수 밖에 없는 것 같다...
5. 최종 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
//문제
//1. 변수명을 입력받는다. 영어 알파벳과 _로만 이루어져 있다.
//입력으로 주어진 변수명이 JAVA형식이면 C++ 형식으로 출력하고
//C++형식이라면 java 형식으로 출력한다.
//둘 다 아니라면 Error을 출력한다
//풀이
//1. 형식이 틀리면 error을 반환하고
//2. 형식이 맞으면 java, cpp, 단어형 검사 메소드로 보낸다
//- 틀린 형식
// 1. 대문자와 _가 문자열 내에 같이 있는가
// 2. 문자 처음에 _나 대문자가 있는가
// 3. 문자 마지막에 _가 있는가
// 4. _가 두 개 이상 연속으로 있는가
//-맞는 형식
// 1. java 형식 (대문자가 있음)
//isGptStupid -> is_gpt_stupid
//cpp형으로 변경한다.
//대문자를 소문자로 바꾸고 앞에 _를 추가한다
// 2. cpp형식 (_가 있음)
//is_right -> isRight
// java형으로 변경한다
// _를 지우고 뒤에 단어를 대문자로 바꾼다
// 3. 단어형
// 문자열 그대로 반환한다.
//예외처리를 먼저 하고 시작
// 형식 검사 함수
// -> false / true
public static boolean isValidFormat(String str) {
// 길이가 100을 넘는 경우 false 반환
if (str.length() > 100) {
return false;
}
//정규식 이용
//1. 대문자와 '_'가 문자열 내에 같이 있는가
//2. 문자 처음에 '_'나 대문자가 있는가
//3. 문자 끝에 _가 있는가
//4. '_' 가 두개 이상 문자 내에 있는가
//반환된 값을 !로 부정하여 false 반환
return !(str.matches(".*[A-Z].*") && str.matches(".*_.*") ||
str.matches("^[_A-Z].*") ||
str.matches(".*__+.*") ||
str.matches(".*_$"));
}
// 형식 변환 함수
public static String convertIdentifier(String str) {
// false일 경우 error 출력
if (!isValidFormat(str)) {
return "Error!";
}
StringBuilder result = new StringBuilder();
boolean toUpper = false;
int i = 0;
while (i < str.length()) {
char c = str.charAt(i);
if (Character.isUpperCase(c)) {
// Case 1: c가 대문자인 경우
if (i > 0 && !toUpper) {
// 앞 문자가 소문자일 경우에만 '_' 추가
result.append('_');
}
// c를 소문자로 변경하여 추가
result.append(Character.toLowerCase(c));
} else if (c == '_') {
// Case 2: '_'인 경우
toUpper = true;
} else {
// Case 3: 소문자인 경우
result.append(c);
toUpper = false;
}
if (toUpper && i + 1 < str.length()) {
// '_' 뒤의 문자를 대문자로 변환하여 추가
result.append(Character.toUpperCase(str.charAt(i + 1)));
i++; // '_' 다음 문자를 건너뛰기
toUpper = false; // 대문자 변환 상태 해제
}
i++; // 다음 문자로 이동
}
return result.toString();
}
//문자열 입력
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
//입력
String input = br.readLine().trim();
// 변환 후 출력
String converted = convertIdentifier(input);
System.out.println(converted);
br.close();
}
}1874 스택 수열
https://www.acmicpc.net/problem/1874문제설명
stack의 push와 pop을 사용한 데이터 삽입과 추출접근방식
O(n) 선형 시간복잡도
스택에 숫자를 넣을 때 변수를 증가시키면서 스택에 최대 n개의 숫자를 넣을 수 있다.
입력의 크기인 수열의 길이 n에 비례하여 선형 시간에 수행된다.
문제 조건 분석 과정
1. 스택을 사용하여 수열을 만든다.
자료구조
Stack<Integer>
정수형 데이터를 저장하는 스택을 생성.
- push: st.push(current)를 사용하여 스택의 맨 위에 정수 current를 추가.
- 이 때, current는 수열에 들어갈 숫자를 의미한다.
- pop: st.pop()을 호출하여 스택의 맨 위에 있는 값을 제거하고 반환한다.
- 이 코드에서는 수열 처리의 일치 여부를 확인한다.
- peek: st.peek()을 호출하여 스택의 맨 위에 있는 값을 조회한다.
- 스택의 top 값과 수열의 처리해야 할 숫자를 비교하기 위해 사용됩니다.
- isEmpty: st.isEmpty()를 사용하여 스택이 비어있는지 여부를 확인한다.
- 스택이 비어있는 경우와 아닌 경우를 처리한다.
틀린이유
스택의 후입선출을 이용한 push 와 pop 문제
만약, 수열이 [4, 3, 6, 8, 7, 5, 2, 1] 이라고 주어졌을때
스택에 순서대로1, 2, 3, 4를 스택에 넣은 후
수열에 4를 처리해야 할 때 pop을 수행하여 4를 수열에 추가한다.
올바른 접근 방식 및 해결 방식
스택, 큐에 대해서 아직 개념이 덜 잡힌 것 같다.
좀 더 공부해야겠다.............
전체코드
import java.io.*;
import java.util.*;
public class Main_1874스택수열 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
Stack<Integer> st = new Stack<>();
StringBuilder result = new StringBuilder();
//수열 지정
int n = Integer.parseInt(br.readLine());
int[] sequence = new int[n];
for(int i = 0; i < n; i++){
sequence[i] = Integer.parseInt(br.readLine());
}
int current = 1; //수열에 들어갈 숫자
for (int num : sequence){
while (current <= num){
st.push(current); //숫자를 스택에 push한다
result.append("+\n"); //push 연산
current++; //current 값 증가
}
//스택의 top이 수열에서 처리하는 숫자와 같은지 확인
if(st.peek() == num){
st.pop(); //수열에서 처리해야 할 숫자와 top이 일치하면 pop
result.append("-\n");
} else {
System.out.println("NO"); //일치하지 않을 경우
return;
}
}
//수열 출력
System.out.println(result.toString());
br.close();
}
}18258 큐2
https://www.acmicpc.net/problem/18258
문제설명
큐를 이용한 연산 문제
접근방식
O(n) 선형 시간복잡도
- 입력의 개수에 따라 O(N)이고, Linkedlist 내부의 연산은 O(1) 상수 시간을 가지기 때문에,
- O(N X 1) 로 전체 프로그램의 시간 복잡도는 O(N)입니다.
- 모든 연산은 입력의 개수에 따라 처리 됩니다.
문제 조건 분석 과정
다양한 연산(push, pop, size, empty, front, back)을 수행하는 queue (linkedList) 자료구조 구현
자료구조
LinkedList<Integer>
- LinkedList는 자바에서 제공하는 연결 리스트 자료구조이다.
- 각 요소들이 이전 요소와 다음 요소를 가리키면서.
- LinkedList<Integer>에서 Integer 타입의 데이터를 저장하는 형태
틀린이유
queue 자료구조에 대해 정리한 글을 보고 풀었다.
값을 빼낼때 큐가 비어있는 경우에 대한 예외처리를 생각 못하고 풀었다.
올바른 접근 방식 및 해결 방식
Linkedlist를 활용하여 Queue를 구현한다.
pop, front, back 연산에서 비어있는 경우에 대한 예외 처리가 필요하다.
각 연산마다 조건문을 사용하여 상태를 확인하고 처리한다.
전체코드
import java.util.*;
import java.io.*;
public class Main_18258큐2 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
LinkedList<Integer> queue = new LinkedList<>();
int N = Integer.parseInt(br.readLine()); //연산 입력
StringTokenizer st;
StringBuilder sb = new StringBuilder();
int Q = 0; //마지막으로 push된 값 저장
for(int i = 0; i < N; i++){
st = new StringTokenizer(br.readLine()); //공백을 추가하여 나열
switch(st.nextToken()){
case "push":
int A = Integer.parseInt(st.nextToken()); //push
queue.add(A); //queue에 값 추가
Q = A;
break;
case "pop":
if (queue.isEmpty()) {
sb.append("-1").append("\n"); //비어있을 경우 -1 출력
} else {
sb.append(queue.poll()).append("\n"); //값을 꺼내 출력
}
break;
case "size":
sb.append(queue.size()).append("\n"); //크기 출력
break;
case "empty":
if(queue.isEmpty()){
sb.append(1).append("\n"); //비어있을 경우 1 출력
} else {
sb.append(0).append("\n"); //비어있지 않으면 0 출력
}
break;
case "front":
if(queue.isEmpty()){
sb.append(-1).append("\n"); //비어있으면 -1 출력
} else {
sb.append(queue.peek()).append("\n"); //맨 앞의 값 출력
}
break;
case "back":
if (queue.isEmpty()) {
sb.append("-1").append("\n"); //비어있으면 -1 출력
} else {
sb.append(queue.peekLast()).append("\n"); //맨 뒤 값 출력
}
break;
default: break;
}
}
System.out.println(sb.toString());
br.close();
}
}1935 후위표기식2
https://www.acmicpc.net/problem/1935
골드문제보다 이게 훨씬 어려웠던 것 같음..
double 때문에 삽질을 꽤 오래 했다.
문제설명
stack을 사용해서 후위표기식 계산
접근방식
O(n) 선형 시간복잡도
중위 표기식을 한번씩 순회하면서 각 문자의 피연산자에 값을 대입하고, 연산자를 처리한다.
각 문자를 스택에 push하거나 pop하고 결과에 넣기 때문에 각 연산은 상수시간에 처리된다.
따라서, o(n x 1) 이므로 o(n)과 같다.
문제 조건 분석 과정
stack의 후입선출을 이용하여
1.피연산자 입력
2. 연산자를 만나면 두개의 수 꺼냄
3. 연산자 삽입
4. 입력받은 숫자로 계산
자료구조
Stack (Stack<Double> st)
- 후위 표기식을 계산하기 위한 스택이다. 이 스택은 피연산자와 연산자를 관리하며, 계산 중간 결과를 저장한다.
- 연산자를 만나면 스택에서 필요한 개수만큼 피연산자를 꺼내어 연산을 수행하고, 결과를 다시 스택에 push 한다.
- 최종 계산 결과는 스택에서 pop하여 가져온다.
틀린이유
double 때문에 삽질을 많이 했다.
어차피 소수점으로 출력하는거, 입력까지 소수점으로 받는게 편하겠다 싶어서
double 형으로 적었는데 입출력 결과는 당연히 실패.
연산 도중에 int형으로 바꿔줬다.
올바른 접근 방식 및 해결 방식
값을 입력받는 건 int형으로 받아줘야한다.
왜? double 형은 정밀도가 한정되어 있어서 (그야 소수니까)
오차가 발생할 수 있음
필요할때만 double형을 써야지 막 쓰면 안됨....
전체코드
import java.util.*;
import java.io.*;
public class Main_1935후위표기식2 {
public static void main(String[] args) throws IOException, IllegalArgumentException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// 변수의 개수 입력
int n = Integer.parseInt(br.readLine());
// 후위 표기식 입력
String exp = br.readLine().trim();
// 변수들의 값을 입력받을 배열
int[] v = new int[n];
// 각 변수에 대응하는 값을 입력
for (int i = 0; i < n; i++) {
v[i] = Integer.parseInt(br.readLine().trim());
}
// 스택 생성 (계산을 위한 스택)
Stack<Double> st = new Stack<>();
// 후위 표기식을 계산
for (int i = 0; i < exp.length(); i++) {
char ch = exp.charAt(i);
if (Character.isAlphabetic(ch)) { // 피연산자인 경우 (A-Z 사이의 문자)
double operandValue = v[ch - 'A'];
st.push(operandValue);
} else { // 연산자인 경우
double operand2 = st.pop(); // 두 번째 피연산자 꺼내기
double operand1 = st.pop(); // 첫 번째 피연산자 꺼내기
double result = 0.0;
// 연산 수행
switch (ch) {
case '+':
result = operand1 + operand2;
break;
case '-':
result = operand1 - operand2;
break;
case '*':
result = operand1 * operand2;
break;
case '/':
result = operand1 / operand2;
break;
}
// 연산 결과를 스택에 push
st.push(result);
}
}
// 스택에서 최종 결과 꺼내기
double finalResult = st.pop();
// 결과를 소수점 둘째 자리까지 출력
System.out.printf("%.2f\n", finalResult);
// BufferedReader 닫기
br.close();
}
}2840 행운의 바퀴
https://www.acmicpc.net/problem/2840
문제설명
후위 증감 연산자를 이용한 바퀴에 숫자를 입력하는 시뮬레이션
1. 초기에는 모든 바퀴가 비어 있다.
2. 주어진 숫자 입력에 따라 바퀴를 회전하면서 특정 위치에 숫자를 입력한다.
3. 입력 조건을 만족하지 않는 경우 !를 출력하고 프로그램을 종료한다.
접근방식
O(k * n) 선형 시간복잡도
while (K-- > 0) 반복문
각 반복에서 updateWheel 함수를 호출하여 바퀴를 업데이트한다.
updateWheel 함수는 배열을 순회하고 중복을 검사하는 작업을 수행하는데
바퀴의 길이 n을 숫자를 입력할 횟수만큼 반복한다.
전체 시간 복잡도는 O(K * N)이 된다.
문제 조건 분석 과정
1. 입력으로 주어지는 바퀴의 길이 N과 숫자를 입력할 횟수 K를 입력받는다.
2. 각 입력에 대해 위치와 입력 숫자를 받아 바퀴를 회전하며 입력된다.
3. 입력한 숫자는 중복되지 않아야 하며, 만약 중복되거나 조건에 맞지 않는 경우 예외처리를 한다.
4. 모든 입력을 처리한 후에는 바퀴에 입력된 숫자들을 왼쪽에서 오른쪽으로 순서대로 출력한다.
사용된 자료구조
배열 (char[] wheel):
바퀴의 길이를 나타내는 N만큼의 공간을 할당받고, 바퀴의 각 위치에 대한 문자를 저장한다.
스트림 (IntStream)
IntStream은 배열의 각 요소를 스트림으로 변환하여 중복을 검사한다.
바퀴에 이미 문자가 있는지 확인하는 데 사용된다.
틀린이유
바퀴의 길이 N 만큼 반복하면서 연산을 계산하는 부분에서 많이. 진짜 많이 헤맸다.
결국 답지를 보고 Instream 이라는 정렬 메소드가 있다는걸 알고 풀었다.
올바른 접근 방식 및 해결 방식
입력 받은 숫자를 바퀴의 현재 위치에서부터 시계 방향으로 입력하며, 중복을 체크한다.
만약 중복된 경우 예외를 발생시키고 프로그램을 종료한다.
바퀴에 입력된 숫자들을 왼쪽에서부터 오른쪽으로 순서대로 출력한다. 비어 있는 곳은 ?으로 처리하여 출력한다.
전체코드
import java.util.*;
import java.io.*;
import java.util.stream.IntStream;
public class Main_2840행운의바퀴 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer stringTokenizer = new StringTokenizer(br.readLine());
int N = Integer.parseInt(stringTokenizer.nextToken()); //바퀴 길이
int K = Integer.parseInt(stringTokenizer.nextToken()); //숫자 횟수
char[] wheel = new char[N];
int arrow = 0;
int updateIdx = 0;
//K번만큼 반복
while (K-- > 0) {
stringTokenizer = new StringTokenizer(br.readLine());
//숫자입력
int change = Integer.parseInt(stringTokenizer.nextToken());
char current = stringTokenizer.nextToken().charAt(0);
//첫번째 숫자일 경우 초기화
if (wheel[0] == '\u0000') {
wheel[0] = current;
continue;
}
//화살표 위치 업데이트
arrow += change;
updateIdx = arrow % N;
try {
//바퀴 업데이트
updateWheel(current, updateIdx, wheel);
} catch (Exception e) {
System.out.println("!");
return;
}
}
System.out.print(createAnswer(wheel, updateIdx));
}
//비밀번호 문자열
private static String createAnswer(char[] wheel, int updateIdx) {
StringBuilder stringBuilder = new StringBuilder();
//왼쪽
for (int i = updateIdx; i >= 0; i--) {
char update = wheel[i]== '\u0000' ? '?' : wheel[i];
stringBuilder.append(update);
}
//오른쪽
for (int i = wheel.length - 1; i > updateIdx; i--) {
char update = wheel[i]== '\u0000' ? '?' : wheel[i];
stringBuilder.append(update);
}
return stringBuilder.toString();
}
//바퀴 업데이트
private static void updateWheel(char current, int updateIdx, char[] wheel) {
// 같은 것이 들어있는 경우
if (wheel[updateIdx] == current) {
return;
}
// 비어있는 경우 && 중복이 아닌경우
if (wheel[updateIdx]== '\u0000' && !duplicate(current, wheel)) {
wheel[updateIdx] = current;
return;
}
// 다른 것이 들어있거나 중복인 경우
throw new IllegalArgumentException();
}
// 중복 검사
private static boolean duplicate(char current, char[] wheel) {
// 배열을 스트림으로 변환하여 중복 여부 확인
return IntStream.range(0, wheel.length).mapToObj(i-> wheel[i]).anyMatch(alphabet -> alphabet == current);
}
}