구현 알고리즘이란
구현이란 머릿속에 있는 알고리즘을 소스 코드로 바꾸는 과정이다.
구현은 생각해낸 문제 풀이 방법을 우리가 원하는 프로그래밍 언어로 정확히 구현해냈을 때 비로소 정답 처리를 받을 수 있다.
구현 유형의 문제는 ‘풀이를 떠올리는 것은 쉽지만 소스 코드로 옮기기 어려운 문제’를 의미한다.
구현 문제 중 어려운 구현 문제의 예시는 다음과 같다.
- 알고리즘은 간단한데 코드가 지나칠만큼 길어지는 문제
- 특정 소수점까지 출력해야 하는 문제
- 문자열이 입력으로 주어졌을 때 한 문자 단위로 끊어서 리스트에 넣어야 하는 문제
대체로 사소한 조건 설정이 많을 수록 여러운 구현 문제라고 볼 수 있다.
구현 유형은 아래와 같이 나눌 수 있다.
- 완전탐색
- 시뮬레이션
완전 탐색은 모든 경우의 수를 주저 없이 다 계산하는 해결 방법을 의미한다.
시뮬레이션은 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행 해야 하는 문제 유형을 의미한다.
구현 시 고려 해야 할 메모리 제약 사항들이 있다.
일반적인 취업시 보는 코테에서는 자바의 경우 long long에서 다룰 수 있는 수보다 더 큰 정수를 처리하는 문제는 잘 출제 되지 않는다.
또한 시간 제한이 1초이고, 데이터의 개수가 100만 개인 문제가 있다면 일반적으로 시간 복잡도 O(NlogN) 이내의 알고리즘을 이용하여 문제를 풀어야 한다.
ex: 우선순위 큐
보통 구현 유형의 문제는 사소한 입력 조건 등을 문제에서 명시해주며 문제의 길이가 꽤 긴 편이다.
그러나 고차원적인 사고력을 요구하는 문제는 나오지 않는 편이라 문법에 익숙하다면 오히려 쉽게 풀 수 있다.
1️⃣ 스택 - 10828
문제
정답
import java.io.*;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;
public class Main {
static List<Integer> nums = new ArrayList<>();
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
public void solution() throws IOException {
int n = Integer.parseInt(br.readLine());
for (int i = 0; i < n; i++) {
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
String command = st.nextToken();
if (st.countTokens() > 0) {
push(Integer.parseInt(st.nextToken()));
}
if (command.equals("pop")) {
pop();
}
if (command.equals("size")) {
size();
}
if (command.equals("empty")) {
empty();
}
if (command.equals("top")) {
top();
}
}
bw.flush();
bw.close();
}
public void push(int num) {
nums.add(num);
}
public void pop() throws IOException {
if (nums.isEmpty()) {
bw.write("-1" + "\n");
} else {
bw.write(nums.get(nums.size() -1) + "\n");
nums.remove(nums.size() -1);
}
}
public void size() throws IOException {
bw.write(nums.size() + "\n");
}
public void empty() throws IOException {
if (nums.isEmpty()) {
bw.write("1" + "\n");
} else {
bw.write("0" + "\n");
}
}
public void top() throws IOException {
if (nums.isEmpty()) {
bw.write("-1" + "\n");
} else {
bw.write(nums.get(nums.size() -1) + "\n");
}
}
public static void main(String[] args) throws IOException {
new Main().solution();
}
}
문제에서 말하는 스택이란 매우 간단하게 설명 하자면 선입후출을 하는 자료구조를 말한다.
스택에 대해서 잘 정리한 글 링크를 동봉한다.
https://st-lab.tistory.com/174
위 레퍼런스에서 좋은 내용이 있기에 가져와본다.
그럼 본격적으로 Stack을 구현하기 전에 알아가야할 것이 있다.
모든 자료구조는 '동적 할당'을 전제로 한다. 가끔 ArrayList, Stack 같이 Object[] 배열을 사용하는 자료구조를 구현 할 때, 자료구조의 용적(Capacity)이 꽉 차면 리스트의 크기를 늘리지 않고 그냥 꽉 찼다고 더이상 원소를 안받도록 구현한 경우가 많은데 이는 자료구조를 구현하는 의미가 없다.
동적 할당을 안하고 사이즈를 정해놓고 구현한다면 메인함수에서 정적배열을 선언하는 것과 차이가 없다.
해당 문제는 쉬운 편이다.
그저 문제가 요구하는 대로 작성하면 된다.
다만 나는 ArrayList 자료 구조를 사용 하였는데 이는 일반적인 리스트보다 연산에 더 많은 시간을 소요 하므로 일반적인 리스트로 stack 구조를 만드는 것이 최고의 방법이었을 것 같다.
ArrayList를 사용 했음에도 시간 초과가 나오지 않았던 이유는 BufferReader를 사용하였기 때문이다.
배운 점
- 내가 List를 사용하지 않았던 이유는 remove시에 기존 리스트를 복사해야 한다는 번거로움 때문이었다.
- 그러나 이를 놀라운 방법으로 다른 분께서 풀었던 코드를 가져왔다.
size를 별도 변수로 선언하면 해당 size 변수의 인덱스만 가지고 후출 선입 하기에 기존 리스트를 복사 하지 않고 연산을 할 수 있었다.int res = stack[size - 1]; stack[size - 1] = 0; // 0으로 초기화 해준다. size--; return res;
- 그러나 이를 놀라운 방법으로 다른 분께서 풀었던 코드를 가져왔다.
2️⃣ 크로아티아 알파벳 - 2941
문제
정답
import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;
public class Main {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
public void solution() throws IOException {
Character[] alphaArr = {'c', 'l', 'd', 'z', 'j', 'n', 's', '-', '='};
String[] arr = {"c=", "c-", "dz=", "d-", "lj", "nj", "s=", "z="};
ArrayList<Character> alphaList = new ArrayList<>(Arrays.asList(alphaArr));
ArrayList<String> list = new ArrayList<>(Arrays.asList(arr));
String inputWords = br.readLine();
int ans = 0;
String tmp = "";
for (int i = 0; i < inputWords.length(); i++) {
Character word = inputWords.charAt(i);
tmp += word;
if (!alphaList.contains(word)) {
ans += tmp.length();
tmp = "";
continue;
}
if (list.contains(tmp)) {
tmp = "";
ans += 1;
} else {
if (tmp.length() == 2 && !tmp.equals("dz")) { // 만약 2개 이상이 되었는데, 맞는 짝이 없다면 pass
tmp = tmp.substring(1);
ans += 1;
}
if (tmp.length() > 2 && !tmp.equals("dz=")) {
tmp = tmp.substring(2);
ans += 2;
}
}
}
bw.write(ans + tmp.length() + "\n");
bw.flush();
bw.close();
}
public static void main(String[] args) throws IOException {
new Main().solution();
}
}
발생 할 수 있는 각 조건에 따라서 분기문을 작성해주면 된다.
문제를 풀면서 아 코드가 너무 지저분한데? 라는 생각이 들었었는데, 다른 분들의 코드를 보니까 분기문으로 인해서 지저분 한건 어쩔 수 없나보다.
순서대로 단어들이 나오기에 큰 어려움은 없는 문제였다.
다른 사람 풀이
배운 점
- 위 레퍼런스간 글에서 좋은 문구를 가지고 왔다. 항상 필자가 강조하는 부분이지만 만약 문제를 딱 보고 한번에 완벽하게 구상되는 것이 아니라면 하나씩 차근차근 짜보면서 완성해나가는 것이 좋다.
필자 보통 코드를 짤 때 한 번에 완성이 안되면 완성시키기 위해 3 가지 방법을 쓴다.
- 큰 틀부터 하나씩 짠다.
- 예외가 발생하는 경우를 쭉 나열한다.
- 예외를 처리하고 및 극단적인 경우의 값을 넣어 디버깅 해본다.
- 문자열 연산이 이렇게 있는 문제는 처음 풀게 되는 것 같다.
- 코테에서는 문자열 연산 문제가 많이 나온다니 문자열 함수들을 외우고 있으면 큰 도움이 될 것 같다.
3️⃣ 셀프 넘버 - 4673
문제
정답
import java.io.*;
public class Main {
public void solution() throws IOException {
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int[] selfNums = new int[10001];
for (int i = 1; i <= 10000; i++) {
int selfNum = getSelfNums(i);
if (selfNum <= 10000) {
selfNums[selfNum] = 1;
}
}
for (int j = 1; j <= 10000; j++) {
if (selfNums[j] == 0) {
bw.write(j + "\n");
}
}
bw.flush();
bw.close();
}
public int getSelfNums(int i) {
int sum = i;
while (i != 0) { // 각 자리수마다 더해줌
sum += i % 10;
i = i / 10;
}
return sum;
}
public static void main(String[] args) throws IOException {
new Main().solution();
}
}
배운 점
- 숫자의 자리수가 정해져 있지 않을 때 아래의 코드를 통해서 각 자리수에 대한 연산을 할 수 있다.
while (i != 0) { // 각 자리수마다 더해줌 sum += i % 10; i = i / 10; }
