<링크>
https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV14zIwqAHwCFAYD
SW Expert Academy
SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!
swexpertacademy.com
<문제>
- 0 ~ 999999 사이의 수로 표현되는 암호문이 있고, 이 암호문을 N개 모아 놓은 암호문 뭉치가 있다.
- 암호문 뭉치를 급히 수정해야 할 일이 발생했는데, 암호문은 특수 제작된 처리기로만 수정이 가능하다.
- 처리기는 다음과 같이 3개의 명령어로 제어한다.
- 1. I(삽입) x, y, s : 앞에서부터 x번째 암호문 바로 다음에 y개의 암호문을 삽입한다. s는 덧붙일 암호문들이다.[ ex) I 3 2 123152 487651 ]
- 2. D(삭제) x, y : 앞에서부터 x번째 암호문 바로 다음부터 y개의 암호문을 삭제한다.[ ex) D 4 4 ]
- 3. A(추가) y, s : 암호문 뭉치 맨 뒤에 y개의 암호문을 덧붙인다. s는 덧붙일 암호문들이다. [ ex) A 2 421257 796813 ]
- 위의 규칙에 맞게 작성된 명령어를 나열하여 만든 문자열이 주어졌을 때, 암호문 뭉치를 수정하고, 수정된 결과의 처음10개 암호문을 출력하는 프로그램을 작성하여라.
<입력>
- 첫 번째 줄 : 원본 암호문 뭉치 속 암호문의 개수 N ( 2000 ≤ N ≤ 4000 의 정수)
- 두 번째 줄 : 원본 암호문 뭉치
- 세 번째 줄 : 명령어의 개수 ( 250 ≤ M ≤ 500 의 정수)
- 네 번째 줄 : 명령어
- 위와 같은 네 줄이 한 개의 테스트 케이스이며, 총 10개의 테스트 케이스가 주어진다.
<출력>
#기호와 함께 테스트 케이스의 번호를 출력하고, 공백 문자 후 수정된 암호문 뭉치의 앞 10개 암호문을 출력한다.
<코드1. - java, linkedList 직접 구현>
import java.util.*;
import java.io.*;
public class Solution {
// 링크드 리스트 직접 구현
static int NODE_MAX = 5000;
static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
// Node
static class Node {
int data;
Node next;
public Node(int data) {
this.data = data;
this.next = null;
}
}
static class LinkedList {
Node head;
Node tail;
// new를 최소한으로 쓰기 위한 녀석
// new 이친구 괴애애애애애장이 느림.
Node[] nodeArr;
int nodeCnt;
public LinkedList() {
head = null;
nodeArr = new Node[NODE_MAX];
nodeCnt = 0;
}
// 정적 할당 방식
// 일단 왕창 메모리에 노드를 만들어 놓고,
// 새로운 노드를 요청시, 여분의 노드중 안쓴거를 가져오는 것
// -> 시간이 엄청나게 줄어듬
Node getNewNode(int data) {
// data를 값으로 갖는 새로운 node 생성하고, 생성된 node를 return
nodeArr[nodeCnt] = new Node(data);
return nodeArr[nodeCnt++];
}
// 앞에서 idx개 이후에 nums 들을 추가하기
void insert(int idx, int[] nums) {
int st = 0;
if (idx == 0) {// 맨 앞에 붙이는 경우 (head가 변경되어야하는 경우등)
// 먼저 한개만 추가하고 head 재조정
if (head != null) {
Node newNode = getNewNode(nums[0]);
newNode.next = head;
head = newNode;
} else {
head = getNewNode(nums[0]);
}
// 남은 수들은 head 뒤에 차례로 이어 붙어야 함
idx = 1;
st = 1;
}
Node cur = head;
// idx 개 만큼 이동하기
for (int i = 1; i < idx; i++) {
cur = cur.next;
}
// nums 추가하기
for (int i = st; i < nums.length; i++) {
Node newNode = getNewNode(nums[i]);
// 만약 아래의 코드의 순서를 바꾸면...
// newNode.next 가 본인 스스로가 되버림. 즉, cur.next가 갈곳이 없어집니다..ㅠ
newNode.next = cur.next;
cur.next = newNode;
cur = newNode;
}
if (cur.next == null) {
tail = cur;
}
}
void delete(int idx, int cnt) { // idx 번 인덱스부터 cnt개 만큼 삭제하기
Node cur = head;
// 맨 앞이 삭제되는 경우 (head 가 재조정 되는 경우)
if (idx == 0) {
for (int i = 0; i < cnt; i++) {
cur = cur.next;
}
head = cur;
return;
}
// idx개 만큼 이동하기
for (int i = 0; i < idx; i++) {
cur = cur.next;
}
Node anchor = cur; // 삭제되기 직전 위치 기억하기
for (int i = 0; i < cnt; i++) {
cur = cur.next;
}
anchor.next = cur.next;
if (anchor.next == null) {
tail = anchor;
}
}
void add(int data) { // 제일 뒤에 data 추가하기
Node cur = tail;
Node newNode = getNewNode(data);
cur.next = newNode;
tail = newNode;
}
void print() throws Exception { // 출력하기
int cnt = 10;
Node cur = head;
while (--cnt >= 0) {
bw.write(cur.data + " ");
cur = cur.next;
}
}
}
public static void main(String[] args) throws Exception {
int T = 10;
StringTokenizer stk;
for (int t = 1; t <= T; t++) {
LinkedList list = new LinkedList();
bw.write("#");
bw.write(t + " ");
int n = Integer.parseInt(in.readLine());
int[] initArr = new int[n];
stk = new StringTokenizer(in.readLine());
for (int i = 0; i < n; i++) {
initArr[i] = Integer.parseInt(stk.nextToken());
}
list.insert(0, initArr);
int M = Integer.parseInt(in.readLine());
stk = new StringTokenizer(in.readLine());
for (int i = 0; i < M; i++) {
char cmd = stk.nextToken().charAt(0);
int x, y;
switch (cmd) {
case 'I':
x = Integer.parseInt(stk.nextToken());
y = Integer.parseInt(stk.nextToken());
int[] temp = new int[y];
for (int j = 0; j < y; j++) {
temp[j] = Integer.parseInt(stk.nextToken());
}
list.insert(x, temp);
break;
case 'D':
x = Integer.parseInt(stk.nextToken());
y = Integer.parseInt(stk.nextToken());
list.delete(x, y);
break;
case 'A':
y = Integer.parseInt(stk.nextToken());
for (int j = 0; j < y; j++) {
list.add(Integer.parseInt(stk.nextToken()));
}
break;
}
}
list.print();
bw.write("\n");
}
bw.flush();
in.close();
bw.close();
}
}
<코드2. java - ArrayList 사용>
import java.util.*;
import java.io.*;
public class Solution2 {
static StringBuilder sb = new StringBuilder();
static StringTokenizer st;
static ArrayList<Integer> list;
public static void main(String[] args) throws Exception {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
int test_case = 10;
for (int t = 1; t <= test_case; t++) {
// 원본 암호문 뭉치속 암호문 개수 n (3198)
int n = Integer.parseInt(in.readLine());
// 암호문 담을 연결 리스트(801, 482, ....)
list = new ArrayList<>();
st = new StringTokenizer(in.readLine());
for (int i = 0; i < n; i++) {
list.add(Integer.parseInt(st.nextToken()));
}
// 명령어 개수 (425)
int m = Integer.parseInt(in.readLine());
st = new StringTokenizer(in.readLine());
for (int i = 0; i < m; i++) {
char cmd = st.nextToken().charAt(0);
int x = Integer.parseInt(st.nextToken());
fun(cmd, x);
}
sb.append("#" + t);
// 암호문중 10개만 출력
for (int i = 0; i < 10; i++) {
sb.append(" " + list.get(i));
}
sb.append("\n");
}
System.out.println(sb);
}
private static void fun(char cmd, int x) {
int y;
switch (cmd) {
case 'I':
y = Integer.parseInt(st.nextToken());
for (int i = 0, insertIdx = x; i < y; i++, insertIdx++) {
list.add(insertIdx, Integer.parseInt(st.nextToken()));
}
break;
case 'D':
y = Integer.parseInt(st.nextToken());
for (int i = 0; i < y; i++) {
list.remove(x);
}
break;
case 'A':
for (int i = 0; i < x; i++) {
list.add(Integer.parseInt(st.nextToken()));
}
break;
}
}
}'알고리즘 > swea' 카테고리의 다른 글
| (SWEA) 10726. 이진수 표현 (0) | 2025.01.20 |
|---|