막대기를 일렬로 세울 때 맨왼쪽에서부터 시작해서 1~N이라고 숫자를 붙여준다. 이때 만약 오른쪽에서 막대기를 본다면 보이는 막대기의 개수와 그 막대기들의 각각의 자릿값을 출력하시오.
(입력): 첫 번째 줄에 N(2≤N≤100,000)이 주어지고 그 아래로 각각 자릿수에의 값 들 h(1≤h≤100,000)를 입력한다.(맨 왼쪽의 값들부터 입력한다.)
(출력): 보이는 막대기 개수와 그 자릿값들이 출력돤다.(자릿값의 시작은 1부터 시작한다.)
**입력**
6
6
9
7
6
4
6
**출력**
3
6, 3, 2
출처: 정올(http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=2626&sca=90))
12개의 풀이가 있습니다.
파이썬 3.x
bars = [6, 9, 7, 6, 4, 6]
# bars = [6, 6, 9, 7, 6, 4, 6]
# bars = [5, 5, 4, 3, 2, 1]
visible_bars = []
for idx, bar in reversed(list(enumerate(bars, start=1))):
bVisible = True
for vb in visible_bars:
if bar <= vb[1]:
bVisible = False
break
if bVisible:
visible_bars.append([idx, bar])
print("보이는 막대 개수:", len(visible_bars))
print("보이는 막대 자릿값:", [bar[0] for bar in visible_bars])
출력:
보이는 막대 개수: 3
보이는 막대 자릿값: [6, 3, 2]
C#
using System;
using System.Collections.Generic;
using System.Linq;
namespace CD253
{
class Program
{
static void Main()
{
int numOfBars = int.Parse(Console.ReadLine());
List<int> barFromRight = new List<int>(); // 우측에서 보는 시점의 막대기 = 리스트로 표현
for (int barNo = 0; barNo < numOfBars; barNo++)
{
int barLength = int.Parse(Console.ReadLine()); // 막대기 길이
// 길이, 인덱스+1 위치에 입력받은 길이의 막대기 생성
List<int> newBar = InitializeBarWithValue(barLength, barNo + 1);
barFromRight = AddBarAtLast(barFromRight, newBar); // 최우측 시점의 막대기 보기
}
List<int> result = new HashSet<int>(barFromRight).OrderByDescending(e=>e).ToList();
Console.WriteLine(result.Count);
Console.WriteLine(string.Join(", ",result.Select(i=>i.ToString())));
}
// 막대기 생성
static List<int> InitializeBarWithValue(int barLength, int initialValue)
{
List<int> result = new List<int>();
for (int i = 0; i < barLength; i++)
{
result.Add(initialValue);
}
return result;
}
// 우측에서 보는 시점의 막대기 리스트 생성
static List<int> AddBarAtLast(List<int> lastBar, List<int> addingBar)
{
List<int> resultBar;
if (lastBar.Count >= addingBar.Count)
{
resultBar = new List<int>(lastBar);
for (int i = 0; i < addingBar.Count; i++)
{
resultBar[i] = addingBar[i];
}
}
else
{
resultBar = new List<int>(addingBar);
}
return resultBar;
}
}
}
package cal;
import java.util.ArrayList;
public class Makdaegi {
public static void main(String[] args) {
//입력값
int[] arr = {5,5,4,3,2,1};
ArrayList<Integer> index = new ArrayList<Integer>();
int max = 0;
for (int i = arr.length-1; i > 0; i--) {
if (arr[i] > max) {
max=arr[i];
index.add(i);
}
}
System.out.println("보이는 막대 개수:" + index.size());
System.out.println("자리값: " + index);
}
}
Python 3.x
def inputnum():
n = int(input())
stick = [0]*n
for i in range(n):
stick[i] = int(input())
stick.reverse()
return stick
def stick_invisible(stick, i):
for j, s in enumerate(stick):
if s <= stick[i] and j > i:
stick[j] = 0
return stick
def stick_visible(stick, i):
for j, s in enumerate(stick):
if s > stick[i] and j > i:
n = j
return n
return False
def show(stick):
n = 0
for s in stick:
if s != 0:
n += 1
print(n)
stick.reverse()
for i, s in enumerate(stick):
if s != 0:
print(i+1, end = ',')
stick = inputnum()
i = 0
while True:
stick = stick_invisible(stick, i)
i = stick_visible(stick, i)
if not i:
break
show(stick)
N = input('막대기 수: ')
Str2 = input('길이들(빈칸 띄움): ').split(' ')
Poles = []
for pole in Str2:
Poles.append(int(pole))
Count = 0
Len = len(Poles)
Visible = []
for i in range(Len-1):
if (Poles[i]>max(Poles[i+1:])):
Count = Count+1
Visible.append(i+1)
Count = Count +1
Visible.append(Len)
print(Count)
print(Visible)
def f(xs):
n, m = len(xs), 0
ans = []
for i, x in enumerate(xs[::-1]):
if m < x:
ans.append(n - i)
m = x
return ans
n = int(input())
xs = [int(input()) for _ in range(n)]
ans = f(xs)
print(len(ans))
print(', '.join(str(x) for x in ans))
bars = [int(input()) for i in range(int(input()))]
seen = [len(bars)]
for i in range(len(bars)-2, -1, -1):
if max(bars[i+1:]) < bars[i]:
seen.append(i+1)
print(len(seen))
print(seen)
sticks = []
high_list = []
for i in range(int(input())):
sticks.append(input(int()))
high_list.append(sticks[-1])
seq = []
for j in range(len(sticks)-2,0,-1):
if sticks[j] >= sticks[j-1] :
high_list.append(sticks[j])
else:
high_list.append(sticks[j-1])
for q in list(set(high_list)):
for k in range(len(sticks)-1,-1,-1):
if sticks[k]==q:
seq.append(k+1)
break
seq.sort(reverse=True)
print(len(set(high_list)))
print(seq)
while True:
N = int(input("N을 입력하시오"))
if N>=2 and N<=100:
break
h_arr=[]
for i in range(N):
while True:
print(i+1,"번째",end=' ')
h = int(input("h를 입력하시오"))
if h>=1 and h<=100000:
h_arr.append(h)
break
output=[]
h_arr.reverse()
n=0
a=len(h_arr)
for k in h_arr:
if k>n :
output.append(a)
n=k
a-=1
for i in output:
print(i,end=', ')
inp = '''6
6
9
7
6
4
6'''
seq = inp.splitlines()
vis = [6]
for i in range(len(seq)-1):
if seq[i] > max(seq[i+1:]):
vis.append(i)
print(len(vis))
print(vis)
package org.javaturotials.ex;
import java.util.*;
import java.util.stream.Collectors;
public class test {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int num = sc.nextInt();
int len_max=0;
int count=0;
int[] arr = new int[num];
for(int i=0; i<num; i++) {
arr[i] = sc.nextInt();
}
for(int i=num-1; i>=0; i--) {
if(len_max<arr[i]) {
len_max=arr[i];
System.out.print(i+1 + ", ");
count++;
}
}
System.out.println("\n" + count);
}
}