올림픽은 참가에 의의가 있기에 공식적으로는 국가간 순위를 정하지 않는다. 그러나, 많은 사람들이 자신의 국가가 얼마나 잘 하는지에 관심이 많기 때문에 비공식적으로는 국가간 순위를 정하고 있다. 두 나라가 각각 얻은 금, 은, 동메달 수가 주어지면, 보통 다음 규칙을 따라 어느 나라가 더 잘했는지 결정한다.
금메달 수가 더 많은 나라
금메달 수가 같으면, 은메달 수가 더 많은 나라
금, 은메달 수가 모두 같으면, 동메달 수가 더 많은 나라
각 국가는 1부터 N 사이의 정수로 표현된다. 한 국가의 등수는 (자신보다 더 잘한 나라 수) + 1로 정의된다. 만약 두 나라가 금, 은, 동메달 수가 모두 같다면 두 나라의 등수는 같다. 예를 들어, 1번 국가가 금메달 1개, 은메달 1개를 얻었고, 2번 국가와 3번 국가가 모두 은메달 1개를 얻었으며, 4번 국가는 메달을 얻지 못하였다면, 1번 국가가 1등, 2번 국가와 3번 국가가 공동 2등, 4번 국가가 4등이 된다. 이 경우 3등은 없다.
각 국가의 금, 은, 동메달 정보를 입력받아서, 어느 국가가 몇 등을 했는지 알려주는 프로그램을 작성하시오.
입력
입력의 첫 줄은 국가의 수 N(1 ≤ N ≤ 1,000)과 등수를 알고 싶은 국가 K(1 ≤ K ≤ N)가 빈칸을 사이에 두고 주어진다. 각 국가는 1부터 N 사이의 정수로 표현된다. 이후 N개의 각 줄에는 차례대로 각 국가를 나타내는 정수와 이 국가가 얻은 금, 은, 동메달의 수가 빈칸을 사이에 두고 주어진다. 전체 메달 수의 총합은 1,000,000 이하이다.
출력
출력은 단 한 줄이며, 입력받은 국가 K의 등수를 하나의 정수로 출력한다. 등수는 반드시 문제에서 정의된 방식을 따라야 한다.
// 입력 값 처리 부분constfs=require("fs");const[numbers,...medals]=fs.readFileSync("/dev/stdin").toString().split("\n").map((line)=>line.split(" ").map((el)=>el*1));const[N,K]=numbers;solveProblem();// 문제 해결 방식// 1. 주어진 K 값으로 탐색하여 target을 구한다.// 2. target과 타국들과의 메달 비교를 통해 rank를 도출.functionsolveProblem(){consttarget=getTarget(K,medals);constrank=getRank(target,medals);console.log(rank);}// target 국가를 구하는 함수// 주어진 K를 전체 국가의 ID과 비교하여 찾는다.// @return {Array}: target 국가 정보functiongetTarget(K,medals){letresult;for(leti=0;i<N;i++){if(medals[i][0]===K)result=medals[i];}returnresult;}// rank를 구하는 함수// 금메달 비교 후 target 국가보다 많으면 rank + 1// 금메달이 같으면, 은메달 비교 후 target 국가보다 많으면 rank + 1// 은메달이 같으면, 동메달 비교 후 target 국가보다 많으면 rank + 1// @return {number}: 최종 rank를 반환functiongetRank(target,medals){letresult=1;// 전체 국가와 비교for(leti=0;i<N;i++){// 본인 국가는 지나가기if(medals[i][0]===target[0])continue;if(medals[i][1]>=target[1]){// 금메달 비교if(medals[i][1]>target[1]){result++;}elseif(medals[i][2]>=target[2]){// 은메달 비교if(medals[i][2]>target[2]){result++;}elseif(medals[i][3]>=target[3]){// 동메달 비교if(medals[i][3]>target[3]){result++;}}}}}returnresult;}
8*8크기의 체스판에 왕이 하나 있다. 킹의 현재 위치가 주어진다. 체스판에서 말의 위치는 다음과 같이 주어진다. 알파벳 하나와 숫자 하나로 이루어져 있는데, 알파벳은 열을 상징하고, 숫자는 행을 상징한다. 열은 가장 왼쪽 열이 A이고, 가장 오른쪽 열이 H까지 이고, 행은 가장 아래가 1이고 가장 위가 8이다. 예를 들어, 왼쪽 아래 코너는 A1이고, 그 오른쪽 칸은 B1이다.
킹은 다음과 같이 움직일 수 있다.
R : 한 칸 오른쪽으로
L : 한 칸 왼쪽으로
B : 한 칸 아래로
T : 한 칸 위로
RT : 오른쪽 위 대각선으로
LT : 왼쪽 위 대각선으로
RB : 오른쪽 아래 대각선으로
LB : 왼쪽 아래 대각선으로
체스판에는 돌이 하나 있는데, 돌과 같은 곳으로 이동할 때는, 돌을 킹이 움직인 방향과 같은 방향으로 한 칸 이동시킨다. 아래 그림을 참고하자.
입력으로 킹이 어떻게 움직여야 하는지 주어진다. 입력으로 주어진 대로 움직여서 킹이나 돌이 체스판 밖으로 나갈 경우에는 그 이동은 건너 뛰고 다음 이동을 한다.
킹과 돌의 마지막 위치를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 킹의 위치, 돌의 위치, 움직이는 횟수 N이 주어진다. 둘째 줄부터 N개의 줄에는 킹이 어떻게 움직여야 하는지 주어진다. N은 50보다 작거나 같은 자연수이고, 움직이는 정보는 위에 쓰여 있는 8가지 중 하나이다.
constfs=require("fs");let[chessPieces,...commands]=fs.readFileSync("/dev/stdin").toString().trim().split("\n");chessPieces=chessPieces.split(" ");constN=chessPieces.pop();solveProblem();functionsolveProblem(){// 이동을 숫자의 증감으로 표현할 수 있도록// 열을 숫자로 변환함.chessPieces=positionToAscii(chessPieces);// 명령 배열을 돌며 명령 수행commands.forEach((command)=>{chessPieces=handleCommand(chessPieces,command);});// 출력을 위해 다시 체스 포지션 문자열로 변경chessPieces=asciiToPosition(chessPieces);// 결과 출력console.log(chessPieces.join("\n"));}// 명령 수행// @chessPieces {Array}: king, stone의 위치 정보를 담은 이차원 배열// @command {String}: 명령 문자열// @return {Array}: king, stone의 위치 정보를 담고 있는 이차원 배열functionhandleCommand(chessPieces,command){let[king,stone]=chessPieces;// king 이동.king=moveChessPiece(king,command);if(king[0]===stone[0]&&king[1]===stone[1]){// king과 store의 위치가 같으면,// stone도 이동시킴.stone=moveChessPiece(stone,command);}// 두 말의 위치가 보드 내에 있다면,// 변경된 위치 정보 반환if(checkPosition(...king)&&checkPosition(...stone))return[king,stone];// 두 말의 위치가 보드 밖에 있다면,// 변경전 위치 정보 반환returnchessPieces;}// 체스말 이동 함수// @chessPiece {Array} : 이동할 체스말 위치 정보// @command {String}: 명령 문자열functionmoveChessPiece(chessPiece,command){let[movedColumn,movedRow]=chessPiece;switch(command[0]){case"R":movedColumn++;break;case"L":movedColumn--;break;case"T":movedRow++;break;case"B":movedRow--;break;}if(command[1]){switch(command[1]){case"T":movedRow++;break;case"B":movedRow--;break;}}return[movedColumn,movedRow];}// 위치 확인 함수// 체스말의 위치가 보드 내에 있는지 확인// @column, row {String}: 체스말 열, 행 정보// @return {Boolean}functioncheckPosition(column,row){if(column>=65&&column<=72&&row>=1&&row<=8)returntrue;returnfalse;}// 체스판 위치 => 아스키코드 변환 함수// @return {Array} : 아스키코드로 변환된 king, stone의 위치 정보 이차원 배열functionpositionToAscii(chessPieces){chessPieces=chessPieces.map((chessPiece)=>{chessPiece=chessPiece.split("");chessPiece[0]=chessPiece[0].charCodeAt();chessPiece[1]=chessPiece[1]*1;returnchessPiece;});returnchessPieces;}// 아스키코드 => 체스판 위치 변환 함수// @return {Array} : 문자열로 변환된 king, stone의 위치 정보 배열functionasciiToPosition(chessPieces){chessPieces=chessPieces.map((chessPiece)=>{chessPiece[0]=String.fromCharCode(chessPiece[0]);chessPiece[1]=chessPiece[1]*1;returnchessPiece.join("");});returnchessPieces;}
여러 개의 쇠막대기를 레이저로 절단하려고 한다. 효율적인 작업을 위해서 쇠막대기를 아래에서 위로 겹쳐 놓고, 레이저를 위에서 수직으로 발사하여 쇠막대기들을 자른다. 쇠막대기와 레이저의 배치는 다음 조건을 만족한다.
쇠막대기는 자신보다 긴 쇠막대기 위에만 놓일 수 있다. - 쇠막대기를 다른 쇠막대기 위에 놓는 경우 완전히 포함되도록 놓되, 끝점은 겹치지 않도록 놓는다.
각 쇠막대기를 자르는 레이저는 적어도 하나 존재한다.
레이저는 어떤 쇠막대기의 양 끝점과도 겹치지 않는다.
아래 그림은 위 조건을 만족하는 예를 보여준다. 수평으로 그려진 굵은 실선은 쇠막대기이고, 점은 레이저의 위치, 수직으로 그려진 점선 화살표는 레이저의 발사 방향이다.
이러한 레이저와 쇠막대기의 배치는 다음과 같이 괄호를 이용하여 왼쪽부터 순서대로 표현할 수 있다.
레이저는 여는 괄호와 닫는 괄호의 인접한 쌍 ‘( ) ’ 으로 표현된다. 또한, 모든 ‘( ) ’는 반드시 레이저를 표현한다.
쇠막대기의 왼쪽 끝은 여는 괄호 ‘ ( ’ 로, 오른쪽 끝은 닫힌 괄호 ‘) ’ 로 표현된다.
위 예의 괄호 표현은 그림 위에 주어져 있다.
쇠막대기는 레이저에 의해 몇 개의 조각으로 잘려지는데, 위 예에서 가장 위에 있는 두 개의 쇠막대기는 각각 3개와 2개의 조각으로 잘려지고, 이와 같은 방식으로 주어진 쇠막대기들은 총 17개의 조각으로 잘려진다.
쇠막대기와 레이저의 배치를 나타내는 괄호 표현이 주어졌을 때, 잘려진 쇠막대기 조각의 총 개수를 구하는 프로그램을 작성하시오.
입력
한 줄에 쇠막대기와 레이저의 배치를 나타내는 괄호 표현이 공백없이 주어진다. 괄호 문자의 개수는 최대 100,000이다.
알파벳 소문자(‘a’-‘z’), 숫자(‘0’-‘9’), 공백(‘ ‘), 특수 문자(‘<’, ‘>’)로만 이루어져 있다.
문자열의 시작과 끝은 공백이 아니다.
‘<’와 ‘>’가 문자열에 있는 경우 번갈아가면서 등장하며, ‘<’이 먼저 등장한다. 또, 두 문자의 개수는 같다.
태그는 ‘<’로 시작해서 ‘>’로 끝나는 길이가 3 이상인 부분 문자열이고, ‘<’와 ‘>’ 사이에는 알파벳 소문자와 공백만 있다. 단어는 알파벳 소문자와 숫자로 이루어진 부분 문자열이고, 연속하는 두 단어는 공백 하나로 구분한다. 태그는 단어가 아니며, 태그와 단어 사이에는 공백이 없다.
정수를 저장하는 덱(Deque)를 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.
명령은 총 여덟 가지이다.
push_front X: 정수 X를 덱의 앞에 넣는다.
push_back X: 정수 X를 덱의 뒤에 넣는다.
pop_front: 덱의 가장 앞에 있는 수를 빼고, 그 수를 출력한다. 만약, 덱에 들어있는 정수가 없는 경우에는 -1을 출력한다.
pop_back: 덱의 가장 뒤에 있는 수를 빼고, 그 수를 출력한다. 만약, 덱에 들어있는 정수가 없는 경우에는 -1을 출력한다.
size: 덱에 들어있는 정수의 개수를 출력한다.
empty: 덱이 비어있으면 1을, 아니면 0을 출력한다.
front: 덱의 가장 앞에 있는 정수를 출력한다. 만약 덱에 들어있는 정수가 없는 경우에는 -1을 출력한다.
back: 덱의 가장 뒤에 있는 정수를 출력한다. 만약 덱에 들어있는 정수가 없는 경우에는 –1을 출력한다.
입력
첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 않은 명령이 주어지는 경우는 없다.
스택 (stack)은 기본적인 자료구조 중 하나로, 컴퓨터 프로그램을 작성할 때 자주 이용되는 개념이다. 스택은 자료를 넣는 (push) 입구와 자료를 뽑는 (pop) 입구가 같아 제일 나중에 들어간 자료가 제일 먼저 나오는 (LIFO, Last in First out) 특성을 가지고 있다.
1부터 n까지의 수를 스택에 넣었다가 뽑아 늘어놓음으로써, 하나의 수열을 만들 수 있다. 이때, 스택에 push하는 순서는 반드시 오름차순을 지키도록 한다고 하자. 임의의 수열이 주어졌을 때 스택을 이용해 그 수열을 만들 수 있는지 없는지, 있다면 어떤 순서로 push와 pop 연산을 수행해야 하는지를 알아낼 수 있다. 이를 계산하는 프로그램을 작성하라.
입력
첫 줄에 n (1 ≤ n ≤ 100,000)이 주어진다. 둘째 줄부터 n개의 줄에는 수열을 이루는 1이상 n이하의 정수가 하나씩 순서대로 주어진다. 물론 같은 정수가 두 번 나오는 일은 없다.
출력
입력된 수열을 만들기 위해 필요한 연산을 한 줄에 한 개씩 출력한다. push연산은 +로, pop 연산은 -로 표현하도록 한다. 불가능한 경우 NO를 출력한다.
첫번째 풀이
입력 숫자가 n번째 수보다 크면 같아질 때까지 push하고, 작으면 pop을 하는 방법으로 풀이했다. 방법이 없을때를 고려해서 try, catch를 사용했다.
constfs=require("fs");letinput=fs.readFileSync("/dev/stdin").toString().trim().split("\n");constn=parseInt(input.shift());conststack=[];constanswerArr=[];letisExist=true;// 가능 / 불가능 확인을 위한 flagletnum=1;// push 해야할 수for(letj=0;j<n;j++){if(num<=parseInt(input[j])){// push 해야 할 수가 제시된 수보다 작으면// 제시된 수까지 push 한다.while(num<=parseInt(input[j])){stack.push(num);answerArr.push("+");num++;}}elseif(stack[stack.length-1]>parseInt(input[j])){// push 해야 할 수가 제시된 수보다 크고,// stack에 있는 수가 제시된 수보다 크면// 아무리 pop해도 스택 수열을 만들 수 없다.isExist=false;break;}// 제시된 수까지 push 되었기 때문에,// pop 해주면 된다.stack.pop();answerArr.push("-");}if(!isExist){console.log("NO");}else{console.log(answerArr.join("\n"));}
정수를 저장하는 큐를 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.
명령은 총 여섯 가지이다.
push X: 정수 X를 큐에 넣는 연산이다.
pop: 큐에서 가장 앞에 있는 정수를 빼고, 그 수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
size: 큐에 들어있는 정수의 개수를 출력한다.
empty: 큐가 비어있으면 1, 아니면 0을 출력한다.
front: 큐의 가장 앞에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
back: 큐의 가장 뒤에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 –1을 출력한다.
입력
첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 않은 명령이 주어지는 경우는 없다.
1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K(≤ N)가 주어진다. 이제 순서대로 K번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다. 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다. 원에서 사람들이 제거되는 순서를 (N, K)-요세푸스 순열이라고 한다. 예를 들어 (7, 3)-요세푸스 순열은 <3, 6, 2, 7, 5, 1, 4>이다.
N과 K가 주어지면 (N, K)-요세푸스 순열을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000)
출력
예제와 같이 요세푸스 순열을 출력한다.
풀이
에디터 때와 같이 두 개의 배열을 통해 풀려고 했는데, 하나의 큐를 만들어서 풀 수 있을 것 같았다. N도 5000 이하로 크지 않아서, 시도해보기로 했다.
constfs=require("fs");letinput=fs.readFileSync("/dev/stdin").toString().trim().split(" ");constN=parseInt(input[0]);constK=parseInt(input[1]);letqueue=newArray(N);queue=queue.fill(0).map((el,index)=>(el=index+1));letcount=0;constanswerArr=[];// K번째 있는 사람을 죽이는 함수// length가 K보다 클 때와 작을 때를 나누어 구현했다.functionkill(cnt){while(cnt!==0){if(queue.length>=cnt){queue.push(...queue.splice(0,cnt));answerArr.push(queue.pop());cnt=0;}else{cnt-=queue.length;}}}while(count<N){kill(K);count++;}console.log(`<${answerArr.join(", ")}>`);
사족
다른 사람들의 풀이를 확인해보니, shift를 사용해서 한 사람들은 시간이 더 걸렸고, 배열로 큐나 스택을 직접 구현 하지 않고, index로만 값에 접근 하면 더 빠른 코드를 구현할 수 있었다.
한 줄로 된 간단한 에디터를 구현하려고 한다. 이 편집기는 영어 소문자만을 기록할 수 있는 편집기로, 최대 600,000글자까지 입력할 수 있다.
이 편집기에는 ‘커서’라는 것이 있는데, 커서는 문장의 맨 앞(첫 번째 문자의 왼쪽), 문장의 맨 뒤(마지막 문자의 오른쪽), 또는 문장 중간 임의의 곳(모든 연속된 두 문자 사이)에 위치할 수 있다. 즉 길이가 L인 문자열이 현재 편집기에 입력되어 있으면, 커서가 위치할 수 있는 곳은 L+1가지 경우가 있다.
이 편집기가 지원하는 명령어는 다음과 같다.
L 커서를 왼쪽으로 한 칸 옮김 (커서가 문장의 맨 앞이면 무시됨)
D 커서를 오른쪽으로 한 칸 옮김 (커서가 문장의 맨 뒤이면 무시됨)
B 커서 왼쪽에 있는 문자를 삭제함 (커서가 문장의 맨 앞이면 무시됨)
삭제로 인해 커서는 한 칸 왼쪽으로 이동한 것처럼 나타나지만, 실제로 커서의 오른쪽에 있던 문자는 그대로임
P $ $라는 문자를 커서 왼쪽에 추가함
초기에 편집기에 입력되어 있는 문자열이 주어지고, 그 이후 입력한 명령어가 차례로 주어졌을 때, 모든 명령어를 수행하고 난 후 편집기에 입력되어 있는 문자열을 구하는 프로그램을 작성하시오. 단, 명령어가 수행되기 전에 커서는 문장의 맨 뒤에 위치하고 있다고 한다.
입력
첫째 줄에는 초기에 편집기에 입력되어 있는 문자열이 주어진다. 이 문자열은 길이가 N이고, 영어 소문자로만 이루어져 있으며, 길이는 100,000을 넘지 않는다. 둘째 줄에는 입력할 명령어의 개수를 나타내는 정수 M(1 ≤ M ≤ 500,000)이 주어진다. 셋째 줄부터 M개의 줄에 걸쳐 입력할 명령어가 순서대로 주어진다. 명령어는 위의 네 가지 중 하나의 형태로만 주어진다.
조건문에 사용된 문도 실행된 것으로 처리된다. if문에 stack.pop()을 통해서 값이 남아있는지 확인하려고 했었는데, 이 부분에서 배열의 값이 pop 되는 바람에 계속 에러가 났었다.
문제
https://www.acmicpc.net/problem/9012
괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 부른다. 한 쌍의 괄호 기호로 된 “( )” 문자열은 기본 VPS 이라고 부른다. 만일 x 가 VPS 라면 이것을 하나의 괄호에 넣은 새로운 문자열 “(x)”도 VPS 가 된다. 그리고 두 VPS x 와 y를 접합(concatenation)시킨 새로운 문자열 xy도 VPS 가 된다. 예를 들어 “(())()”와 “((()))” 는 VPS 이지만 “(()(”, “(())()))” , 그리고 “(()” 는 모두 VPS 가 아닌 문자열이다.
여러분은 입력으로 주어진 괄호 문자열이 VPS 인지 아닌지를 판단해서 그 결과를 YES 와 NO 로 나타내어야 한다.
입력
입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 주어진다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 괄호 문자열이 한 줄에 주어진다. 하나의 괄호 문자열의 길이는 2 이상 50 이하이다.
출력
출력은 표준 출력을 사용한다. 만일 입력 괄호 문자열이 올바른 괄호 문자열(VPS)이면 “YES”, 아니면 “NO”를 한 줄에 하나씩 차례대로 출력해야 한다.
연산자를 활용하면 코드를 간결하게 만들 수 있다. 하지만 많이 사용하면 가독성이 떨어질 수 있다.
문제
https://www.acmicpc.net/problem/10828
정수를 저장하는 스택을 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.
명령은 총 다섯 가지이다.
push X: 정수 X를 스택에 넣는 연산이다.
pop: 스택에서 가장 위에 있는 정수를 빼고, 그 수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다.
size: 스택에 들어있는 정수의 개수를 출력한다.
empty: 스택이 비어있으면 1, 아니면 0을 출력한다.
top: 스택의 가장 위에 있는 정수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 –1을 출력한다.
입력
첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 않은 명령이 주어지는 경우는 없다.
출력
출력해야하는 명령이 주어질 때마다, 한 줄에 하나씩 출력한다.
스택과 큐
스택 : 택배 상하차 (입출구가 동일)
큐 : 한정판 대기열 (입출구가 다름)
스택은 후입선출 자료구조로 LIFO(Last In First Out)로, 큐는 선입선출 자료구조로 FIFO(First In First Out)이라고도 부른다.
풀이
처음에 문제를 보고 멘붕와서 각 함수를 구현해야하나 생각했었는데, 돌아보니 그럴 필요까지는 없고 그냥 조건문을 사용하면 될 것 같았다. 이 경우 if 문을 사용하는 것보다 switch case 조건문을 사용하는 것이 나을 것 같았다.
이번에는 stack과 알고리즘 관련해서 모르는 것이 많아서 구글에서 나온 블로그를 참고해서 풀이했다.
참고 풀이 : https://gurtn.tistory.com/67 (나를 제외한 천재들)
유튜브, 구글, 다른 스택 풀이들을 보니 결국 js에서 1차원 스택은 여러 상황이나 조건에 따라 구현이 다르겠지만, 당장은 배열을 통한 풀이를 생각할 수 있었다.
첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다.
출력
첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.
시간 제한 5초, 메모리 제한 8MB
접근
힌트가 카운팅 정렬이었어서, 카운팅 정렬에 대해 찾아보았다.
계수 정렬 (Counting sort)
Counting Sort는 O(n)의 시간 복잡도를 가지는 정렬 알고리즘이다. 일반적으로는 평균 시간 복잡도가 O(nlogn)인 Quick Sort 알고리즘이 더 빠르지만 수의 등장 횟수를 누적합으로 바꿔주는 Counting Sort의 경우 수의 범위 특정하게 정해진 경우 range를 구해서 빠르게 정렬할 수 있다. 하지만 대부분의 상황에서 엄청난 메모리 낭비가 될 수 있다.
일단 설명만 보고 스스로 구현을 먼저 해보고, 막히면 찾아보기로 했다.
풀이
범위에 맞는 countArr를 만들어서 풀려고 했는데, 바로 메모리 초과가 나왔다.
찾아보니, node.js는 메모리 초과가 나와서, 추후 제한 완화 예정이라고 해서 파이썬으로 찾아서 문제를 풀었다. 설명되어있는 counting sort를 사용해보고 싶었는데, 생각과는 달리 더 빠른 방법이 있었다.
python으로 풀때도 input으로 받으면 메모리 초과가 나온다고 해서, sys.stdin.readline()을 사용해서 풀었다. 나중에 node.js 메모리 제한이 풀리면 다시 풀어보고 싶다.
지민이는 자신의 저택에서 MN개의 단위 정사각형으로 나누어져 있는 M×N 크기의 보드를 찾았다. 어떤 정사각형은 검은색으로 칠해져 있고, 나머지는 흰색으로 칠해져 있다. 지민이는 이 보드를 잘라서 8×8 크기의 체스판으로 만들려고 한다.
체스판은 검은색과 흰색이 번갈아서 칠해져 있어야 한다. 구체적으로, 각 칸이 검은색과 흰색 중 하나로 색칠되어 있고, 변을 공유하는 두 개의 사각형은 다른 색으로 칠해져 있어야 한다. 따라서 이 정의를 따르면 체스판을 색칠하는 경우는 두 가지뿐이다. 하나는 맨 왼쪽 위 칸이 흰색인 경우, 하나는 검은색인 경우이다.
보드가 체스판처럼 칠해져 있다는 보장이 없어서, 지민이는 8×8 크기의 체스판으로 잘라낸 후에 몇 개의 정사각형을 다시 칠해야겠다고 생각했다. 당연히 8*8 크기는 아무데서나 골라도 된다. 지민이가 다시 칠해야 하는 정사각형의 최소 개수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다.
출력
첫째 줄에 지민이가 다시 칠해야 하는 정사각형 개수의 최솟값을 출력한다.
풀이
체스판을 먼저 만든 다음, 옳은 체스판과 비교해서 브루트 포스로 카운트 한 뒤 가장 작은 수를 찾아서 풀었다.
666은 종말을 나타내는 숫자라고 한다. 따라서, 많은 블록버스터 영화에서는 666이 들어간 제목을 많이 사용한다. 영화감독 숌은 세상의 종말 이라는 시리즈 영화의 감독이다. 조지 루카스는 스타워즈를 만들 때, 스타워즈 1, 스타워즈 2, 스타워즈 3, 스타워즈 4, 스타워즈 5, 스타워즈 6과 같이 이름을 지었고, 피터 잭슨은 반지의 제왕을 만들 때, 반지의 제왕 1, 반지의 제왕 2, 반지의 제왕 3과 같이 영화 제목을 지었다.
하지만 숌은 자신이 조지 루카스와 피터 잭슨을 뛰어넘는다는 것을 보여주기 위해서 영화 제목을 좀 다르게 만들기로 했다.
종말의 숫자란 어떤 수에 6이 적어도 3개이상 연속으로 들어가는 수를 말한다. 제일 작은 종말의 숫자는 666이고, 그 다음으로 큰 수는 1666, 2666, 3666, …. 과 같다.
따라서, 숌은 첫 번째 영화의 제목은 세상의 종말 666, 두 번째 영화의 제목은 세상의 종말 1666 이렇게 이름을 지을 것이다. 일반화해서 생각하면, N번째 영화의 제목은 세상의 종말 (N번째로 작은 종말의 숫자) 와 같다.
숌이 만든 N번째 영화의 제목에 들어간 숫자를 출력하는 프로그램을 작성하시오. 숌은 이 시리즈를 항상 차례대로 만들고, 다른 영화는 만들지 않는다.
입력
첫째 줄에 숫자 N이 주어진다. N은 10,000보다 작거나 같은 자연수이다.
출력
첫째 줄에 N번째 영화의 제목에 들어간 수를 출력한다.
첫번째 풀이
N이 10000까지 되어서 하나씩 수를 증가하면서 푸는 방식은 섹시하지 못할 것 같지만, 다른 로직이 떠오르지 않아서 일단 수행해보았다.
1보다 큰 자연수 중에서 1과 자기 자신을 제외한 약수가 없는 자연수를 소수라고 한다. 예를 들어, 5는 1과 5를 제외한 약수가 없기 때문에 소수이다. 하지만, 6은 6 = 2 × 3 이기 때문에 소수가 아니다.
골드바흐의 추측은 유명한 정수론의 미해결 문제로, 2보다 큰 모든 짝수는 두 소수의 합으로 나타낼 수 있다는 것이다. 이러한 수를 골드바흐 수라고 한다. 또, 짝수를 두 소수의 합으로 나타내는 표현을 그 수의 골드바흐 파티션이라고 한다. 예를 들면, 4 = 2 + 2, 6 = 3 + 3, 8 = 3 + 5, 10 = 5 + 5, 12 = 5 + 7, 14 = 3 + 11, 14 = 7 + 7이다. 10000보다 작거나 같은 모든 짝수 n에 대한 골드바흐 파티션은 존재한다.
2보다 큰 짝수 n이 주어졌을 때, n의 골드바흐 파티션을 출력하는 프로그램을 작성하시오. 만약 가능한 n의 골드바흐 파티션이 여러 가지인 경우에는 두 소수의 차이가 가장 작은 것을 출력한다.
입력
첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고 짝수 n이 주어진다.
출력
각 테스트 케이스에 대해서, n보다 크고, 2n보다 작거나 같은 소수의 개수를 출력한다.
풀이
각 테스트 케이스에 대해서 주어진 n의 골드바흐 파티션을 출력한다. 출력하는 소수는 작은 것부터 먼저 출력하며, 공백으로 구분한다.
그룹 단어란 단어에 존재하는 모든 문자에 대해서, 각 문자가 연속해서 나타나는 경우만을 말한다. 예를 들면, ccazzzzbb는 c, a, z, b가 모두 연속해서 나타나고, kin도 k, i, n이 연속해서 나타나기 때문에 그룹 단어이지만, aabbbccb는 b가 떨어져서 나타나기 때문에 그룹 단어가 아니다.
단어 N개를 입력으로 받아 그룹 단어의 개수를 출력하는 프로그램을 작성하시오.
풀이
먼저 set을 이용해서, 중복되는 문자가 없을 때의 경우를 제외해주고 반복문을 통해 확인하기로 정했다.