러아니푸의 기록

2675번: 문자열 반복 (acmicpc.net)

Java 문제풀이

import java.util.*;

public class B2675 {

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		
		int n = scan.nextInt(); // 작업할 횟수
		String[] result = new String[n]; // 결과값을 저장할 배열
        
		// n번만큼 작업을 진행
		for(int i=0;i<n;i++) {
			int num = scan.nextInt(); // 문자를 반복할 횟수
			String str = scan.next(); // 문자열
			String str_num ="";
			// 각 문자를
			for(int j=0;j<str.length();j++) {
				// num번만큼 반복하여 출력
				for(int k=0;k<num;k++) {
					str_num += str.charAt(j);
				}
			}
			result[i] = str_num;
		}
		
		// 결과값을 모아둔 배열 출력
		for(String r:result) {
			System.out.println(r);
		}

	}

}

어쩌다보니 for문을 3중으로 써버렸습니다. 실제로 개발할때는 반복문의 중복을 최대한 피하도록 노력해야겠습니다. 생각해보면 백준도 실제 개발을 위한 공부인데.. 지금부터라도 고쳐야겠네요.

코드는 짧고 간지나게 짜는것이 아니라.. 보기 편하게 짜는것이 좋다고.. 합니다. 잘못 익힌 습관을 고치도록 노력해야겠습니다.

Java 문제풀이

import java.util.Scanner;
import java.util.LinkedList;
import java.util.Queue;

public class Main {

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int n= scan.nextInt();
		int k = scan.nextInt();
		Queue<Integer> q = new LinkedList<>(); 
		
		for(int i=0;i<n;i++) {
			q.add(i+1);
		}
		
		System.out.print("<");
		while (q.size()>0){
        	// 맨 앞에있던 숫자를 poll한 후 큐에 새로 추가하여 큐의 시작을 변경
			for(int i=0;i<k-1;i++) {
				q.add(q.poll());
			}
			System.out.print(q.poll());
			if (q.size()>0) {
				System.out.print(", ");
			}
		}
		System.out.print(">");
	}

}

요세푸스 문제를 더욱 효율적으로 풀어봤습니다.

파이썬으로 풀었을때는 어떻게 풀었는지 기억이 안나는데 이 방법이 가장 효율적인 것 같습니다.

큐를 선언하여 지정된 수 만큼의 숫자를 순차적으로 큐에 추가합니다.

k번째에 세어지는 숫자가 순차적으로 제거되기 떄문에 k-1번의 횟수만큼 큐의 맨 앞에 있는 숫자를 지웠다가 새로 추가하여 뒤로 보내는 작업을 합니다. 그러면 맨 앞에 있는 숫자가 k번째 숫자가 되기 때문에 그 숫자를 poll해줍니다.

출력은 <?, ?, ?, ?>형태로 하도록 되어있기 때문에 지저분해졌지만 문제는 풀었습니다..ㅎㅎ

Python 문제풀이

# 프린터 큐
n = int(input())
result=[]
for i in range(n):
    a,b = map(int, input().split())# a는 문서의 개수, b는 출력 순번을 알고자하는 문서의 위치
    x= input().split()
    y=[]
    #y는 처음 입력받은 문서의 중요도 리스트
    for j in range(a):
        y.append(x[j])
    x.sort(reverse=True) #x는 문서의 중요도 리스트를 내림차순 시킨 것
    position=0 #y를 원형큐로 사용하기 위해 현재 위치를 나타내는 변수

    for j in range(a):# 문서의 개수만큼 반복
        while 1:
            if y[position] == x[j]: #만약 찾고있는 중요도가 리스트(y)에서 발견되었는데
                if position==b: #y에서 발견된 위치와 출력 순번을 알고자하는 문서의 위치가 동일하다면
                    result.append(j+1) # j+1번째에 출력되었습니다. (결과리스트에 추가)
                # 포지션 증가 (원형큐)
                if position == a - 1:
                    position = 0
                else:
                    position += 1
                break
            # 포지션 증가 (원형큐)
            if position == a-1:
                position=0
            else:
                position +=1

for i in range(n):
    print(result[i])

자세한 것은 주석에 작성하였습니다.

원형큐를 구현하기 위한 포지션 증가값의 코드 반복이 조금 거슬리긴 했지만 오늘은 문제를 풀은것으로 만족하겠습니다. 다음부터는 꼭 함수의 사용을..!

Python 문제풀이

n = int(input())
x=[]
sum=0
for i in range(n):
    num=int(input())
    if num !=0:
        x.append(num)
    else:
        x.pop()

for i in range(len(x)):
    sum+= x[i]

print(sum)

너무 간단한 문제입니다. 0이 아니면 push해주고 0이라면 pop을 해줍니다.

결국 마지막에 남은 값들을 더해서 그 값을 출력합니다.

Python 문제풀이

text = input()
result =0
i=0
while len(text)-2>=i: # 문자열 리스트 길이를 넘는 것을 방지하기 위해 -1을 해야겠지만
    # 이 경우를 보면 i+1의 값을 비교해볼때가 있기 때문에 1회 더 줄여서 -2를 해줍니다.
    # 마지막 문자는 검사를 안하느냐 걱정될 수 있습니다. 주석을 계속 읽어봅시다.
    if text[i]=='c' and (text[i+1]=='-' or text[i+1]=='='):
        result +=1
        i +=1 # 크로아티아 문자열이 된 길이만큼 반복문의 핵심인 i값을 증가시켜 일반 알파벳으로 인식되는 것을 회피합니다.
    # 문자열 길이를 넘는 것을 방지하기 위해 'dz='의 경우는 i의 여유를 1개 더 가진 상태일떄 확인합니다.
    elif text[i]=='d' and (text[i+1]=='-' or (text[i+1]=='z' and len(text)-3>=i and text[i+2]=='=')):
        if text[i+1]=='z':
            result += 1
            i += 2
        else:
            result += 1
            i += 1
    elif text[i]=='l' and text[i+1]=='j':
        result += 1
        i += 1
    elif text[i]=='n' and text[i+1]=='j':
        result += 1
        i += 1
    elif text[i]=='s' and text[i+1]=='=':
        result += 1
        i += 1
    elif text[i]=='z' and text[i+1]=='=':
        result += 1
        i += 1
    else:
        result += 1
    i +=1 # for문이 아니기 때문에 기본적인 i값을 항상 증가시켜줍니다.

# 만약 i값이 문자열길이-1과 값이 같다면, 마지막 값이 크로아티아 문자가 아닌 경우이기 때문에 세어지지 않았습니다.
if len(text)-1 == i:
    result +=1 # 결과값을 1 증가시켜줍니다.

print(result)

간단하게 문자열의 각 자리의 뒷부분을 비교해보면서 크로아티아 문자가 되는 경우는 result값에 1을 증가시켜줍니다. 크로아티아 문자열이 된 길이만큼 반복문의 핵심인 i값을 증가시켜 일반 알파벳으로 인식되는 것을 회피합니다.

자세한 것은 주석을 확인하셔도 좋을것같습니다. 열심히 적었습니다 : )

Python 문제풀이

n = int(input()) # 수열의 요소 개수
x=[] # 입력받은 수열
y=[0] # 작업할 스택 공간, 0을 넣어준 이유는 y[-1]을 했을때 범위 오류 방지용
result=[] # +,- 등의 결과를 저장할 리스트

# 수열을 입력받는다
for i in range(n):
    x.append(int(input()))

current=0 # push되는 스택의 현재 수
for i in range(n):
    if y[-1]<x[i]: # 스택의 top에 위치한 값이 수열 값보다 작다면
        while current<x[i]: # push되는 스택의 현재 수가 수열 값과 같아질때까지 push한다
            current += 1
            y.append(current) #push 작업
            result.append('+')
        y.pop() # 수열에 입력된 값이라는 뜻은 결국 pop을 당했던 것이기 때문에 해준다.
        result.append('-')

    elif y[-1]==x[i]: # 스택의 top에 위치한 값이 수열 값과 같다면
        y.pop() # 그대로 pop해준다
        result.append('-')
    else: # 스택의 top에 위치한 값이 수열 값보다 크다면
        print('NO') # 직접 해보면 알겠지만 이 경우가 NO를 출력해야하는 경우이다
        exit()

for i in range(len(result)): # 결과를 출력한다
    print(result[i])

1차로 문제 이해가 안가서 고전하다가 2차로 구현에서 고전했는데.. 뭐든 원리에서 답이 나오는것같습니다.

주석으로 설명을 쓰긴 했지만 핵심 부분을 설명하겠습니다.

- 수열에 입력된 값은 pop이 되면서 입력된 값들이다. 수열에 입력된 값에 도달하는 순간 그 값은 pop을 당해야 한다.

  : 그렇기 때문에 수열이 현재 스택의 top 값보다 큰 값을 요청했다면 그 값까지 push를 한 뒤 pop을 한 번 당한것이다.

- push작업이 필요한게 아닌 경우라면 항상 top의 값과 수열의 요청값이 같을것이다.

  : 이 문제에서는 push와 pop만 진행하는데 push작업이 필요한 경우는 수열이 현재 스택의 top 값보다 큰 값을 요청했을 경우이다. 더 추가를 해야하는 경우가 아니라면 빼는 pop 작업밖에 없다. 근데 스택은 빼는 작업을 항상 top에서만 진행하기 때문에 pop작업을 요청했다면 항상 top과 수열의 요청값이 같다.

- 그렇다면 수열에 입력된 값이 top 값보다 작은 경우는 어떻게 되는가?

  : 그 경우가 스택이 깨지는 순간이다. 'NO'를 출력하면 된다. 스택은 top에있는 값만을 pop할 수 있는데 top 값을 무시하고 그 속에있는 값을 요청하는 꼴이기 때문이다.

Python 문제풀이

#요세푸스 문제
a,b = map(int, input().split()) # a는 인원수, b는 삭제되는 자리 위치

x = []
result =[]
# 편하게 리스트에 사람들을 세움
for i in range(a):
    x.append(i)

#count는 삭제되는 자리위치를 셀 변수, current는 현재 위치
count=1
current=-1 #시작마다 current를 1씩 증가시켜 주기 위해 완전 초기 시작은 -1

while 1:
    #만약 1명밖에 남지 않았다면 그사람 출력하고 종료
    if len(x)==1:
        result.append(x[0]+1)
        break
    #만약 현재 위치가 리스트 맨 끝 자리라면 초기로 돌아가도록 한다
    if current == len(x)-1:
        current = 0
    else: #아니라면 그냥 1 증가
        current +=1

    #만약 count가 삭제될 순번이 되었다면 삭제
    if count ==b:
        count =1
        result.append(x[current]+1)
        del x[current]
        current -=1 #삭제후 리스트 길이가 줄면서 범위를 넘게되는걸 방지하기 위해 -1
        continue
    count +=1

#도대체 왜 이렇게 출력하라고 했을까?
print('<', end='')
for i in range(len(result)-1):
    print(result[i], end='')
    print(', ',end='')
print(result[-1],end='')
print('>')

코딩이 조금 복잡해져서 주석으로 약간의 설명을 적었습니다.

사람이 삭제되어야 할 순간에는 결과값을 출력할 result리스트에 추가하였습니다.

코드의 주요 부분을 설명드리겠습니다. count는 삭제되는 번째의 수의 카운트입니다. 3번째 사람을 삭제시킨다고 하면 일단 3번째인 것을 알기위해 1부터 3까지 숫자를 세야할겁니다. 그 카운트입니다.

current는 현재 위치입니다. 7명의 사람이 있다고 치면, count와 함께 하나씩 증가하며 count가 삭제 위치에 도달했을때 현재 위치의 사람을 없애기 위해 존재하는 변수입니다.

다만 유의할 점이 있습니다. 현재위치가 리스트의 마지막일 경우 사람을 한명 삭제하면 리스트의 길이가 1 줄어듭니다. 사람을 삭제했을때 current 변수 값을 하나 줄이지 않으면 다음 계산때 리스트 밖을 벗어나게 되기 때문에 -1을 해줍니다.

current를 -1했을때 현재위치가 차이나는것은 while문을 시작하자마자 증가시켜주기 때문에 걱정하지 않으셔도 됩니다. 그리고 현재 위치가 리스트의 마지막 부분이라면 1을 증가시켜야 할 부분에서 리스트의 0번째 위치로 이동하도록 변경합니다. 원형리스트를 만들었다고 생각하면 됩니다.

while문을 통해 사람을 없애다가 사람이 한명밖에 안남았다면 그냥 그 사람을 결과 리스트인 result에 추가하고 반복문을 탈출합니다.

마지막으로 결과리스트를 출력할때 <3,1,4,....>의 모양을 갖추기위해 코드를 좀 작성해줍니다.

이 문제는 백준 10828번 스택 문제의 연장선입니다. 먼저 확인하시는 것을 추천드립니다.

[백준 10828번] 스택 Python 풀이 :: 러아니푸의 공부방 (tistory.com)

Python 문제풀이

#큐
import sys

n = int(input())
x=[]
for i in range(n):
    # 입력을 input을 쓰지말고 이렇게 활용해야 빠르게 풀 수 있다.
    order= sys.stdin.readline().rstrip()

    if order =='pop':
        if len(x)==0:
            print(-1)
        else:
            print(x.pop())
    elif order =='size':
        print(len(x))
    elif order =='empty':
        if len(x)==0:
            print(1)
        else:
            print(0)
    elif order =='top':
        if len(x)==0:
            print(-1)
        else:
            print(x[-1])
    elif order =='front':
        if len(x)==0:
            print(-1)
        else:
            print(x[-1])
    elif order =='back':
        if len(x)==0:
            print(-1)
        else:
            print(x[0])
    else:
        x.insert(0, order.split()[1])

스택과 다른 점은 push로 입력받을때 0번째 위치로 넣어주고 나머지 작업은 리스트의 맨 마지막에서 이루어진다는 것 입니다. 물론 back을 입력받았을 경우에는 제일 최근 숫자가 들어온 위치인 0번째를 출력해줍니다.

이 외에는 스택 문제와 다른점이 없습니다. 시간초과가 나셔서 찾아오셨다면 sys.stdin.readline().rstrip()로 명령을 입력받는 것을 추천드립니다.

백준 1427번 소트인사이드 문제의 연장선 같습니다. 먼저 소트인사이드를 확인하시는 것도 좋을것같습니다.

[백준 1427번] 소트인사이드 Python 풀이 :: 러아니푸의 공부방 (tistory.com)

Python 문제풀이

n = input()
x = []
sum=0
result=''

#내림차순 정렬
for i in range(len(n)):
    x.append(n[i])
x.sort(reverse=True)

#내림차순 된 리스트를 문자열로 변환, 값 더하기
for i in range(len(x)):
    result += x[i]
    sum += int(x[i])

#모두 더한 값이 3으로 나눠지며 제일 작은 값이 0이라면
if sum%3==0 and result[-1]=='0':
    print(result) #30으로 나누어지는 숫자이니 출력
else:
    print(-1)

해당 문제는 입력받은 문자열을 내림차순으로 정렬한 후, 3으로 나눠지는 수.. 즉 각 자리수를 모두 더한 값이 3으로 나눠지는지 확인하고, 이 문제는 30으로 나누어지는 것을 원했으니 제일 작은 수 부분에 0이 있다면 30으로도 충분히 나누어지는 수가 됩니다.

상대방에게 이해되도록 설명하는 것이 어렵네요. 역시 개발자들은 코드로 이야기하는게 좋은것 같습니다! ㅎㅎ

Python 문제풀이

n = input()
x = []
result=''
for i in range(len(n)):
    x.append(n[i])
x.sort(reverse=True)

for i in range(len(x)):
    result += x[i]
print(result)

입력 받은 문자열을 내림차순하기 위해서 리스트에 하나씩 옮겨담습니다.

파이썬은 참 다양하고 편리한 함수가 많은것같습니다.

sort를 이용하여 리스트를 정렬하는데 reverse=True 옵션을 넣어 정렬해줍니다.

정렬이 끝난 리스트는 문자열로 변환하여 출력합니다.